/************************* * Written By: bornToCode() **************************/ #include #include #include using namespace std; //regular insertion sort void insertionSort(int arr[], const int &n) { int firstUnsorted; int position; int current; for(firstUnsorted = 1; firstUnsorted < n; firstUnsorted++) { if(arr[firstUnsorted] < arr[firstUnsorted - 1]) { position = firstUnsorted; current = arr[firstUnsorted]; do { arr[position] = arr[position - 1]; position--; } while(position > 0 && arr[position - 1] > current); arr[position] = current; } } } //modified insertion sort void insertionSort(int arr[], const int &n, const int &start, const int &increment) { int firstUnsorted; int position; int current; for(firstUnsorted = start; firstUnsorted < n; firstUnsorted += increment) { if(firstUnsorted != 0) { if(arr[firstUnsorted] < arr[firstUnsorted - 1]) { position = firstUnsorted; current = arr[firstUnsorted]; do { arr[position] = arr[position - 1]; position--; } while(position > 0 && arr[position - 1] > current); arr[position] = current; } } } } void shellSort(int arr[], const int &n) { int increment = n; int start; do { increment = increment/3 + 1; for(start = 0; start < increment; start++) { insertionSort(arr, n, start, increment); } } while(increment > 1); } void print(int const arr[], const int &n) { cout << endl << endl; for(int i = 0; i < n; i++) { cout << "[" << arr[i] << "] "; } cout << endl << endl; } int main() { int n; cout << "Enter the number of list entries: "; try { cin >> n; if(cin.fail()) throw std::domain_error("Domain Error: Please enter a positive integer."); cout << "\nn = " << n << endl; int arr[n]; srand(time(NULL)); for(int i = 0; i < n; i++) { arr[i] = rand() % 100 + 1; } print(arr, n); //insertionSort(arr, n, 1, 1); shellSort(arr, n); print(arr, n); } catch(const std::exception &ex) { cout << endl << ex.what(); } return 0; }