// // demonstrates a bubble 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 // // "In a bubble sort, several left-to-right passes are made over the array // of records to be sorted. In each pass, pairs of adjacent records are compared and // exchanged if necessary. The sort terminates following a pass in which no records // are exchanged." (p. 444) // E. Horowitz, et al. Fundamentals of Data Structures in C++. // Computer Science Press, New York, 1995. // // This routine sorts an array of integers in ascending order. // void bubbleSort (int array[], int elementCount) { bool swappedElements = true; while (swappedElements) { swappedElements = false; // set flag to false for (int i = 0; i < (elementCount-1); i ++) // elementCount-1 because we are comparing [i] with [i+1] { if (array[i+1] < array[i]) { // element to the right is less than current element, so swap int temp = array[i]; array[i] = array[i+1]; array[i+1] = temp; swappedElements = true; // signal that we performed a swap } } } } // // 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 bubbleSort (array, numElements); // print the array for (i = 0; i < numElements; i = i + 1) { cout << array[i] << ' '; } cout << endl; return 0; }