This is a simple C implementation of various sorting algorithms such as Bubble Sort, Insertion Sort, Selection Sort and Shell Sort.
Bubble Sort
Bubble sort, is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Complexity:
Worst complexity: n^2
Best complexity: n
Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final list one item at a time. This is an in-place comparison-
Complexity:
Worst complexity: n^2
Best complexity: n^2
Selection Sort
Selection sort is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.
Complexity:
Worst complexity: n^2
Best complexity: n^2
Shell Sort
Shell Sort Algorithm, also known as Shell sort or Shell’s method, is an in-place comparison sorting algorithm. It can be seen as either a generalization of sorting by exchange or sorting by insertion.
Complexity:
Average complexity: n*log(n)^2 or n^(3/2)
Best complexity: n
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 | #include <iostream.h> #include <stdio.h> #include <conio.h> void bubblesort(float[], int); void insertionsort(float[], int); void selectionsort(float[], int); void shellsort(float[], int); void print(float[], int); void read(float[], int); void main() { char wtc = 'y'; while (wtc == 'y' || wtc == 'Y') { clrscr(); int choice, n; float a[200]; printf("Enter the size of array"); scanf("%d", & n); printf("\n"); printf("Enter %d integers of array", n); read(a, n); printf("\n Enter the following numbers to use the following techniques:\n"); printf("\t1.BUBBLE SORT\n"); printf("\t2.INSERTION SORT\n"); printf("\t3.SELECTION SORT\n"); printf("\t4.SHELL SORT\n"); printf("\n"); printf("Enter your choice"); scanf("%d", & choice); switch (choice) { case 1: { bubblesort(a, n); print(a, n); //calling funtion by using switch statements getch(); break; } case 2: { insertionsort(a, n); print(a, n); getch(); break; } case 3: { selectionsort(a, n); print(a, n); getch(); break; } case 4: { shellsort(a, n); print(a, n); getch(); break; } } cout << "\n\n Do you want to continue(y/n)"; cin >> wtc; } getch(); } void read(float a[], int n) { for (int i = 0; i < n; i++) { cin >> a[i]; } } //Bubble sort implementation void bubblesort(float a[], int n) { for (int p = 0; p < (n - 1); p++) { for (int i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { float temp; temp = a[i + 1]; a[i + 1] = a[i]; a[i] = temp; } } } } //Insertion sort implementation void insertionsort(float a[], int n) { for (int i = 1; i < n; i++) { float x = a[i]; int j = i; while (j > 0 && a[j - 1] > x) //definition of insertion sort a[j--] = a[j - 1]; a[j] = x; } } //Shell sort implementation void shellsort(float a[], int n) { int gap; int swap; gap = n / 2; int k = 0; do { do { swap = 0; k++; int i; for (i = 0; i < n - gap; i++) if (a[i] > a[i + gap]) { int temp; temp = a[i]; a[i] = a[i + gap]; a[i + gap] = temp; swap = 1; } for (int t = 0; t < n; t++) cout << " " << a[t]; cout << "swap=" << swap; cout << "\n"; } while (swap); } while (gap = gap / 2); } //Selection sort implementation void selectionsort(float a[], int n) { for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n - 1; j++) if (a[i] > a[j]) { float temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } } } void print(float a[], int n) { for (int i = 0; i < n; i++) { cout << a[i] << ","; } cout << endl; } |
