1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

QuickSort in C#

Discussion in 'C#' started by Smoke6969, Jan 6, 2011.

  1. Smoke6969

    Smoke6969 New Member

    Joined:
    Dec 30, 2010
    Messages:
    2
    Likes Received:
    1
    Trophy Points:
    0
    A few days ago I had an interview on a c# programmer vacancy (already received a refuse letter :happy: ) On the interview I was asked to implement a QuickSort algorithm and I couldn't do that, so now I want to help you not to repeat my mistake and get the understanding of this algorithm before you'll need it.

    Simple Algorithm


    1. Pick an element from the list (usually the most left element is used). This element will serve as a pivot point
    2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). This is called the partition operation.
    3. Recursively repeat the algorithm for both halves of the original array.
    That's it. Pretty clear as I think.

    Pseudo Code



    Here is the Pseudo code for better understanding:

    Code:
    [B]function[/B] quicksort(array)
         [B]var[/B] [I]list[/I] less, greater
         [B]if[/B] length(array) ≤ 1
             [B]return[/B] array
         select and remove a pivot value[I] pivot[/I] from array
         [B]for each[/B] x [B]in[/B] array
             [B]if[/B] x ≤ pivot [B]then[/B] append x to less
             [B]else[/B] append x to greater
         [B]return[/B] concatenate(quicksort(less), pivot, quicksort(greater))

    C# Implementation



    That's enough for theory, here is my implementation of this in C#:

    Code:
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace sortQuick
    {
        class quickSort
        {
            // this is our array to sort
            private int[] arr = new int[20];
    
            // this holds a number of elements in array
            private int len;
    
            // Quick Sort Algorithm
            public void QuickSort()
            {
                sort(0, len - 1);
            }
    
            public void sort(int left, int right)
            {
                int pivot, l_holder, r_holder;
    
                l_holder = left;
                r_holder = right;
                pivot = arr[left];
    
                while (left < right)
                {
                    while ((arr[right] >= pivot) && (left < right))
                    {
                        right--;
                    }
    
                    if (left != right)
                    {
                        arr[left] = arr[right];
                        left++;
                    }
    
                    while ((arr[left] <= pivot) && (left < right))
                    {
                        left++;
                    }
    
                    if (left != right)
                    {
                        arr[right] = arr[left];
                        right--;
                    }
                }
    
                arr[left] = pivot;
                pivot = left;
                left = l_holder;
                right = r_holder;
    
                if (left < pivot)
                {
                    sort(left, pivot - 1);
                }
    
                if (right > pivot)
                {
                    sort(pivot + 1, right);
                }
            }
    
            public static void Main()
            {
                quickSort q_Sort = new quickSort();
    
                int[] arr = {4,3,1,4,6,7,5,4,3,5,6,87,8};
                q_Sort.arr = arr;
                q_Sort.len = q_Sort.arr.Length;
    
                // Sort the array
                q_Sort.QuickSort();
    
                for (int j = 0; j < q_Sort.len; j++)
                {
                    Console.WriteLine(q_Sort.arr[j]);
                }
                Console.ReadKey();
            }
        }
    }
    
    
     
    shabbir likes this.

Share This Page