Thu Nov 13, 2008 3:05 pm
#include <iostream>
using namespace std;
/*
* Program to read a list of integers from standard input and print them in
* sorted order.
*
* Author: Tom Bennet
*/
/*
* Swap function for sorting.
*/
void swap(int &a, int &b)
{
int tmp; // Exchange temp value.
tmp = a;
a = b;
b = tmp;
}
/*
* Partition function for the recursive quicksort. It takes a pointer
* to the start of the array, and its size, and partitions it, returning a
* the location of the split point.
*/
int split(int arr[], int size)
{
int splitval = arr[0]; // Use first value as split value.
int left = 1; // Left (low) end scanner.
int right = size - 1; // Right (high) end scanner.
while(1)
{
// Scan tward middle until you find a items which are out
// of place at each end.
while(left <= right && arr[left] <= splitval)
left++;
while(splitval < arr[right])
right--;
// If they passed each other, we are done. Otherwise,
// swap the elements and try again.
if(left > right)
break;
else
swap(arr[left], arr[right]);
}
/* Move the pivot into place, and return. */
swap(arr[0], arr[right]);
return right;
}
/*
* Recursive quicksort. It takes a pointer to the data and a size,
* and it sorts the data.
*/
void sort(int data[], int size)
{
if(size > 1)
{
/* Split the array, and recursively sort each part. */
int splitloc = split(data, size);
sort(data, splitloc);
sort(data + splitloc + 1, size - splitloc - 1);
}
}
/*
* Main program. Reads the integers into an array, sorts them, and
* prints them out.
*/
const int MAX_NUM_INTS = 100;
int main()
{
int ints[MAX_NUM_INTS]; // Where the numbers go.
// Read them in.
int i;
for(i = 0; i < MAX_NUM_INTS && cin >> ints[i]; ++i);
int numints = i;
// Sort them.
sort(ints, numints);
// Print them.
cout << "==================" << endl;
for(int i = 0; i < numints; ++i)
cout << ints[i] << endl;
cout << "==================" << endl;
}
Codemiles.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com
Powered by phpBB © phpBB Group.