Quick sort is one of the fastest sorting algorithms. This algorithm belongs to partitioning category of sorting algorithms.

How Quick sort works:

We can make this algorithm recursively. In this algorithm first of all we have to find the pivot. What is pivot? We can select pivot any number in the array but normally it is selected from start, mid or end. If we consider a sorted array it means that every element has a specific location in the array so the array gets sort. Using this concept we find the actual location of pivot in the array. When first time we fined it than we divides the array in two parts and again get pivot in each array and place them at their actual places. We continue this process till the one element remains in new array after dividing. We divined every part in more two parts. Next question is how we find pivot? For this purpose we use two pointers (I, j) one (I) points at the first location and other points (J) at last location of array. We check if pivot is greater or equal to the element where ‘I’ is pointing than we do increment in ‘I’ and if pivot is less than element where J is pointing than we do decrement in J. we do this process till ‘I’ and J does not come at same location. If the situation is come that neither ‘I’ increases or nor J decreases, at this point we swap the elements where ‘I’ and J are pointing. This situation is called dead lock. The point where J is equal to ‘I’ that is actual location of pivot. Swap that element with pivot. At the end the array will be sorted.

Complexity of Quick Sort Algorithm:

This algorithm takes n log n time in its average case. So we can say that its complexity is BIG O of n log n. and it takes N Square in worst case.

To demonstrate this make a window form based application. Drag one button and one list box on the form. Load an integer array in the list box and than press button to sort.

Now write the following code on Button Click event:

C#

private void btn_Sort_Click(object sender, EventArgs e)

        {

           QuickSort(0,4);

            listBox_elements.Items.Clear();

            for (int x = 0; x < arr.Length; x++)

                listBox_elements.Items.Insert(x, arr.GetValue(x));

        }

VB

Private Sub btn_Sort_Click(ByVal sender As Object, ByVal e As EventArgs)

        QuickSort(0,4);

        listBox_elements.Items.Clear()

        For x As Integer = 0 To arr.Length - 1

            listBox_elements.Items.Insert(x, arr.GetValue(x))

        Next

    End Sub

This is a simple code to call Quick Sort () Function. After sorting, this code will load the sorted array in list box.

Now write the following code in Quick Sort () Function:

C#

private void QuickSort(int left, int right)

        {

            int i = left, j = right;

            int temp;

            int pivot = (int)arr.GetValue(Pivot(right, left));

            while (i <= j)

            {

                while ((int)arr.GetValue(i) < pivot)

                    i++;

                while ((int)arr.GetValue(j) > pivot)

                    j--;

                if (i <= j)

                {

                    temp =(int) arr.GetValue(i);

                    arr.SetValue(arr.GetValue(j), i);

                    arr.SetValue(temp, j);

                    i++;

                    j--;

                }

            }

            if (left < j)

                QuickSort(left, j);

            if (i < right)

                QuickSort(i, right);

        }

VB

Private Sub QuickSort(ByVal left As Integer, ByVal right As Integer)

        Dim i As Integer = left, j As Integer = right

        Dim temp As Integer

        Dim pivot__1 As Integer = CInt(arr.GetValue(Pivot(right, left)))

        While i <= j

            While CInt(arr.GetValue(i)) < pivot__1

                i += 1

            End While

            While CInt(arr.GetValue(j)) > pivot__1

                j -= 1

            End While

            If i <= j Then

                temp = CInt(arr.GetValue(i))

                arr.SetValue(arr.GetValue(j), i)

                arr.SetValue(temp, j)

                i += 1

                j -= 1

            End If

        End While

        If left < j Then

            QuickSort(left, j)

        End If

        If i < right Then

            QuickSort(i, right)

        End If

    End Sub

I made a function to take mid element of array as a pivot. Now write the body of function Pivot ().

Now write the following code in Pivot () Function:

C#

private int Pivot(int left, int right)

        {

            return (left + right) / 2;

        }

VB

Private Function Pivot(ByVal left As Integer, ByVal right As Integer) As Integer

        Return (left + right) / 2

    End Function

This is simple code to sort.

Now write the following code on FORM LOAD event:

C#

  private void Form1_Load(object sender, EventArgs e)

        {                 

            arr.SetValue(8, 0);

            arr.SetValue(9,1);

            arr.SetValue(2, 2);

            arr.SetValue(4, 3);

            arr.SetValue(7, 4);

            for (int i = 0; i < arr.Length; i++)

                listBox_elements.Items.Insert(i, arr.GetValue(i));

            this.Text = "DEVASP QUICK SORT APPLICATION";

        }

VB

Private Sub Form1_Load(ByVal sender As Object, ByVal e As EventArgs)

        Me.Text = "DEVASP QUICK SORT APPLICATION"

        arr.SetValue(8, 0)

        arr.SetValue(9, 1)

        arr.SetValue(2, 2)

        arr.SetValue(4, 3)

        arr.SetValue(7, 4)

        For i As Integer = 0 To arr.Length - 1

            listBox_elements.Items.Insert(i, arr.GetValue(i))

        Next

    End Sub

This simple article tells how to do sorting using Quick sort in VB and C# .net 2.0.