🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In this blog post, we will learn how to write a C++ program to sort an array of integers in Ascending Order using the Quick Sort algorithm.
Quick Sort is a 'divide and conquer' algorithm. The primary concept behind Quick Sort is to pick a 'pivot' element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.
2. Program Overview
1. partition(): Function that takes an element as a pivot, places the pivot at its correct position, and places all elements smaller to the left and all greater elements to the right.
2. quickSort(): The main recursive function that implements QuickSort.
3. printArray(): Utility function to display the array's elements.
4. main(): The main function that starts the program.
3. Code Program
#include<iostream>
using namespace std;
// This function takes last element as pivot, places it at its correct position,
// and places all smaller (smaller than pivot) to the left and all greater elements to the right
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
// Main function that sorts arr[low..high] using quickSort
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Utility function to print the array
void printArray(int arr[], int size) {
for (int 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]);
cout << "Original array is: \n";
printArray(arr, n);
quickSort(arr, 0, n - 1);
cout << "Sorted array in ascending order is: \n";
printArray(arr, n);
return 0;
}
Output:
Original array is: 10 7 8 9 1 5 Sorted array in ascending order is: 1 5 7 8 9 10
4. Step By Step Explanation
1. partition(): The goal of this function is to select a pivot, in this case, the last element of the array, and to place it in the right position such that all numbers less than the pivot are on the left and all numbers greater than the pivot are on the right. This function returns the index of the pivot element.
2. quickSort(): This is the main function that recursively sorts the elements of the array. Based on the index returned from the partition, it recursively sorts the left and right segments of the array.
3. printArray(): A utility function to display the array elements. This helps visualize the array before and after sorting.
4. main(): This function initializes a sample array, displays its elements, calls the quickSort function to sort the array, and then displays the sorted elements.
The partition() function is the essence of the Quick Sort. The choice of pivot and the partition logic are critical to the efficiency of the Quick Sort algorithm.
Related C++ Programs on Sorting Algorithms
- Bubble Sort in Ascending Order in C++
- Bubble Sort in Descending Order in C++
- Selection Sort in Ascending Order in C++
- Selection Sort in Descending Order in C++
- Insertion Sort in Ascending Order in C++
- Insertion Sort in Descending Order in C++
- Merge Sort in Ascending Order in C++
- Merge Sort in Descending Order in C++
- Quick Sort in Ascending Order in C++
- Quick Sort in Descending Order in C++
- Heap Sort in Ascending Order in C++
- Heap Sort in Descending Order in C++
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment