Quick Sort

Implementation from [1]

// C++ implementation of QuickSort 
#include <bits/stdc++.h>
using namespace std;
// A utility function to swap two elements
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// This function takes last element as pivot, places
// the pivot element at its correct position in sorted
// array, and places all smaller (smaller than pivot)
// to left of pivot and all greater elements to right
// of pivot
int partition (int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p] is now
// at right place
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver Code
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
// This code is contributed by rathbhupendra

My own implementation

#include <iostream>
#include <vector>
using namespace std;
void quicksort(vector<int>& a, int i, int j) {
if (i >= j || i < 0 || j >= a.size()) return;
// pick up the first element as pivot
int pivot = a[i], pivot_idx = i + 1;
for (int k = i + 1; k <= j; ++k) {
if (a[k] <= pivot) {
swap(a[k], a[pivot_idx++]);
}
}
pivot_idx--;
swap(a[i], a[pivot_idx]);
quicksort(a, i, pivot_idx - 1);
quicksort(a, pivot_idx + 1, j);
}
int main() {
vector<int> a = {10, 6, 7, 8, 9, 0, 6};
cout << "Before sorting:" << endl;
for (auto x : a) cout << x <<" ";
cout << endl;
quicksort(a, 0, a.size() - 1);
cout << "After sorting:" << endl;
for (auto x : a) cout << x <<" ";
cout << endl;

}

Reference

[1] https://www.geeksforgeeks.org/quick-sort/

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Welcome Chris Jacobs to the Origin Engineering Team!

Domain-driven event sourcing with Akka Typed

App Academy W5D5

OET Reading and Listening tips

How do I manage a dependency inherited from a parent POM in the child POM : Log4j example?

Swift Optionals – Day 9

Communication in Team During the Project: Why It’s Important and Worth Your Money

Building a GraphQL API using Firebase Functions and Apollo

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Function Execution Context

Journey of DLithe Bootcamp Java Full Stack Developer | Week 7(May2-May 8)

BACKTRACKING ALGORITHM

Dependency Injection & Inversion of Control