Tuesday, October 11, 2016

quick sort and its time complexity

Here is the javascript implementation.
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(n2)

cn+c(n−1)+c(n−2)+⋯+2c=c(n+(n−1)+(n−2)+⋯+2)=c((n+1)(n/2)−1)=c((n2+n)/2-1) => O(n2)

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.

No comments:

Post a Comment