how to understand quick sort algorithm

Question

I am learning quick sort in java, according to the material I have. The best case is the pivot is the median, worst case is when one side of the pivot is always empty.

For the following code, is "indexPartition" the pivot? What kind of parameters do you put in the following function so it will run in the worst situation?

    private void quickSortSegment(E[] list, int start, int end)
{
  if (end-start>1) 
  { 
     int indexPartition = partition(list, start, end);
     quickSortSegment(list, start, indexPartition);
     quickSortSegment(list, indexPartition+1, end);
  }
}

private int partition(E[] list, int start, int end)
{
  E temp; 
  E partitionElement = list[start];
  int leftIndex = start; 
  int rightIndex = end-1;
  while (leftIndex<rightIndex)
  {  
    while (list[leftIndex].compareTo(partitionElement) <= 0 && leftIndex<rightIndex)
    {
        leftIndex++; 
    }
    while (list[rightIndex].compareTo(partitionElement) > 0)
    {
        rightIndex--; 
    }
     if (leftIndex<rightIndex)
     {  
        temp = list[leftIndex];
        list[leftIndex] = list[rightIndex];
        list[rightIndex] = temp;
     }
  }
  list[start] = list[rightIndex];
  list[rightIndex] = partitionElement;
  return rightIndex;
}

http://stackoverflow.com/questions/4019528/quick-sort-worst-case — Damian0o, Jun 20 '13 at 08:32
http://en.wikipedia.org/wiki/File:Sorting_quicksort_anim.gif — Ilya, Jun 20 '13 at 08:36
I highly recommend watching some videos, you can find really nice youtube videos — anvarik, Jun 20 '13 at 09:02

score 1 · Accepted Answer · answered Jun 20 '13 at 08:33

No the pivot is partitionElement. It also seems this code always selects the first element in the sequence to be the pivot. The function will run in all cases including the worst cases, but it will perform badly(have square complexity).

Different people propose different solutions for selecting the pivot but I personally like this one: Select 3 random elements from the interval in consideration, compute their average and use it as pivot.

score 1 · Answer 2 · edited Feb 08 '17 at 14:42

1

Quick Sort Video

This video along with the wikipedia article should clear things up. Wikipedia is pretty awesome for explaining sorting algorithms. With respect to your question, indexPartition is rightIndex, which is the index of partitionElement, the pivot.

edited Feb 08 '17 at 14:42

Community

1
1

answered Jun 20 '13 at 09:08

Steve P.

14,489
8
42
72

score 1 · Answer 3 · answered Jun 20 '13 at 10:07

Something wrong with this method partition(), e.g. for {3,1,2} we'll get {1,3,2}:

public class CompareApp {
public static void main(String... args) {
    Integer[] arr = {3, 1, 2};
    quickSortSegment(arr, 0, 2);
    for (Integer i : arr) System.out.println(i);
}

private static <E extends Comparable> void quickSortSegment(E[] list, int start, int end) {
    if (end - start > 1) {
        int indexPartition = partition(list, start, end);
        quickSortSegment(list, start, indexPartition);
        quickSortSegment(list, indexPartition + 1, end);
    }
}


private static <E extends Comparable> int partition(E[] list, int start, int end) {
    E temp;
    E partitionElement = list[start];
    int leftIndex = start;
    int rightIndex = end - 1;
    while (leftIndex < rightIndex) {
        while (list[leftIndex].compareTo(partitionElement) <= 0 && leftIndex < rightIndex) {
            leftIndex++;
        }
        while (list[rightIndex].compareTo(partitionElement) > 0) {
            rightIndex--;
        }
        if (leftIndex < rightIndex) {
            temp = list[leftIndex];
            list[leftIndex] = list[rightIndex];
            list[rightIndex] = temp;
        }
    }
    list[start] = list[rightIndex];
    list[rightIndex] = partitionElement;
    return rightIndex;
}}

java system.compare.CompareApp

1 3 2

Also it will not sort size=2 arrays (sub-arrays): {3,1} -> {3,1} — alex, Jun 20 '13 at 10:32

how to understand quick sort algorithm

3 Answers3