```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 ``` ```#include template void printArray(T * array, int size, const std::string& space) { for (int i = 0; i != size; ++i) { if (i != size - 1) std::cout << array[i] << space; else std::cout << array[i]; } std::cout << std::endl; } template void numberSort(T * array, int size) { //Commenting accomplished by Bazzy //Bubble sort algorithm bool bDone = false; // this flag will be used to check whether we have to continue the algorithm int length = size; //This actually isn't needed but I need something to hold the value of size so I can print it properly. printArray(array, size, "-"); // print the initial array while (!bDone) { bDone = true; // assume that the array is currently sorted for (int i = 0; i != length - 1; ++i) // for every element in the array ( notice: this can be a bit optimized, see http://en.wikipedia.org/wiki/Bubblesort#Optimizing_bubble_sort ) { if ( array[i] > array[i + 1] ) // compare the current element with the following one { // They are in the wrong order, swap them T tmp = array[i]; array[i] = array[i+1]; array[i+1] = tmp; bDone = false; // since we performed a swap, the array needs to be checked to see if it is sorted // this is done in the next iteration of the while printArray(array, size, "-"); // print current array to show the steps done by the algorithm } } length -= 1; //After each full iteration of the while loop, we know that the last element in the array is the highest number //Because we know this, we can lower the amount of iterations in the array we need to do and simply subtract 1. } } int main() { int array[] = { 50, 10, 20, 1, 5 }; //Array to sort int size = sizeof(array)/sizeof(int); numberSort (array, size); } ```
 ```1 2 3 4 5 6 7 8 9 ``` ```50-10-20-1-5 10-50-20-1-5 10-20-50-1-5 10-20-1-50-5 10-20-1-5-50 10-1-20-5-50 10-1-5-20-50 1-10-5-20-50 1-5-10-20-50 ```