This is a short You Tube video I made last month, to visualize the Quick Sort sorting algorithm. As you all know this is one of the most efficient algorithms for sorting data. There are many implementations of that algorithm so this is just one of them.

The basic idea of quicksort is to choose one element that we call pivot, and to place all the elements lower that the pivot on the left side and all the elements higher than the pivot on the right side. This way the pivot is placed on the right place and we repeat the same procedure for the two remaining sub lists and so on recursively until we have the entire list sorted.

Here is a short C# code snippet of this specific implementation:

 
public static void QuickSort(List<string> list, int left, int right){
  int initial_left = left;
  int initial_right = right;
  string pivotValue = list[initial_left];
  
  while(left < right){
    while(String.Compare(list[right], pivotValue) >= 0 && (left < right)){
      right--;
    }
    if(left != right){
      list[left] = list[right];
      left++;
    }
    while(String.Compare(list[left], pivotValue) <= 0 && (left < right)){
      left++;
    }
    if(left != right){
      list[right] = list[left];
      right--;
    }
  }
  
  list[left] = pivotValue;
  int pivotIndex = left;
        
  if((pivotIndex - 1) > initial_left)        QuickSort(list, initial_left,    pivotIndex - 1);
  if((pivotIndex + 1) < initial_right)    QuickSort(list, pivotIndex + 1,    initial_right);
}

And at the end I would like to point to an interesting article from Igor Ostrovsky describing how this algorithm in some cases may degrade to O(N2) time complexity and also how to overcome it: http://igoro.com/archive/quicksort-killer/

Share this post:   digg     Stumble Upon     del.icio.us     E-mail

IFRA
Posted on 1/26/2010 12:15:24 PM

excellent approach to convey a lesson to others.....thanks

prabha ramanathan
Posted on 3/3/2010 8:13:47 PM

This video and explanation is excellent!!!!

Prabha

trinitry
Posted on 1/15/2011 2:03:36 PM

This video was quite good .. very good explanation. Thanks!

Please post your comments:

Name:  
Email (optional): Your email address will not be posted.
Comments: HTML will be ignored, URLs will be converted to hyperlinks  
Enter the text you see in the box: