// // demonstrates an insertion sort // Written by Maxwell Sayles, 2001, for CPSC331, University of Calgary. // #include #include #include using namespace std; const int numElements = 128; // number of elements to sort // // // This routine sorts an array of integers in ascending order. // // The algorithm is taken from pp. 2-4. // Cormen, Thomas H., et al. Introduction to Algorithms. // The MIT Press, 1990. // void InsertionSort (int A[], int elementCount) { for (int j = 1; j < elementCount; j = j + 1) { int key = A[j]; // insert A[j] into the sorted sequence A[1..j-1] int i = j - 1; while ((i >= 0) && (A[i] > key)) { A[i+1] = A[i]; i = i - 1; } A[i+1] = key; } } // // program entry // int main() { int i = 0; // seed the random number generator srand((unsigned int)time(0)); // create an array of random integers int array[numElements]; for (i = 0; i < numElements; i = i + 1) { array[i] = rand() % numElements; // keep numbers in the range of 0-numElements } // sort the array InsertionSort (array, numElements); // print the array for (i = 0; i < numElements; i = i + 1) { cout << array[i] << ' '; } cout << endl; return 0; }