Quicksort is a popular and powerful sorting algorithm that is used in a variety of situations. It is one of the most efficient sorting algorithms, and is the algorithm of choice for most applications. In this article, we will discuss the details of quicksort in C++, including how it works, its time and space complexities, and how to implement it in C++. We will also provide some coding exercises so that you can test your understanding of quicksort.
What is Quicksort?
Quicksort is an efficient sorting algorithm that works by taking an unsorted list of elements and recursively dividing it into smaller lists until each list is sorted. It works by selecting a pivot element from the list, and then using that pivot to partition the list into two separate lists: one containing elements that are less than the pivot, and the other containing elements that are greater than the pivot. The quicksort algorithm then continues to recursively sort each sub-list until all elements in the list are sorted.
How Does Quicksort Work?
Quicksort is a recursive algorithm, meaning that it works by breaking down a problem into smaller sub-problems and then solving those sub-problems. The quicksort algorithm works by first selecting a pivot element from the list to be sorted. This pivot element is typically chosen as the first element of the list. The quicksort algorithm then partitions the list into two sub-lists, one containing elements that are less than the pivot, and the other containing elements that are greater than the pivot. The quicksort algorithm then recursively sorts each sub-list until all elements in the list are sorted.
Quicksort in C++
Now that we have discussed how the quicksort algorithm works, let’s look at how to implement it in C++. The following C++ code demonstrates how to implement quicksort in C++:
// Function to implement quicksort in C++
void quicksort(int arr[], int left, int right)
{
// Create an index for our pivot element
int i = left, j = right;
// Select the first element in the array as the pivot element
int pivot = arr[left];
// Create a while loop to iterate through the array and partition it
while (i <= j)
{
// Iterate through the array until we find an element that is greater than the pivot
while (arr[i] < pivot)
i++;
// Iterate through the array until we find an element that is less than the pivot
while (arr[j] > pivot)
j--;
// If the two elements are not in the correct order, swap them
if (i <= j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// Recursively call the quicksort function on the left and right sub-arrays
if (left < j)
quicksort(arr, left, j);
if (i < right)
quicksort(arr, i, right);
}
Time Complexity of Quicksort
The time complexity of quicksort is dependent on the selection of the pivot element. In the best case scenario, the pivot element is chosen such that the list is partitioned into two equal halves each time. This results in a time complexity of Ο(n log n). In the worst case scenario, the pivot element is chosen such that the list is partitioned into one half with all elements greater than the pivot, and one half with all elements less than the pivot. This results in a time complexity of Ο(n2). On average, the time complexity of quicksort is Ο(n log n).
Space Complexity of Quicksort
The space complexity of quicksort is Ο(log n). This is because the quicksort algorithm only requires space for the recursive calls and the temporary variables used to swap elements.
Conclusion
In conclusion, quicksort is an efficient sorting algorithm that works by recursively dividing an unsorted list into two sub-lists and then sorting each sub-list. It is one of the most efficient sorting algorithms, with a time complexity of Ο(n log n) in the best case and Ο(n2) in the worst case. The space complexity of quicksort is Ο(log n). The quicksort algorithm can be easily implemented in C++ using the code provided in this article.
Exercises
Write a quicksort algorithm that sorts an array of integers in descending order.
// Function to implement quicksort in C++
void quicksort(int arr[], int left, int right)
{
// Create an index for our pivot element
int i = left, j = right;
// Select the first element in the array as the pivot element
int pivot = arr[left];
// Create a while loop to iterate through the array and partition it
while (i <= j)
{
// Iterate through the array until we find an element that is less than the pivot
while (arr[i] > pivot)
i++;
// Iterate through the array until we find an element that is greater than the pivot
while (arr[j] < pivot)
j--;
// If the two elements are not in the correct order, swap them
if (i <= j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// Recursively call the quicksort function on the left and right sub-arrays
if (left < j)
quicksort(arr, left, j);
if (i < right)
quicksort(arr, i, right);
}
Write a quicksort algorithm that sorts an array of strings in alphabetical order.
// Function to implement quicksort in C++
void quicksort(string arr[], int left, int right)
{
// Create an index for our pivot element
int i = left, j = right;
// Select the first element in the array as the pivot element
string pivot = arr[left];
// Create a while loop to iterate through the array and partition it
while (i <= j)
{
// Iterate through the array until we find an element that is lexicographically greater than the pivot
while (arr[i].compare(pivot) < 0)
i++;
// Iterate through the array until we find an element that is lexicographically less than the pivot
while (arr[j].compare(pivot) > 0)
j--;
// If the two elements are not in the correct order, swap them
if (i <= j)
{
string temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// Recursively call the quicksort function on the left and right sub-arrays
if (left < j)
quicksort(arr, left, j);
if (i < right)
quicksort(arr, i, right);
}
Given an array of integers, write a quicksort algorithm that sorts the array in ascending order and also prints out the sorted array.
#include <iostream>
using namespace std;
// Function to implement quicksort in C++
void quicksort(int arr[], int left, int right)
{
// Create an index for our pivot element
int i = left, j = right;
// Select the first element in the array as the pivot element
int pivot = arr[left];
// Create a while loop to iterate through the array and partition it
while (i <= j)
{
// Iterate through the array until we find an element that is greater than the pivot
while (arr[i] < pivot)
i++;
// Iterate through the array until we find an element that is less than the pivot
while (arr[j] > pivot)
j--;
// If the two elements are not in the correct order, swap them
if (i <= j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// Recursively call the quicksort function on the left and right sub-arrays
if (left < j)
quicksort(arr, left, j);
if (i < right)
quicksort(arr, i, right);
}
// Function to print the sorted array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Main function
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;
}
Write a quicksort algorithm that takes an array of integers and sorts it in descending order. The algorithm should also print out the sorted array.
#include <iostream>
using namespace std;
// Function to implement quicksort in C++
void quicksort(int arr[], int left, int right)
{
// Create an index for our pivot element
int i = left, j = right;
// Select the first element in the array as the pivot element
int pivot = arr[left];
// Create a while loop to iterate through the array and partition it
while (i <= j)
{
// Iterate through the array until we find an element that is less than the pivot
while (arr[i] > pivot)
i++;
// Iterate through the array until we find an element that is greater than the pivot
while (arr[j] < pivot)
j--;
// If the two elements are not in the correct order, swap them
if (i <= j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// Recursively call the quicksort function on the left and right sub-arrays
if (left < j)
quicksort(arr, left, j);
if (i < right)
quicksort(arr, i, right);
}
// Function to print the sorted array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Main function
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 in descending order: \n";
printArray(arr, n);
return 0;
}
Write a program to calculate the factorial of a given number using recursion in C++.
#include <iostream>
using namespace std;
// Function to calculate the factorial of a given number using recursion
int factorial(int n)
{
// Base case
if (n == 0)
return 1;
// Recursive case
return n * factorial(n - 1);
}
// Main function
int main()
{
int num;
cout << "Enter a number: ";
cin >> num;
int result = factorial(num);
cout << "The factorial of " << num << " is " << result << endl;
return 0;
}