quickSort re-explained (hopefully with more clarity)

[Søren Kyale]

let quickSort be a function

list is a list to be sorted.

low is the index of the first element to sort

high is the index of the last element to sort

@n is a reference to the nth element in list

if low equals high

   then 

      return because the sort is complete since a one element list 

      needs no sorting thought it might help to use insertion sort if 

      the difference between low or high is small.

      # example:

      # if high - low < small

      #     then

      #        return iSort with arguments list, low, high.

      #        note: to do this your iSort must accept three

      #        arguments. See my pseudo code for iSort.

   pivot = low    # this is dull sad and ugly but will work in some cases.

   # it is better to set the pivot to the median of

   # three points.

   # example:

   #

   # pivot = the average of low and high

   #

   # python can do this quickly with the bitwise 

   # shift operator >>

   # for example a + b >> 1 = (a+b)/2 yet may be quicker.

   # continuing on:

   #

   # if @pivot > @high

   #  then

   #     pivot = high

   #

   # if @pivot <= @low

   #  then

   #     pivot = low

   #

   #  swap @pivot and @low

   #  pivot = low

   #

   # Now pivot has the median value of the low, middle and

   # high indexes and is stored in the position of the low

   # index.

   index, pointer = low, low

   

   for index, [low+1, high] # from low+1 to high inclusive

      if @index < @pivot

         then

            add one to pointer

            swap @pointer and @index

   swap @pivot and @pointer to put the pivot where it belongs

   you only need to sort lists with two unsorted elements so

   if low+1 < pointer

      then 

         quickSort with arguments list=list, low=low and high=pointer + 1

   if high-1 > pointer

         then

            quickSort with arguments list=list, low=pointer + 1, high=high.

The uncommented portions are pretty much the same as the project 5 standard except with fewer unnecessary recursions. The commented out show how to greatly improve pivot selection and sorting of short fragments.

[Søren Kyale]

The code I gave for finding a median was in error (same on me for not having a test):

Example: sorted([a,b,c])[1] == median(a,b,c)

Here's the revised code for finding a median:

@index = List value at index

mindex: list, int, int -> int

    compare the list values each index and return the index that gives the lower result.

    example for python (i if aList[i] < aList[j] else j)

pivot = mindex(List, end, mid)

   if @start < @pivot, then congrats, you fond a median.

   else

      pivot = mindex(List, start, mid)

      if @end < @pivot, then congrats you found a median

      else

          pivot = mindex(List, start, end) # since neither start nor end are minimums, the lesser of the two  must be the median of the three.

Also, for quick sorting, the biggest issue seems to be on lists with many identical entries. Choosing a good pivot and taking care of these entries makes it fairly reliable for O(nlog(n)).