挿入ソート、バブルソート、選択ソート、ヒルソート、集計ソート、クイックソート、スタックソート、ベースソートのC++実装

ヘッダファイルh配列生成用

#include 
#include 
#include 
using namespace std;
/*      ，    */
int* makeRamdomArr(int count, int ldomain, int rdomain) {
	
	int *arr = new int[count];
	srand((unsigned)time(NULL));
	int range = rdomain - ldomain; 
	for (int i = 0; i < count; i++) {
		arr[i] = (rand() % range) + ldomain;
	}
	return arr;
}

ヘッダファイルh補助スタック並べ替え用

// Assert: If "val" is false, print a message and terminate
// the program
inline void Assert(bool val, string s) {
	if (!val) { // Assertion failed -- close the program
		cout << "Assertion Failed: " << s << endl;
		exit(-1);
	}
}

// Swap two elements in a generic array
template<typename E>
inline void swap(E A[], int i, int j) {
	E temp = A[i];
	A[i] = A[j];
	A[j] = temp;
}


template <typename E, typename Comp> class heap {
private:
	E* Heap;          // Pointer to the heap array
	int maxsize;         // Maximum size of the heap
	int n;               // Number of elements now in the heap

	// Helper function to put element in its correct place
	void siftdown(int pos) {
		while (!isLeaf(pos)) { // Stop if pos is a leaf
			int j = leftchild(pos);  int rc = rightchild(pos);
			if ((rc < n) && Comp::prior(Heap[rc], Heap[j]))
				j = rc;            // Set j to greater child's value
			if (Comp::prior(Heap[pos], Heap[j])) return; // Done
			swap(Heap, pos, j);
			pos = j;             // Move down
		}
	}

public:
	heap(E* h, int num, int max)     // Constructor
	{
		Heap = h;  n = num;  maxsize = max;  buildHeap();
	}
	int size() const       // Return current heap size
	{
		return n;
	}
	bool isLeaf(int pos) const // True if pos is a leaf
	{
		return (pos >= n / 2) && (pos < n);
	}
	int leftchild(int pos) const
	{
		return 2 * pos + 1;
	}    // Return leftchild position
	int rightchild(int pos) const
	{
		return 2 * pos + 2;
	}    // Return rightchild position
	int parent(int pos) const  // Return parent position
	{
		return (pos - 1) / 2;
	}
	void buildHeap()           // Heapify contents of Heap
	{
		for (int i = n / 2 - 1; i >= 0; i--) siftdown(i);
	}

	// Insert "it" into the heap
	void insert(const E& it) {
		Assert(n < maxsize, "Heap is full");
		int curr = n++;
		Heap[curr] = it;            // Start at end of heap
		// Now sift up until curr's parent > curr
		while ((curr != 0) &&
			(Comp::prior(Heap[curr], Heap[parent(curr)]))) {
			swap(Heap, curr, parent(curr));
			curr = parent(curr);
		}
	}
	// Remove first value
	E removefirst() {
		Assert(n > 0, "Heap is empty");
		swap(Heap, 0, --n);       // Swap first with last value
		if (n != 0) siftdown(0);  // Siftdown new root val
		return Heap[n];             // Return deleted value
	}

	// Remove and return element at specified position
	E remove(int pos) {
		Assert((pos >= 0) && (pos < n), "Bad position");
		if (pos == (n - 1)) n--; // Last element, no work to do
		else
		{
			swap(Heap, pos, --n);          // Swap with last value
			while ((pos != 0) &&
				(Comp::prior(Heap[pos], Heap[parent(pos)]))) {
				swap(Heap, pos, parent(pos)); // Push up large key
				pos = parent(pos);
			}
			if (n != 0) siftdown(pos);     // Push down small key
		}
		return Heap[n];
	}
};

##すべて並べ替え

#include "heap.h"

// Swap two elements in a generic array
template<typename E>

extern void swap(E A[], int i, int j);

// For use with min-heap and sorting
class minIntCompare {
public:
	static bool prior(int x, int y) { return x < y; }
};

// Get the key from an int
class getintKey {
public:
	static int key(int x) { return x; }
};



//    
template <typename E, typename Comp>
void inssort(E A[], int n) { // Insertion Sort
	for (int i = 1; i < n; i++)       // Insert i'th record
		for (int j = i; (j > 0) && (Comp::prior(A[j], A[j - 1])); j--)
			swap(A, j, j - 1);
}

//    
template<typename E, typename Comp>
void bubsort(E A[], int n) {
	for (int i = 0; i < n - 1; i++)
		for (int j = n - 1; j > i; j--)
			if (Comp::prior(A[j], A[j - 1]))
				swap(A, j, j - 1);
}

//    
template<typename E, typename Comp>
void selsort(E A[], int n) {
	for (int i = 0; i < n - 1; i++) {
		int lowindex = i;
		for (int j = n - 1; j > i; j--)
			if (Comp::prior(A[j], A[lowindex]))
				lowindex = j;
		swap(A, i, lowindex);
	}
}

/*    */

//inssort2      ：sublist
//  16   ，  incresement 8   ，    ， 8 sublist
//  16   ，  incresement 4   ，    ， 4 sublist

//n sublist   index
template <typename E,typename Comp>
void inssort2(E A[], int n, int incr) {
	for (int i = incr; i < n; i += incr)
		for (int j = i; (j >= incr) && (Comp::prior(A[j], A[j - incr])); j -= incr)
			swap(A, j, j - incr);
}

template <typename E,typename Comp>
void shellsort(E A[], int n) {
	for (int i = n / 2; i > 2; i /= 2) //increasement     
		for (int j = 0; j < i; j++)//   incresement     sublist  
			//j sublist   index， n-j sublist   index
			inssort2<E,Comp>(&A[j], n - j, i);
}

/*    */
template <typename E,typename Comp>
void mergesort(E A[], E temp[], int left, int right) {
	if (left == right)return;
	int mid = (left + right) / 2;
	mergesort<E, Comp>(A, temp, left, mid);
	mergesort<E, Comp>(A, temp, mid+1, right);
	for (int i = left; i <= right; i++)
		temp[i] = A[i];


	//i1 i2       inlist     
	int i1 = left;
	int i2 = mid+ 1;
	//    
	for (int curr = left; curr <= right; curr++) {
		if (i1 == mid + 1)
			A[curr] = temp[i2++];
		else if (i2 > right)
			A[curr] = temp[i1++];
		else if (Comp::prior(temp[i1], temp[i2]))
			A[curr] = temp[i1++];
		else A[curr] = temp[i2++];
	}
}

/*    */
//template 
//inline int findpviot(E A[], int i, int j) {
//	return (i + j) / 2;
//}


//    privot     value，   index
template <typename E,typename Comp>
inline int partition(E A[], int l, int r, E&privot) {
	do {
		while (Comp::prior(A[++l], privot));
		while ((l < r) && Comp::prior(privot, A[--r]));
		swap(A, l, r);
	} while (l < r);
	return l;
}



//i leftmost index; j   rightmost index;
template <typename E, typename Comp>
void qsort(E A[], int i, int j) { // Quicksort
	if (j <= i) return; // Don't sort 0 or 1 element
	int pivotindex =(i+j)/2;
	swap(A, pivotindex, j);    // Put pivot at end
	// k will be the first position in the right subarray
	int k = partition<E, Comp>(A, i - 1, j, A[j]);
	swap(A, k, j);             // Put pivot in place
	qsort<E, Comp>(A, i, k - 1);
	qsort<E, Comp>(A, k + 1, j);
}




/*   */

template <typename E,typename Comp>
void heapsort(E A[], int n) {
	E maxval;
	heap<E, Comp>H(A, n, n);
	for (int i = 0; i < n; i++)
		maxval = H.removefirst();

}

/*Radix  */
//A      ，B    ，n A[]   ，k  digits  ，r     ，cnt[]   B[]            
template <typename E, typename getKey>
void radix(E A[], E B[],
	int n, int k, int r, int cnt[]) {
	// cnt[i] stores number of records in bin[i]
	int j;

	for (int i = 0, rtoi = 1; i < k; i++, rtoi *= r) { // For k digits
		for (j = 0; j < r; j++) cnt[j] = 0;        // Initialize cnt

		// Count the number of records for each bin on this pass
		for (j = 0; j < n; j++) cnt[(getKey::key(A[j]) / rtoi) % r]++;

		// Index B: cnt[j] will be index for last slot of bin j.
		for (j = 1; j < r; j++) cnt[j] = cnt[j - 1] + cnt[j];

		// Put records into bins, work from bottom of each bin.
		// Since bins fill from bottom, j counts downwards
		for (j = n - 1; j >= 0; j--)
			B[--cnt[(getKey::key(A[j]) / rtoi) % r]] = A[j];

		for (j = 0; j < n; j++) A[j] = B[j];    // Copy B back to A
	}
}