The first time run partition function. partition([4,8,7,1,3,5,6,2], 0, 7)

index is actually the swap position if any number less than 4(first item) is found

- compare 8 with 4, 8>4, no change
- compare 7 with 4, 7>4, no change
- compare 1 with 4, 1<4, swap 1 with 8 (put the less number behind 4) and index++ (count the number less than 4)
- now the array is 4,1,7,8,3,5,6,2
- compare 3 with 4, 3<4, swap 3 with 7 and index++
- now the array is 4,1,3,8,7,5,6,2
- compare 5 with 4, 5>4, no change
- compare 6 with 4, 6>4, no change
- compare 2 with 4, 2<4, swap 2 with 8 and index++
- now the array is 4,1,3,2,7,5,6,8
- it executes swap(arr, pivot, index - 1); which swaps 4 with 2.
- now the array is 2,1,3,4,7,5,6,8

As it reaches the end of the array, partition method is done, it returns 3, which is the position index of number 4 in current array.

We can see left to the 4, they are all numbers less than 4. The right side of 4 are all the numbers great than 4.

Then it will do recursive quickSort on left and right.

The worst time complexity is O(n

^{2})

cn+c(n−1)+c(n−2)+⋯+2c=c(n+(n−1)+(n−2)+⋯+2)=c((n+1)(n/2)−1)=c((n

^{2}+n)/2-1) => O(n

^{2})

The best time complexity is O(nlogn).

Quicksort's best case occurs when the partitions are as evenly balanced as possible: their sizes either are equal or are within 1 of each other.

Here is the dual pivot quick sort.

http://www.geeksforgeeks.org/dual-pivot-quicksort/

The basic idea is that it has two pivots, the left and the right. If the left > right, swap them. Then move anything < left to the left of left pivot and anything > right pivot to the right of the right pivot.

## No comments:

## Post a Comment