// Program: quick_sort.cpp
// Author: Megh Thakkar
// Purpose: Sort an array of n elements in ascending order
// using the quick sort method
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream.h>
class sort {
private:
int *X; //List of data elements
int n; //Number of elements in the list
public:
sort (int size) { X = new int[n=size]; }
~sort( ) { delete [ ]X; }
void load_list (int input[ ] );
void show_list (char *title);
void quick_sort( int first, int last);
};
void sort::load_list(int input[ ])
{
for (int i = 0; i < n; i++)
X[i] = input[i];
}
void sort::show_list( char *title)
{
cout << "\n" << title;
for (int i = 0; i < n; i++)
cout << " " << X[i];
cout << "\n";
}
void sort::quick_sort( int first, int last)
{
//"temp" variable is temporary space used during swapping
int temp;
if (first < last)
{
//Start with the pivot as the first element in the list
int pivot = X[first];
//The variable "i" is used for scanning from the left.
int i = first;
//The variable "j" is used for scanning from the right.
int j = last;
while (i < j)
{
// Search the list for a data element that is greater than or equal to
// the chosen pivot element. Search from the left.
while (X[i] <= pivot && i < last)
i += 1;
// Search the list for a data element that is less than or equal to
// the chosen pivot element. Search from the right.
while (X[j] >= pivot && j > first)
j -= 1;
if (i < j) //swap(X[i],X[j])
{
temp = X[i];
X[i] = X[j];
X[j] = temp;
}
}
//swap(X[j],X[first])
temp = X[first];
X[first] = X[j];
X[j] = temp;
//Recursively apply quick sort on the two splits
quick_sort(first, j-1);
quick_sort(j+1, last);
}
}
//main( ) : Test driver for quick sort
void main(void)
{
sort sort_obj (5);
static int unsorted_list[] = {54,6,26,73,1};
sort_obj.load_list(unsorted_list);
sort_obj.show_list("List to be sorted in ascending order using quick sort");
sort_obj.quick_sort(0,4);
sort_obj.show_list("List sorted in ascending order using quick sort");
}
Welcome to pickSourcecode.com
