#include #include /* written by: bornToCode() This program compares the efficiency of the bubble and shell sort algorithms. As you can see, each algorithm's efficiency depends on the size of the array, etc. @kurwius: Thank you for suggesting a do while loop in place of a while loop in the shell sort. */ using namespace std; int compares, swapNum; void print(int ar[], int n) { cout << endl << "{ "; for(int i = 0; i < n; i++) { cout << ar[i]; if(!(i == n-1)) cout << ", "; } cout << " }" << endl; } void bubbleSort(int ar[], int n) { int swaps = 1; while(swaps) { swaps = 0; for(int i = 0; i < n; i++) { compares++; if(ar[i] > ar[i + 1]) { swap(ar[i], ar[i + 1]); swaps = 1; swapNum++; } } } } void shellSort(int ar[], int n) { int gap = n/2; int swaps = 1; while(gap > 0) { do { swaps = 0; for(int i = 0; i < n - gap; i++) { compares++; if(ar[i] > ar[i + gap]) { swap(ar[i], ar[i + gap]); swaps = 1; swapNum++; } } }while(swaps); gap = gap/2; } } void counterReset() { swapNum = 0; compares = 0; } void printCost() { cout << "Compares = " << compares; cout << "\nSwaps = " << swapNum; cout << endl; } int main() { const int SIZE = 10; int ar[SIZE]; for(int i = 0; i < SIZE; i++) { ar[i] = i; } random_shuffle(ar, ar+(SIZE - 1)); print(ar, SIZE); cout << "Bubble Sort: "; bubbleSort(ar, SIZE); print(ar, SIZE); printCost(); counterReset(); random_shuffle(ar, ar+(SIZE - 1)); print(ar, SIZE); cout << "Shell Sort: "; shellSort(ar, SIZE); print(ar, SIZE); printCost(); counterReset(); const int N = 100; int ar2[N]; for(int i = 0; i < N; i++) { ar2[i] = rand() % 100; } print(ar2, N); cout << "Bubble Sort: "; bubbleSort(ar2, N); print(ar2, N); printCost(); counterReset(); random_shuffle(ar2, ar2+(N - 1)); print(ar2, N); cout << "Shell Sort: "; shellSort(ar2, N); print(ar2, N); printCost(); counterReset(); return 0; }

compare_sorting_algorithms