Back to Course

Data Structures and Algorithms with C++

0% Complete
0/0 Steps
  1. Introduction to Data Structures and Algorithms
    Overview of Data Structures and Algorithms with C++
  2. Importance of Data Structures and Algorithms in Programming with C++
  3. How to Choose the Right Data Structure or Algorithm for a given Problem with C++
  4. Basic C++ Concepts Review
    Variables and Data Types in C++
  5. Control Flow Statements in C++
  6. Classes and Objects in C++
  7. Methods and Constructors in C++
  8. Basic Input and Output in C++
  9. Data Structures
    Arrays in C++
  10. Stacks and Queues in C++
  11. Linked Lists in C++
  12. Hash Tables in C++
  13. Trees in C++
  14. Types of Trees
    Binary Search Trees in C++
  15. Cartesian Trees in C++
  16. B-Trees in C++
  17. Red-Black Trees in C++
  18. Splay Trees in C++
  19. AVL Trees in C++
  20. KD Trees in C++
  21. Min Heap in C++
  22. Max Heap in C++
  23. Trie Trees in C++
  24. Suffix Trees in C++
  25. Sorting Algorithms
    Quicksort in C++
  26. Mergesort in C++
  27. Timsort in C++
  28. Heapsort in C++
  29. Bubble Sort in C++
  30. Insertion Sort in C++
  31. Selection Sort in C++
  32. Tree Sort in C++
  33. Shell Sort in C++
  34. Bucket Sort in C++
  35. Radix Sort in C++
  36. Counting Sort in C++
  37. Cubesort in C++
  38. Searching Algorithms
    Linear Search in C++
  39. Binary Search in C++
  40. Graphing Algorithms
    Breadth First Search (BFS) in C++
  41. Depth First Search (DFS) in C++
  42. Dijkstra’s Algorithm in C++
  43. Algorithm Design Techniques
    Greedy Algorithms in C++
  44. Dynamic Programming in C++
  45. Divide and Conquer in C++
  46. Backtracking in C++
  47. Randomized Algorithms in C++
  48. Conclusion
    Recap of DSA with C++

Participants 445

Show more

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; 
}