www.pudn.com > ArraySort.zip > sort.h

/* 
	Author:	David Martinjak 
	Date:	December, 2001 
	Email:	martinfd@muohio.edu 
 
	This is a class header file that you can implement 
	in a driver program (such as the included sortmain.cpp) 
	to sort arrays of multiple types.   
 
	This software is open source code, and is provided 
	as-is with no warranties whatsoever.  Please feel 
	free to make modifications and use for your own 
	intents and purposes. 
 
  */ 
 
#include  
#include  
 
 
template  
class sort { 
public: 
	sort(int);								// constructor 
	void bubble(T array[]);					// bubble sort 
	void insertion(T array[]);				// insertion sort 
	void quick(T array[], int, int);		// quick sort 
	void selection(T array[]);				// selectioni sort 
 
private: 
	int size; 
}; 
 
 
 
template  
sort::sort(int s) { 
	if (s < 0) {			// make sure the size is valid 
		cerr << "** An invalid array size was entered." << endl; 
		exit(-1); 
		return; 
	} 
 
	size = s;				// if the size is valid, assign it  
} 
 
 
template  
void sort::bubble(T array[]) { 
	 
	T temp; 
	int last = size - 1; 
	bool sorted = true; 
 
	do { 
		sorted = true; 
		for (int i = 0; i < last; i++) { 
 
			/*  
				swap elements if the higher index element is  
				greater than the smaller index element 
			 */ 
 
			if (array[i] > array[i + 1]) {	 
				temp = array[i]; 
				array[i] = array[i + 1]; 
				array[i + 1] = temp; 
				sorted = false; 
			} 
 
		} 
 
		last--; 
	} while (!sorted); 
 
} 
 
 
template  
void sort::insertion(T array[]) { 
 
	T cVal;		// current value being examined 
	 
	for (int i = 1; i < size; i++) { 
 
		cVal = array[i]; 
		for (int n = i - 1; n >= 0 && cVal < array[n]; n--) { 
			array[n + 1] = array[n]; 
		} 
 
		array[n + 1] = cVal; 
 
	}	// end for loop 
 
} 
 
 
template  
void sort::quick(T array[], int llimit, int rlimit) { 
 
	T temp; 
	int left = llimit; 
	int right = rlimit; 
	int pivot = (left + right) / 2;	// find the median 
	T median = array[pivot]; 
 
 
	do { 
 
		while ((array[left] < median) && (left < rlimit)) { 
			left++; 
		} 
 
		while ((median < array[right]) && (right > llimit)) { 
			right--; 
		} 
 
		if (left <= right) { 
 
			// swap elements 
			temp = array[left]; 
			array[left] = array[right]; 
			array[right] = temp; 
			left++; 
			right--; 
		} 
 
	} while (left <= right); 
 
 
	if (llimit < right) { 
		sort::quick(array, llimit, right); 
	} 
 
 
	if (left < rlimit) { 
		sort::quick(array, left, rlimit); 
	} 
 
} 
 
 
template  
void sort::selection(T array[]) { 
 
	T temp; 
	int min; 
 
	for (int i = 0; i < size - 1; i++) { 
		min = i; 
 
		for (int n = i + 1; n < size; n++) { 
			if (array[n] < array[min]) { 
				min = n; 
			} 
 
			temp = array[min]; 
			array[min] = array[i]; 
			array[i] = temp; 
		} 
	} 
 
}