Explore-open-source/QuickSort.cpp at main · coder2hacker/Explore-open-source · GitHub

History

71 lines (51 loc) · 1.1 KB

Raw

// C++ Implementation of the Quick Sort Algorithm.

#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++;

}

// Giving pivot element its correct position

int pivotIndex = start + count;

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

// Sorting left and right parts of the pivot element

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)

{

// base case

if (start >= end)

return;

// partitioning the array

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

// Sorting the left part

quickSort(arr, start, p - 1);

// Sorting the right part

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;

}

Explore-open-source/QuickSort.cpp at main · coder2hacker/Explore-open-source · GitHub

Uh oh!

Expand file tree

Breadcrumbs

QuickSort.cpp

Latest commit

History

Breadcrumbs

QuickSort.cpp

File metadata and controls