Quick sort is a divide and conquer inplace sorting algorithm. This is a preferable sorting algorithm for many practical applications because of its average case performnace is very good- O(n log n).
Quick sort takes an array and partitions around a pivot item X such that elements left of X are smaller than X and elements right of X is greater than or equal to X. It takes O(n) to partition any array.
It then recursively sorts subarrays left of X and right of X recursively. If partitions are done in the middle on average total runtime will be O(n log n).
partition(items, left, right) X = items[left] I = left FOR J = left+1 TO right IF items[J] <= X I = I + 1 swap(items[I], items[J]) swap(items[left], items[I] RETURN I
quicksort(items, left, right) if left < right r = partition(items, left, right) quicksort(items, left, r-1) quicksort(items, r+1, right)
We call the quicksort function passing the array and entire range initially.
quicksort(items, 1, n);
Lets take an array of numbers
items = [27, 54, 43, 56, 9, 23, 4, 13, 17]
We start by calling
quicksort(items, 0, 8)
Lets execute the partition statement of quicksort function since left < right or (0 < 8) is TRUE
r = partition(items, 0, 8)
Initially left = 0 right = 8
X=27 I=1
FOR J = 1
item[1] = 54 (54 <= 27) is FALSE so we move to next iteration
FOR J = 2
item[2] = 43 (43 <= 27) is FALSE so we move to next iteration
FOR J = 3
item[2] = 56 (56 <= 27) is FALSE so we move to next iteration
FOR J = 4
item[4] = 9 (9 <= 27) is TRUE I = 0 + 1 = 1 We swap items[1] and items[4], so 9 and 54 swaps their places and items becomes
items = [27, 9, 43, 56, 54, 23, 4, 13, 17]
FOR J = 5
item[5] = 23 (23 <= 27) is TRUE I = 1 + 1 = 2 We swap items[2] and items[5], so 43 and 23 swaps their places and items becomes
items = [27, 9, 23, 56, 54, 43, 4, 13, 17]
FOR J = 6
item[6] = 4 (4 <= 27) is TRUE I = 2 + 1 = 3 We swap items[3] and items[6], so 4 and 56 swaps their places and items becomes
items = [27, 9, 23, 4, 54, 43, 56, 13, 17]
FOR J = 7
item[7] = 13 (13 <= 27) is TRUE I = 3 + 1 = 4 We swap items[4] and items[7], so 13 and 54 swaps their places and items becomes
items = [27, 9, 23, 4, 13, 43, 56, 54, 17]
FOR J = 8
item[7] = 17 (17 <= 27) is TRUE I = 4 + 1 = 5 We swap items[5] and items[8], so 17 and 43 swaps their places and items becomes
items = [27, 9, 23, 4, 13, 17, 56, 54, 43]
FOR loop is now complete (J is now equal to right).
We now swap items[left] = items[0] and items[5] so 17 and 27 swap their places and items becomes
items = [17, 9, 23, 4, 13, 27, 56, 54, 43]
No if you look at the items array any number that is smaller than 27 ia on the left of 27 and any number greater is on the right side of 27.
Now if we recursively partition left of 27 and right of 27 we well have our sorted items.
Here r = 5. So we call quicksort with
quicksort(items, 0, 5) quicksort(items,6, 8)
We continue this and recursion of any branch stops when left < right is true. Then the subarray is completely sorted and there is nothing to do.
Quickselect
The quick select algorithm finds the k-th smallest number given an array of numbers containing items greater than or equal to k (you cn not find 6th smallest item from an array of 5 items).
This algorithms is very similar to the quicksort algorithms and uses the same partition function. When one partition is made and position of partition r is greater than k we partition left subarray (r+1, right) and if r is smaller than k we partition roght subarray (left, r-1).
quickselect(items, left, right, k) if(left == right) return items[left] r = partition(items, left right) if r == k return items[k] if r > k return quickselect(items, left, r-1) else return quickselect(items, r+1, right, k)
Please not that the algorithm does not check any error condition.
