MaheshT.com

Performance

• Best: O(n Log n)
• Average:O(n Log n)
• Worst: O()

Steps in one iteration of a quick sort:

• Select the leftmost element as pivot. Remove the pivot from the list and keep it outside.
• There are two pointers, one in the left (left pointer ) and one in right ( right pointer). In the beginning, the left pointer points to the empty space of pivot and the right pointer at the rightmost element in the list
• At any step, either the left pointer or right pointer element would be empty.
  Compare the non-empty element which is pointed by either right or left pointer with pivot.
• If the right pointer element less than the pivot, move it to empty space pointed by the left pointer and move the left pointer by one element toward the center of the list.
• If the right pointer element greater than or equal to the pivot, keep it in the same place and move the right pointer toward the center by one element.
• If the left pointer element less than or equal to the pivot, keep it in the same place and move the left pointer toward the center by one element.
• If the left pointer element is greater than the pivot, move to the empty space pointed by the right pointer and move the right pointer toward the center by one element.
• When the left pointer and left pointer collides, move the pivot to that location. This will put pivot in the correct position in the list
• Split the given list into two sub-lists divided by the pivot and run the same steps on each of them.
• Run this recursively.

Quicksort implementation in Java

import java.util.Random;

/**
 * @author MaheshT
 *
 */
public class QuickSort {

  private  void sort(final int inList[], int start, int end) {
    int pivot = inList[start]; // consider this as  hole at inList[start],
    int leftPointer = start;
    int rightPointer = end;
    final int LEFT = 1;
    final int RIGHT = -1;
    int pointerSide = RIGHT; //  we start with right as pivot is from left

    while (leftPointer != rightPointer) {
      if (pointerSide == RIGHT) {
        if (inList[rightPointer] < pivot) {
          inList[leftPointer] = inList[rightPointer];
          leftPointer++;
          pointerSide = LEFT;
        } else {
          rightPointer--;
        }
      } else if (pointerSide == LEFT) {
        if (inList[leftPointer] > pivot) {
          inList[rightPointer] = inList[leftPointer];
          rightPointer--;
          pointerSide = RIGHT;
        } else {
          leftPointer++;
        }
      }
    }
    //put the pivot where leftPointer and rightPointer collide
    inList[leftPointer]=pivot;

    if((leftPointer - start) > 1){
      sort(inList, start, leftPointer-1);
    }

    if((end - leftPointer) > 1){
      sort(inList, leftPointer+1, end);
    }

  }

  public static void main(String[] args) {

    final int  NO_OF_ELEMENT = 10000000;
    Random random = new Random();

    int [] myArray = new int [NO_OF_ELEMENT];
    for (int i=0; i< NO_OF_ELEMENT ;i++){
      myArray[i] = random.nextInt(NO_OF_ELEMENT );
    } 

    QuickSort quickSort = new QuickSort();
   // int [] myArray = {2,8,3,9,8,2,3,2,4,3,4,5,3,4,5,8};
    long startTime = System.currentTimeMillis();
    quickSort.sort(myArray, 0, myArray.length-1);
    System.out.println("Time taken " + (System.currentTimeMillis() - startTime));

    for (int i=myArray.length-1000; i<myArray.length; i++){
      System.out.println(" element at " + i + " : " + myArray[i]  );
    }

  }

}