A simple program quick sort in C++ program that I wrote while I am learning C++ programming.
My email address is jakerpomperada@gmail.com and jakerpomperada@yahoo.com
Program Listing
// quick_sort.cpp
// Prof. Jake R. Pomperada, MAED-IT, MIT
// www.jakerpomperada.com / www.jakerpomperada.blogspot.com
// jakerpomperada@gmail.com
// Bacolod City, Negros Occidental Philippines
#include <iostream>
#include <cstdlib>
using namespace std;
void swap_numbers(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int Partition(int a[], int low, int high)
{
int pivot, index, i;
index = low;
pivot = high;
for(i=low; i < high; i++)
{
if(a[i] < a[pivot])
{
swap_numbers(&a[i], &a[index]);
index++;
}
}
swap_numbers(&a[pivot], &a[index]);
return index;
}
int RandomPivotPartition(int a[], int low, int high)
{
int pvt, n, temp;
n = rand();
pvt = low + n%(high-low+1);
swap_numbers(&a[high], &a[pvt]);
return Partition(a, low, high);
}
int QuickSort(int a[], int low, int high)
{
int pindex;
if(low < high)
{
pindex = RandomPivotPartition(a, low, high);
QuickSort(a, low, pindex-1);
QuickSort(a, pindex+1, high);
}
return 0;
}
int main()
{
int n=0, i=0;
cout <<"\n";
cout <<"\t\tQuick Sort in C++";
cout <<"\n\n";
cout<<"\tHow many items to be sorted? ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++)
{
cout<<"\tEnter item no. "<<i+1<<": ";
cin>>arr[i];
}
cout <<"\n";
cout<<"\tUnSorted Items\n ";
cout <<"\n";
cout <<"\t";
for (i =0; i < n; i++) {
cout<<" ,"<<arr[i];
}
cout <<"\n";
QuickSort(arr, 0, n-1);
cout <<"\n\n";
cout<<"\tSorted Item \n";
cout <<"\n";
cout <<"\t";
for (i = 0; i < n; i++) {
cout<<" ,"<<arr[i];
}
cout <<"\n\n";
cout <<"\tEnd of Program";
cout <<"\n";
}
No comments:
Post a Comment