Caută
  • oanaunciuleanu

Quick Sort Algorithm in C++



Quick sort is a recursive sorting algorithm. It uses the idea of divide et conquer. To solve the array, we have to choose a pivot, which is approximately in the middle of the array. We must find an element that is greater than the pivot, and one that is smaller and swap them to be in order. We find other values with the same properties until the pivot is in its place. We recursively apply the same method to solve the order for other values and pivots, applying Quick sort for the left part and then for the right part of the array.


// Quick Sort

#include <iostream>
using namespace std;

int partitionArray(int *arrayOfNumbers, int startIndex,int lastIndex)
{
    int pivotValue = arrayOfNumbers[lastIndex];
    int pivotIndex = startIndex;
    int temporary;

    // Check if value is smaller than pivot and swap if necessary
    for(int i = startIndex; i < lastIndex; i++)
    {
    	if(arrayOfNumbers[i] <= pivotValue)
        {
            temporary = arrayOfNumbers[i];
            arrayOfNumbers[i] = arrayOfNumbers[pivotIndex];
            arrayOfNumbers[pivotIndex] = temporary;
            pivotIndex++;
        }
     }

      // Swap the values of pivot and last value
      temporary = arrayOfNumbers[lastIndex];
      arrayOfNumbers[lastIndex] = arrayOfNumbers[pivotIndex];
      arrayOfNumbers[pivotIndex]= temporary;

     return pivotIndex;
 }

 void quickSort(int *arrayOfNumbers, int startIndex, int lastIndex)
 {
    if(startIndex < lastIndex)
    {
         int pivotIndex = partitionArray(arrayOfNumbers, startIndex, lastIndex);
             quickSort(arrayOfNumbers, startIndex, pivotIndex - 1);
             quickSort(arrayOfNumbers, pivotIndex + 1, lastIndex);
    }
}
void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
  for (int i = 0; i < numberOfElements; ++i)
  {
    cout << arrayOfNumbers[i] << " ";
  }
  cout << endl;
}

int main(void)
{
  int arrayOfNumbers[] = {4, 7, 9, 3, 21, 18, 23, 15, 8, 17};
  int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
  int startIndex = 0;
  int lastIndex = numberOfElements - 1;

  quickSort(arrayOfNumbers, startIndex, lastIndex);
  cout<<"The sorted array is: \n";
  printElementsOfArray(arrayOfNumbers, numberOfElements);
}

© 2018 by The Art Of Coding. by Oana Unciuleanu

This site was designed with the
.com
website builder. Create your website today.
Start Now