Write the algorithm of quick sorting?

Answer 1

1- set pass =1

2- repeat step 3 varying j from 0 to n-1-pass

3- if the element at index j is >than the element at index j+1 swap the two element

4- increment pass by 1

5-if pass is <=n-1 go to step 2

Answer 2

Given an unsorted sub-array, select a pivot element and divide the array into two-subarrays, such that all elements to the left of the pivot are less than the pivot and all elements to the right are greater than or equal to the pivot. The pivot is now its correct place, but each of the sub-arrays remains unsorted. Repeat recursively for each sub-array. The terminating condition for a recursion is reached when the sub-array has fewer than 2 elements (an array of 0 or 1 elements can always be regarded as being sorted).

Pivot selection is key to optimal performance. Ideally, the pivot should represent the median of the sub-array (thus equally dividing the array), however the elements must be in sorted order to obtain the median which would naturally render the algorithm moot. Selecting the median of the first, last and middle element (the median of three) is one possible solution, however selecting an element at random can be just as good, and is particularly effective at guarding against data deliberately ordered to render quicksort as inefficient as possible when pivot selection is predictable.

Once a pivot is selected, swap it with the final element. We now partition the reminder of the sub-array. We start by pointing to the lower (left) and upper (right) bounds of the sub-array (excluding the pivot). Now work from each end until we find a left element that is not less than the pivot and a right element that is less than the pivot. If the left and right pointers haven't met or crossed each other, we swap the elements and continue. When the left and right pointers do meet or cross each other, we swap the pivot and the left element. The pivot is now in its correct place and we can now recurse over the sub-arrays on either side.

Note that if we initially swap the pivot with the first element instead of the last element, we must swap it with the right pointer instead of the left pointer.

In some cases the pivot may end up in the first or last position of the sub-array which means we possibly made a poor choice when selecting the pivot; one of the sub-arrays is empty. However, an empty sub-array represents the terminating condition for a recursion, so it doesn't affect the algorithm it only affects performance and is why pivot selection is so important to the partitioning process.

Performance can be improved by recursing over the smaller of the two sub-arrays (an empty sub-array will immediately return). The larger sub-array can be handled iteratively by adjusting the formal arguments of the current instance of the function and then jumping to the start of the function with a goto. However, given that the second recursion is also the final statement of the algorithm, a modern compiler can handle this for us using tail-call optimisation.

Performance can be further improved by dividing the array into three sub-arrays. The middle sub-array represents all the elements that are equal to the pivot and therefore does not need sorting, we simply recurse over the outer two sub-arrays. However, this is only of benefit if we know the array contains many duplicates.

A further optimisation we can make is to terminate a recursion when the sub-array has k elements or less. This means that when all recursions have terminated, all unsorted elements will be no more than k elements away from their final position, thus we can efficiently apply the insert sort algorithm iteratively across the entire array to finalise the sort. Choosing the optimum value for k is critical to this optimisation and is largely hardware dependant, however values in the range of 5 to 15 work for most implementations.

It is important to note that quicksort is an unstable sort. This means that elements of equal value might switch position relative to the order they were originally input. The input order is important when an object has several keys. For example, when we sort files by name and then sort again by type we would expect all files of the same type to remain in name order. With a stable sort we get this automatically without having to keep track of which key is secondary because it is either the original input order or the output order from the previous sort. With an unstable sort, the complexity of making it stable can render it less efficient than a naturally stable sort.

Answer 3

Given the start and end iterators of a subset, if the subset has less than two elements then the subset is sorted. Otherwise, select any pivot element from the subset and partition the subset such that all elements lower than the pivot are on the left of the pivot, and all other elements are on the right of the pivot. Repeat the algorithm for each subset on either side of the pivot.

Selecting the pivot depends on whether the subset permits random access or not. If not, select the last element, otherwise select an element at random and swap it with the last element.

To partition the subset, initialise left and right iterators to the start and end of the subset. Advance from the left until you locate a value that is not less than the pivot, then advance from the right until you locate a value that is less than pivot. If the iterators have not crossed each other, swap the elements and continue searching from those points. As soon as either iterator crosses the other, swap the left element with the pivot element. The pivot is now in the correct place, with all lower elements to its left and all other elements to its right. You can then sort each of these subsets in the same way.

Answer 4

greedy method