Quick sort

Best Case: nlogn

Average Case: nlogn

Worst Case: n2

Stable: No

Quick sort is similar to merge sort making it a divide and conquer algorithm. You can make quick sort to choose its pivot point, like at the start or the end of the array. If the array is already sorted then you get the worst case scenario.

  • Pivot with first element
  • Pivot Last element
  • Pivot middle element
  • Pivot a random element

The following example makes use of thye last element to be the pivot but you can change to any pivot if you so with to.

C++/C example

   
//Swaps the values
void QuickSwap(int* x, int* y)
{
    int t = *x;
    *x = *y;
    *y = t;
}

//Grabs the last element and pivots it to the correct position in the sorted array
int QuickPartition (int A[], int low, int high) {

    int piv = A[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++)
    {
        //Checks if the current element is smaller or equal to the pivot point
        if (A[j] <= piv)
        {
            i++;
            QuickSwap(&A[i], &A[j]);
        }
    }
    QuickSwap(&A[i + 1], &A[high]);
    return (i + 1);
}

//Main function that implements the quick sort algorithm
void QuickSort(int A[], int low, int high)
{
    if (low < high)
    {
        //the partition for the index that is in the correct positiion
        int pi = QuickPartition(A, low, high);

        //sort the elements before the partition
        QuickSort(A, low, pi - 1);
        //Sorts it after the partition
        QuickSort(A, pi + 1, high);
    }
}

int main()
{
    double random;

    //create an empty array with 100 elements
    int A[100000];

    //creating random number generator
    srand (time(NULL));

    //get the size of array
    int size = (sizeof(A)/sizeof(A[0]));

    //loops through and inserts into array with a random int between 1-1000
    for (int i = 0; i < size; i++)
    {
        random = rand() % 10001 + 0;
        A[i] = random;
    }

    //begin sorting
    QuickSort(A, 0, size-1);

    //print through sorted array
    for (int i = 0; i < size; i++)
    {
        std::cout << A[i] << std::endl;
    }

    return 0;
}
                

Summary

Fast algorithm and requires very little code and is easy to implement only downside is that it can be inefficient if the data is already sorted.