Visual C++ - Sorting Algorithm - Quick Sort Recursive
We often using sorting algorithm to sort numbers and strings. Also we have many sorting algorithms. I have explained here on how quick sort algorithm works.
The recusrive approach requires creatiion multi branch recursion by dividing the number of elements by two. For each time when partition method is called, the pivot is placed at the correct position meaning all the elements to the left are less than the pivot value and all the elements to right are greater than the pivot value.
Click here for C++ Bubble Sort Algorithm
Click here for C++ insertion Sort Algorithm
Click here for C++ Merge Sort Recursive Algorithm
Click here for C++ Merge Sort Iterative Algorithm
Click here for C++ Quick Sort Recursive Algorithm
Click here for C++ Quick Sort Iterative Algorithm
The complete program and test run output are given below:
Source Code
#include <iostream>
#include <string>
int Partition(int a[], int left, int right)
{
int pivot = a[left];
while (true)
{
while (a[left] < pivot)
left++;
while (a[right] > pivot)
right--;
if (left < right)
{
int temp = a[right];
a[right] = a[left];
a[left] = temp;
}
else
{
return right;
}
}
}
void QuickSort(int *arr, int left, int right)
{
if(left < right)
{
int pivot = Partition(arr, left, right);
//for(int i = 0; i < 9; i++)
// std::cout << arr[i] << " ";
// std::cout << "\n";
if(pivot > 1)
QuickSort(arr, left, pivot - 1);
if(pivot + 1 < right)
QuickSort(arr, pivot + 1, right);
}
}
void QuickSort(int *arr, int len)
{
QuickSort(arr, 0, len - 1);
}
void main()
{
int max;
std::cout << "\nProgram for Ascending order of Numeric Values using QUICK SORT";
std::cout << "\n\nEnter the total number of elements: ";
std::cin >> max;
int *numarray = new int[max];
for(int i = 0; i < max; i++)
{
std::cout << "\nEnter [" << i + 1 << "] element: ";
std::cin >> numarray[i];
}
std::cout << "Before Sorting : ";
for(int k = 0; k < max; k++)
std::cout << numarray[k] << " ";
std::cout << "\n";
QuickSort(numarray,max);
std::cout << "\n\nThe numbers in ascending orders are given below:\n\n";
for(int i = 0; i < max; i++)
{
std::cout << "Sorted [" << i + 1 << "] element: ";
std::cout << numarray[i];
std::cout << "\n";
}
delete [] numarray;
}
Output
Program for Ascending order of Numeric Values using QUICK SORT
Enter the total number of elements: 8
Enter [1] element: 80
Enter [2] element: 60
Enter [3] element: 40
Enter [4] element: 20
Enter [5] element: 10
Enter [6] element: 30
Enter [7] element: 50
Enter [8] element: 70
The numbers in ascending orders are given below:
Sorted [1] element: 10
Sorted [2] element: 20
Sorted [3] element: 30
Sorted [4] element: 40
Sorted [5] element: 50
Sorted [6] element: 60
Sorted [7] element: 70
Sorted [8] element: 80
|
|