quick sort c++

Similar đồ sộ the Merge Sort algorithm, the Quick Sort algorithm is a Divide and Conquer algorithm. It initially selects an element as a pivot element and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. 

  1. Always pick the first element as a pivot (implemented below).
  2. Always pick the last element as the pivot.
  3. Pick a random element as a pivot.
  4. Pick median as a pivot.

The key process in quickSort is the partition() process. The aim of the partition() function is đồ sộ receive an array and an element x of the array as a pivot, put x at its correct position in a sorted array and then put all smaller elements (smaller than thở x) before x, and put all greater elements (greater than thở x) after x. All this should be done in linear time i.e.  Big O(n) .
Pseudo Code for recursive QuickSort function : 

Bạn đang xem: quick sort c++

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

Method-1 : 

CPP

#include <iostream>

using namespace std;

int partition(int arr[], int start, int end)

{

    int pivot = arr[start];

    int count = 0;

    for (int i = start + 1; i <= end; i++) {

        if (arr[i] <= pivot)

            count++;

    }

    int pivotIndex = start + count;

    swap(arr[pivotIndex], arr[start]);

    int i = start, j = end;

    while (i < pivotIndex && j > pivotIndex) {

        while (arr[i] <= pivot) {

            i++;

        }

        while (arr[j] > pivot) {

            j--;

        }

        if (i < pivotIndex && j > pivotIndex) {

            swap(arr[i++], arr[j--]);

        }

    }

    return pivotIndex;

}

void quickSort(int arr[], int start, int end)

{

    if (start >= end)

        return;

    int p = partition(arr, start, end);

    quickSort(arr, start, p - 1);

    quickSort(arr, p + 1, end);

}

int main()

{

    int arr[] = { 9, 3, 4, 2, 1, 8 };

    int n = 6;

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {

        cout << arr[i] << " ";

    }

    return 0;

}

Method-2 :

This method’s space complexity is O(n). As we will take an extra array in partition function lượt thích in merge function of merge sort. 

Algorithm explanation and steps of partition function: 

  • Make a new array of size equal đồ sộ given array.
  • push all the smaller elements than thở pivotElement đồ sộ the new array.
  • Push pivotElement đồ sộ new array now.
  • finally, push all the greater elements than thở pivotElement đồ sộ the new array.
  • Now, copy the new array đồ sộ the original array.
  • Store the index of the pivotElement from the original array. Return this index.

After this, all the elements in the original array are in the order : smaller than thở pivotElement -> pivotElement -> greater than thở pivotElement.

Time Complexity : θ(nlogn).

Space Complexity : O(n).

C++

#include <iostream>

using namespace std;

int partition(int* arr, int start, int end)

{  

    int index = 0, pivotElement = arr[end], pivotIndex;

    int* temp = new int[end - start + 1];

    for (int i = start; i <= end; i++)

    {

        if(arr[i] < pivotElement)

        {

Xem thêm: cách trị kiến trong nhà

            temp[index] = arr[i];

            index++;

        }

    }

    temp[index] = pivotElement;

    index++;

    for (int i = start; i < end; i++)

    {

        if(arr[i] > pivotElement)

        {

            temp[index] = arr[i];

            index++;

        }

    }

    index = 0;

    for (int i = start; i <= end; i++)

    {  

        if(arr[i] == pivotElement)

        {

            pivotIndex = i;

        }

        arr[i] = temp[index];

        index++;

    }

    return pivotIndex;

}

void quickSort(int* arr, int start, int end)

    if(start < end)

    {  

        int partitionIndex = partition(arr, start, end);

        quickSort(arr, start, partitionIndex - 1);

        quickSort(arr, partitionIndex + 1, end);

    }

    return;

}

int main()

{   

    int size = 9;

    int arr[size] = {5, 12, 7, 1, 13, 2 ,23, 11, 18};

      cout << "Unsorted array : ";

    for (int i = 0; i < size; i++)

    {

        cout << arr[i] << " ";

    }

    printf("\n");

    quickSort(arr, 0, size - 1);

      cout << "Sorted array : ";

    for (int i = 0; i < size; i++)

    {

       cout << arr[i] << " ";

    }

      return 0;

}

Output

Unsorted array : 5 12 7 1 13 2 23 11 18 
Sorted array : 1 2 5 7 11 12 13 18 23 

Please refer complete article on QuickSort for more details!

Xem thêm: 1 cây vàng giá bao nhiêu


Last Updated : 21 Dec, 2022

Like Article

Save Article