Quicksort

In order to sort a data set efficiently, algorithms are written. Two common sorting algorithms are Quicksort, and Heapsort.
Quicksort will be the first algorithm we will go over. Quicksort is considered a "comparison sort" algorithm, as it uses less-than operators to sort the data. Because of this, the algorithm can run directly on the array, only needing a low amount of additional memory. It's Big-O notation is O(n log n) for Best Case Performance and O(n2) for Worst Case Performance. Quicksort was developed in 1959 by Tony Hoare, a British Computer Scientist. If the quicksort algorithm is used correctly, it can sort at a rate two to three times faster than Mergesort and Heapsort. 


To start, you select a pivot element in the array. In order to prevent integer overflow, especially in large amounts of data, you should choose the middle element. Once assigned to a variable, you can then start the main portion of the algorithm, which is partitioning the elements.

First, assign a variable (usually i ) to the left-most element in the array. Then, assign another variable (usually j ) to the right-most element in the array.

Increase i until the value of array[i] is greater than the pivot element. Decrease j until the value of array[j] is less than the pivot element. Exchange these two elements in the array. Increase i and decrease j  after each exchange. Once all of the elements less than the pivot element are to the left of the pivot element, and all of the elements greater than the pivot element are to the right of the pivot element, repeat this quicksort operation on both the left and right partitions of the pivot, excluding the pivot from each. Recursively quicksort each partition until you are left with a sorted array.


Pseudo Code:
function quicksort(array) var list less, equal, greater if length(array) ≤ 1 return array select a pivot value pivot from array for each x in array if x < pivot then append x to less if x = pivot then append x to equal if x > pivot then append x to greater return concatenate(quicksort(less), equal, quicksort(greater))
(from http://www.codecodex.com/wiki/Quicksort#Pseudocode)

VIDEO EXAMPLE





QUESTIONS:

  1. 1 point
    What is the pivot element of the array [8,5,4,9,2,7,6,3,1] using the (lo + (hi-lo)/2) equation?
  2. 1 point
    What is the pivot element of array[1,2,3,4] using the (lo + (hi-lo)/2) equation?
  3. 1 point
    Should the variable i be increased in the given array?
    i j
    1 3 5 6 8 9 4 2 9
  4. 1 point
    Should the variable j be decreased in the given array?
    i j
    1 3 5 6 8 9 4 2 9
  5. 1 point
    What should happen next?
    i j
    1 3 5 6 8 9 4 2 7
  6. 1 point
    What happens if i is greater than j?