Quick sort

Quick sort or Hoar sort is one of the fastest data sorting algorithms.

The Hoar Algorithm is a modified version of the direct exchange method. Other popular variations of this method - bubble sort and shaker sort , unlike quick sort, are not very effective.

The principle of operation of the quick sort algorithm

The idea of ​​the algorithm is as follows:

  • It is necessary to choose a supporting element of the array, it can be any element, the correctness of the algorithm does not depend on this;
  • Divide the array into three parts, the first should include elements less than reference, the second - equal to the reference and the third - all elements are larger than the reference;
  • The previous steps are performed recursively, for subarrays with smaller and larger values, as long as they contain more than one element.

Since the quick sort method divides the array into parts, it belongs to the group of algorithms divide and conquer.

Implement quick sort

using System;

class program
{
    // method for exchanging array elements
    static void Swap(ref int x, ref int y)
    {
        var t = x;
        x = y;
        y = t;
    }

    // method returns the index of the reference element
    static int Partition(int[] array, int minIndex, int maxIndex)
    {
        var pivot = minIndex - 1;
        for (var i = minIndex; i < maxIndex; i++)
        {
            if (array[i] < array[maxIndex])
            {
                pivot++;
                Swap(ref array[pivot], ref array[i]);
            }
        }

        pivot++;
        Swap(ref array[pivot], ref array[maxIndex]);
        return pivot;
    }

    // quick sort
    static int[] QuickSort(int[] array, int minIndex, int maxIndex)
    {
        if (minIndex >= maxIndex)
        {
            return array;
        }

        var pivotIndex = Partition(array, minIndex, maxIndex);
        QuickSort(array, minIndex, pivotIndex - 1);
        QuickSort(array, pivotIndex + 1, maxIndex);

        return array;
    }

    static int[] QuickSort(int[] array)
    {
        return QuickSort(array, 0, array.Length - 1);
    }

    static void Main(string[] args)
    {
        Console.Write("N =");
        var len = Convert.ToInt32(Console.ReadLine());
        var a = new int[len];
        for (var i = 0; i < a.Length; ++i)
        {
            Console.Write("a [{0}] =", i);
            a[i] = Convert.ToInt32(Console.ReadLine());
        }

        Console.WriteLine("Ordered array: {0}", string.Join(",", QuickSort(a)));

        Console.ReadLine();
    }
}

The Partition method returns the index of the reference element, which divides the array into elements smaller than the reference on the left, and elements larger than the reference on the right. In the method itself, the last element is selected as a reference, and traversal is carried out from the beginning of the array.

The result of the program:

Related pages: