Добрый вечер, гвардейцы. Хотел сделать красивый пост с описанием работы всех сортировок, но, увы, не успел, потому выкладываю просто файл со всеми реализованными сортировками. Проверки все достаточно топорные, так что перепишете под себя, если захотите =) По всем вопросам писать сюда под тему
- Bubble sort
- Merge sort
- Radix LSD
- Selection sort
- HeapSort
- Counting sort
- Shell Sort
- Quick Sort
Ctrl+F и вводим нужную сортировку.
Сортировки Пузырек (Bubble sort) #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <time.h> #include <cstdio> using namespace std; void BubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) for (int j = 0; j < n – 1 - j; j++) { if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]); } } int main() { const int n = 10000; //Вводим длину массива int a[n]; /* int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() % mod; cout << a[i] << " "; } cout << endl; */ freopen("input10k.txt", "r", stdin); // Для конечного тестирования на скорость unsigned int start_time = clock(); BubbleSort(a, n); unsigned int end_time = clock(); unsigned int search_time = end_time - start_time; cout << "Time in seconds: " << double(search_time) / double(1000) << endl; cout << "Sorted:" << endl; for (int i = 0; i < n; i++) { cout << a[i] << " "; } } Cлияние (merge sort) #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <time.h> #include <cstdio> using namespace std; void Merge(int arr[], long int left, long int right, long int mid) { long int i, j = 0, k = left, nleft = mid - left + 1, nright = right - mid; int* LeftArr = new int[nleft], * RightArr = new int[nright]; for (i = 0; i < nleft; i++) LeftArr[i] = arr[left + i]; for (i = 0; i < nright; i++) RightArr[i] = arr[mid + i + 1]; i = 0; while (i < nleft && j < nright) { if (LeftArr[i] <= RightArr[j]) { arr[k] = LeftArr[i]; i++; } else { arr[k] = RightArr[j]; j++; } k++; } while (i < nleft) { arr[k] = LeftArr[i]; i++; k++; } while (j < nright) { arr[k] = RightArr[j]; j++; k++; } } void MergeSort(int arr[], long int left,long int right) { if (left < right) { long int mid = (left + right - 1) / 2; MergeSort(arr, left, mid); MergeSort(arr, mid + 1, right); Merge(arr, left, right, mid); } } int main() { const long int n = 10; //Вводим длину массива int *a=new int[n]; int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() % mod; cout << a[i] << " "; } cout << endl; /* freopen("input10k.txt", "r", stdin); // Для конечного тестирования на скорость for (long int i = 0; i < n; i++) cin >> a[i]; */ unsigned int start_time = clock(); MergeSort(a, 0, n-1); unsigned int end_time = clock(); unsigned int search_time = end_time - start_time; cout << "Time in seconds: " << double(search_time) / double(1000) << endl; cout << "Sorted:" << endl; //Вывод массива for (int i = 0; i < n; i++) { cout << a[i] << " "; } } Разрядная (Radix LSD) #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <time.h> #include <cstdio> using namespace std; int Rad(int x, int n) { return (x / int(pow(10, n))) % 10; } void RadixSort(int arr[], long int n) { for (int j = 0; j <= 4; j++) { long int k=0; int** R = new int* [10]; int nR[10]; for (int i = 0; i <= 9; i++) { R[i] = new int[n]; nR[i] = 0; } for (int i = 0; i < n; i++) { int num = Rad(arr[i], j); R[num][nR[num]] = arr[i]; nR[num]++; } for (int i = 0; i <= 9; i++) { for (int l = 0; l < nR[i]; l++) { arr[k] = R[i][l]; k++; } } for (int i = 0; i <= 9; i++) delete[]R[i]; } } int main() { const long int n = 90000; //Вводим длину массива int *a=new int[n]; /* int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() % mod; cout << a[i] << " "; } cout << endl; */ freopen("input90k.txt", "r", stdin); // Для конечного тестирования на скорость for (long int i = 0; i < n; i++) cin >> a[i]; unsigned int start_time = clock(); RadixSort(a, n); unsigned int end_time = clock(); unsigned int search_time = end_time - start_time; cout << "Time in seconds: " << double(search_time) / double(1000) << endl; /* cout << "Sorted:" << endl; //Вывод массива for (long int i = 0; i < n; i++) { cout << a[i] << " "; } */ delete[]a; } Выбором (Selection Sort) #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <time.h> #include <cstdio> using namespace std; void SelectionSort(int arr[], long int n) { for (long int i = 0; i < n; i++) { int minx = arr[i]; long int minc = i; for (long int j = i+1; j < n; j++) { if (arr[j] < minx) { minx = arr[j]; minc = j; } } swap(arr[i], arr[minc]); } } int main() { const long int n = 30000; //Вводим длину массива int *a=new int[n]; /* int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() % mod; cout << a[i] << " "; } cout << endl; */ freopen("input30k.txt", "r", stdin); // Для конечного тестирования на скорость for (long int i = 0; i < n; i++) cin >> a[i]; unsigned int start_time = clock(); SelectionSort(a, n); unsigned int end_time = clock(); unsigned int search_time = end_time - start_time; cout << "Time in seconds: " << double(search_time) / double(1000) << endl; cout << "Sorted:" << endl; //Вывод массива for (long int i = 0; i < n; i++) { cout << a[i] << " "; } delete[]a; } Пирамидальная сортировка (HeapSort/ сортировка кучей) #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <time.h> #include <cstdio> using namespace std; void DoubleHeap(int arr[], long int n, long int root) { long int Big = root, n1 = 2 * root + 1, n2 = 2 * root + 2; if (arr[Big] < arr[n1] && n1 < n) Big = n1; if (arr[Big] < arr[n2] && n2 < n) Big = n2; if (Big != root) { swap(arr[root], arr[Big]); if(Big<=n/2-1) DoubleHeap(arr, n, Big); } } void HeapSort(int arr[], long int n) { for (int i = n / 2 - 1; i >= 0; i--) DoubleHeap(arr, n, i); for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); DoubleHeap(arr, i, 0); } } int main() { const long int n = 810000; //Вводим длину массива int* a = new int[n]; /* int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() % mod; cout << a[i] << " "; } cout << endl; */ freopen("input810k.txt", "r", stdin); // Для конечного тестирования на скорость for (long int i = 0; i < n; i++) cin >> a[i]; unsigned int start_time = clock(); HeapSort(a, n); unsigned int end_time = clock(); unsigned int search_time = end_time - start_time; cout << "Time in seconds: " << double(search_time) / double(1000) << endl; /* cout << "Sorted:" << endl; //Вывод массива for (long int i = 0; i < n; i++) { cout << a[i] << " "; } */ return 0; } Подсчетом (Counting sort) #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <time.h> #include <cstdio> using namespace std; void CountingSort(int arr[], long int n) { int maxel = arr[0]; for (int i = 0; i < n;i++) if (arr[i] > maxel) maxel = arr[i]; int* a = new int[maxel + 1]; for (int i = 0; i <= maxel;i++) a[i] = 0; for (int i = 0; i < n; i++) { int t = arr[i]; a[t]=a[t]+1; } for (int i = 0; i <= maxel; i++) for (int j = 1; j <= a[i]; j++) cout << i << " "; cout << endl; } int main() { const long int n = 10; //Вводим длину массива int *a=new int[n]; /* int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() % mod; cout << a[i] << " "; } cout << endl; */ freopen("input810k.txt", "r", stdin); // Для конечного тестирования на скорость for (long int i = 0; i < n; i++) cin >> a[i]; unsigned int start_time = clock(); CountingSort(a, n); unsigned int end_time = clock(); unsigned int search_time = end_time - start_time; cout << "Time in seconds: " << double(search_time) / double(1000) << endl; /* cout << "Sorted:" << endl; //Вывод массива for (long int i = 0; i < n; i++) { cout << a[i] << " "; } */ return 0; } Shell Sort (взяты базовые промежутки Шелла) #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <time.h> #include <cstdio> using namespace std; void ShellSort(int arr[], long int n) { for (int d=n/2;d>0;d=d/2) { for (int i = d; i < n; i++) for (int j = i; j > 0 && arr[j - d] > arr[j]; j-=d) swap(arr[j - d], arr[j]); } } int main() { const long int n = 10; //Вводим длину массива int* a = new int[n]; int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() % mod; cout << a[i] << " "; } cout << endl; /* freopen("input30k.txt", "r", stdin); // Для конечного тестирования на скорость for (long int i = 0; i < n; i++) cin >> a[i]; */ unsigned int start_time = clock(); ShellSort(a, n); unsigned int end_time = clock(); unsigned int search_time = end_time - start_time; cout << "Time in seconds: " << double(search_time) / double(1000) << endl; cout << "Sorted:" << endl; //Вывод массива for (long int i = 0; i < n; i++) { cout << a[i] << " "; } return 0; } Quick Sort #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <time.h> #include <cstdio> using namespace std; void QuickSort(int arr[], long int left, long int right) { int i = left; int j = right; int x = arr[(i + j) / 2]; do { while (arr[i] < x) i++; while (arr[j] > x) j--; if (i <= j) {swap(arr[i], arr[j]); i++; j--;} } while (i <= j); if (left < j) QuickSort(arr,left, j); if (i < right) QuickSort(arr,i, right); } int main() { const long int n = 810000; //Вводим длину массива int *a=new int[n]; /* int mod = 100; // Вводим максимально допустимые числа, далее начальное тестирование на работоспособность srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() % mod; cout << a[i] << " "; } cout << endl; */ freopen("input810k.txt", "r", stdin); // Для конечного тестирования на скорость for (long int i = 0; i < n; i++) cin >> a[i]; unsigned int start_time = clock(); QuickSort(a, 0, n-1); unsigned int end_time = clock(); unsigned int search_time = end_time - start_time; cout << "Time in seconds: " << double(search_time) / double(1000) << endl; /* cout << "Sorted:" << endl; //Вывод массива for (long int i = 0; i < n; i++) { cout << a[i] << " "; } */ return 0; }