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(N^{2}) time complexity and also how to overcome it: http://igoro.com/archive/quicksort-killer/