CODEWITHSUNDEEP
javaalgorithm
June
June

Reputation: 1014

how to understand quick sort algorithm

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;
}

Upvotes: 0

Views: 1740

Answers (3)

alex
alex

Reputation: 19

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

Upvotes: 1

Steve P.
Steve P.

Reputation: 14709

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.

Upvotes: 1

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

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.

Upvotes: 1

Related Questions