Visual C++ - Sorting Algorithm - Quick Sort Iterative
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 in iterative mode.
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.
The iteration approach requires stacking of the beg(left), end(right) positions that are used in recursion. I have used the vector to store the values and made sure the loop is getting repeated until vector is empty.
Click here for Bubble Sort Algorithm
Click here for insertion Sort Algorithm
Click here for Merge Sort Algorithm
Click here for Merge Sort Iterative Algorithm
Click here for Quick Sort Algorithm
Click here for Quick Sort Iterative Algorithm
The complete program and test run output are given below:
Source Code
#include <iostream>
#include <queue>
#include <vector>
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_Recursive(int *arr, int left, int right)
{
// For Recusrion
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_Recursive(arr, left, pivot - 1);
if(pivot + 1 < right)
QuickSort_Recursive(arr, pivot + 1, right);
}
}
void QuickSort_Iterative(int *arr, int left, int right)
{
if(left >= right)
return; // Invalid index range
std::vector<std::pair<int, int> > list;
int srcleft = left;
int srcright = right;
list.push_back(std::pair<int, int>(left, right));
while(1)
{
if(list.size() == 0)
break;
left = list.back().first;
right = list.back().second;
list.pop_back();
int pivot = Partition(arr, left, right);
std::pair<int,int> p;
if(pivot > 1)
list.push_back(std::pair<int, int>(left, pivot - 1));
if(pivot + 1 < right)
list.push_back(std::pair<int, int>(pivot + 1, right));
}
}
void QuickSortHelper(int *arr, int len)
{
//QuickSort_Recursive(arr, 0, len - 1);
QuickSort_Iterative(arr, 0, len - 1);
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[] = { 3, 8, 7, 5, 2, 1, 9, 6, 4 };
int len = sizeof(arr) / sizeof(arr[0]);
QuickSortHelper(arr, len);
for(int i = 0; i < len; i++)
std::cout << arr[i] << " ";
return 0;
}
Output
1 2 3 4 5 6 7 8 9
|
|