// The program performs a bubble sort of a fix array // for demo purposes. The algorithm used came from // the following site: // https://en.wikipedia.org/wiki/Bubble_sort?wprov=sfla1 // The code and documenting comments are mine. It // displays the contents of the array before any // sorting is done and after each pass through the // array so the user can read and understand this // code. Three different arrays are sorted: reverse // ordered, sorted ordered, and partially sorted. // To watch how it works, Burey created an awesome // web program here: https://code.sololearn.com/WRK8Y6Bkj9eP/?ref=app // This link is also in my comment on this program. #include // ******************** print ******************** // // Print the pass number, last element to check, and // the array contents like: // 0:4->10,20,30,40,50 // p l e e e e e // a a l l l l l // s s m m m m m // s t 1 2 3 4 5 // This code is able to handle any size array, // but it should break up the output lines on // larger ones. // // Arguments // pass: The current pass being displayed // size: The number of array elements // array: The array to display // last: The last element to check on next pass // // Returns // Nothing. void print( int pass, int size, int array[], int last) { int i; // Array index // Output the pass number, last element to check, // and for each element in the array display // either a comma or "->" (when first element // is being processed) plus the current element. // After the last element, output the end of line. std::cout << pass << ":" << last; for (i=0; i < size; i++) { if (i == 0) { std::cout << "->"; } else { std::cout << ","; } std::cout << array[i]; } // for std::cout << std::endl; } // print // ******************** sort ******************** // // Perform the bubble sort on the array. Note, // while the comments talk about a 5 element // array, the code can handle any number of // elements. // // Note: the 'pass' varable and debugging array // printing aren't required for this code to be // reused. If you use my code, please give me // credit in the comments. Based on the algorithm // documented on the following site: // https://en.wikipedia.org/wiki/Bubble_sort?wprov=sfla1 // // Arguments // size: The number of array elements // array: The array to display // // Returns // Nothing. void sort(int size, int array[]) { int swap; // Temporary value being swapped int last; // The last element swapped int num = // Number of elements to check size-1; int pass = // Number of passes made 0; // Output pass 0 (before any sorting is done), // last element to check, and the contents of // the array. print(pass, size, array, num); // For every possibly needed pass, perform a // swap as needed. If the data is completely // in reverse order, we need to process the // swap for 4 passes to handle our 5 element // array. If the data is already sorted, we // don't need to perform any passes. Of // course, any number of passes between 0 and // 4 could be required. We optimize this to // keep track of the last swap as everything // beyond that point is sorted. do { // Each pass moves the highest element // to the last position. Therefore, // we can avoid processing what we know // to be sorted. Also, as pointed out // in the pass loop comment, the data // may be sorted already. Therefore, // assume we are sorted by initializing // 'last' to zero and increment our pass // number. For every element that might // need a swap, check it. For our 5 // element array, this means 4 checks // on the first pass. After that, we // only check to where our last swap // was made. last = 0; pass++; for (int i = 0; i < num; i++) { // If the current element is greater // than the next one, swap them (save // the current element's value, copy // the next one into the current one, // copy the saved original value into // the next) and note that we swapped // this element. if (array[i] > array[i+1]) { swap = array[i]; array[i] = array[i+1]; array[i+1] = swap; last = i; } // if } // for // Output the current pass number, the // last element to check, and contents of // the array. Change the last element to // check for the next pass to be the last // one swapped and if we need to perform // another pass, loop. print(pass, size, array, last); num = last; } while (num > 0); } // sort // ******************** main ******************** // // The main entry point of the bubblesort program // sorting 3 fixed arrays. // // Arguments // Nothing. // // Returns // 0. int main() { int n = 5; // Number of items in array int array1[] = // Array in reverse order {90, 81, 67, 43, 12}; int array2[] = // Array in sorted order {12, 43, 67, 81, 90}; int array3[] = // Partially sorted array {12, 90, 67, 43, 81}; // Process the array in reverse order. std::cout << "Sort of reverse ordered data." << std::endl; sort(n, array1); // Process the array in sorted order. std::cout << std::endl << "Sort of sorted ordered data." << std::endl; sort(n, array2); // Process the array in reverse order. std::cout << std::endl << "Sort of partially sorted data." << std::endl; sort(n, array3); return 0; } // main

cBubbleSort mn sr