This content originally appeared on DEV Community and was authored by Gustavo
In this post I'll show what I learned from the quicksort algorithm. I'll be sorting in ascending order an int array in C++.
The pivot
The quicksort algorithm is based on the pivot you choose. It can be the first, last, the middle or you can have other ways of choosing the pivot, like median-of-three.
Where the pivot is supposed to be
You should be asking where are we putting this pivot. Well, the pivot should abide by some rules so we know it is in its right place:
- It occupies the right sorted position on the given array.
- All items to the left are smaller
- All items to the right are bigger
The partition function
In this example, I'll be choosing the last element as the pivot.
In the function we call partition, we are going to find the right index where the pivot is supposed to be and return it to use in our quicksort function.
#include <iostream>
using namespace std;
const int ARR_SIZE = 7;
int partition(int arr[], int left, int right)
{
int pivot = arr[right]; // get the last element as pivot
int sortedIndex = left - 1;
for (int j = left; j < right; j++)
{
if (arr[j] < pivot)
{
sortedIndex++;
swap(arr[sortedIndex], arr[j]);
}
}
swap(arr[sortedIndex + 1], arr[right]);
return sortedIndex + 1;
}
-
sortedIndexwill store the previous index that the pivot will occupy at the end of the function - We iterate from
lefttoright. - If the element is smaller than the pivot, we add
+ 1tosortedIndexand swap the elementsarr[sortedIndex]andarr[j] - At the end of the function, we swap the pivot (last element) with the
sortedIndex + 1th element, and we return the new index of the pivot.
The Quick Sort recursive function
- In the quicksort function, we receive the array, the
leftand therightindex. -
Here we are basically getting the correct pivot position with the
partitionfunction and dividing the array in two:- from
lefttopivot - 1 - from
pivot + 1toright
- from
The stop criteria is when the function receives
leftequal or bigger thanright.And like that, we have our quicksort function:
void quicksort(int arr[], int left, int right)
{
if (left < right)
{
int pivot = partition(arr, left, right);
quicksort(arr, left, pivot - 1);
quicksort(arr, pivot + 1, right);
}
}
Final code
Let's use an array with 7 positions and sort it using the quicksort function:
#include <iostream>
using namespace std;
const int ARR_SIZE = 7;
int partition(int arr[], int left, int right)
{
int pivot = arr[right];
int sortedIndex = left - 1;
for (int j = left; j < right; j++)
{
if (arr[j] < pivot)
{
sortedIndex++;
swap(arr[sortedIndex], arr[j]);
}
}
swap(arr[sortedIndex + 1], arr[right]);
return sortedIndex + 1;
}
void quicksort(int arr[], int left, int right)
{
if (left < right)
{
int pivot = partition(arr, left, right);
quicksort(arr, left, pivot - 1);
quicksort(arr, pivot + 1, right);
}
}
int main()
{
int arr[ARR_SIZE] = {3, 7, 8, 4, 6, 2, 5};
cout << "\n-------------Original array-------------\n";
for (int i = 0; i < ARR_SIZE; i++)
{
cout << arr[i] << " ";
}
quicksort(arr, 0, ARR_SIZE - 1);
cout << "\n-------------Sorted array-------------\n";
for (int i = 0; i < ARR_SIZE; i++)
{
cout << arr[i] << " ";
}
return EXIT_SUCCESS;
}
Hope you could find it useful! If you have any advice, tips, recommendations or doubts, just ping me on Twitter
This content originally appeared on DEV Community and was authored by Gustavo
Gustavo | Sciencx (2023-03-07T13:52:37+00:00) Quick Sort Algorithm in C++. Retrieved from https://www.scien.cx/2023/03/07/quick-sort-algorithm-in-c/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.