Ten Sorting Algorithms Overview
Bubble Sort
#include #include #include #include #include
void bubbleSort(std::vector &v) { int n = v.size(); if (n < 2) return; bool flag = false; for (int i = n - 1; i > 0; --i) { flag = false; for (int j = 0; j < i; ++j) { if (v[j] > v[j + 1]) { int t = v[j]; v[j] = v[j + 1]; v[j + 1] = t; flag = true; } } if (!flag) return; } }
int main() { srand(time(NULL)); std::vector v(10); for (int i = 0; i < 10; ++i) { v.push_back(rand()); }
printf("Sorting before:\n");
for (const auto& i : v) {
printf("%d ", i);
}
printf("\n");
printf("Sorting after:\n");
bubbleSort(v);
for (const auto& i : v) {
printf("%d ", i);
}
printf("\n");
return 0;
}
Selcetion Sort
#include #include #include #include
void selectSort(std::vector& v) { if (v.size() < 2) return; int minPos = 0; for (int i = 0; i < v.size() - 1; ++i) { minPos = i; for (int j = i + 1; j < v.size(); ++j) { if (v[j] < v[minPos]) { minPos = j; } } if (minPos != i) { int t = v[minPos]; v[minPos] = v[i]; v[i] = t; } } }
void selectSort2(std::vector& v) { int l = 0, r = v.size() - 1; int minPos = 0, maxPos = 0; while (l < r) { minPos = maxPos = l; for (int i = l; i <= r; ++i) { if (v[i] < v[minPos]) minPos = i; if (v[i] > v[maxPos]) maxPos = i; } if (minPos != l) { int t = v[minPos]; v[minPos] = v[l]; v[l] = t; } if (maxPos == l) maxPos = minPos; if (maxPos != r) { int t = v[maxPos]; v[maxPos] = v[r]; v[r] = t; } ++l; --r; } }
int main() { srand(time(nullptr)); std::vector v; for (int i = 0; i < 10; ++i) { v.push_back(rand() % 100); }
printf("Sorting before\n");
for (const auto& i : v) {
printf("%d ", i);
}
printf("\n");
selectSort2(v);
printf("Sorting after\n");
for (const auto& i : v) {
printf("%d ", i);
}
return 0;
}
Insertion Sort
#include #include #include
void insertSort(int arr[], int n) { int i = 0, j = 0; for (i = 1; i < n; ++i) { int tmp = arr[i]; for (j = i - 1; (j >= 0) && (arr[j] > tmp); --j) { arr[j + 1] = arr[j]; } arr[j + 1] = tmp; } }
int main() { srand(time(NULL)); int arr[10] = {0}; int n = sizeof(arr) / sizeof(int); for (int i = 0; i < n; ++i) { arr[i] = rand() % 100; } printf("before:\n"); for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } printf("\n"); insertSort(arr, n); printf("after:\n"); for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } printf("\n"); return 0; }
Shell Sort
#include #include #include
void shellSort(int arr[], int n, int step) { int i = 0, j = 0; for (i = step; i < n; ++i) { int tmp = arr[i]; for (j = i - step; j >= 0 && arr[j] > tmp; j -= step) { arr[j + step] = arr[j]; } arr[j + step] = tmp; } }
void shell(int arr[], int n) { for (int step = n / 2; step > 0; step /= 2) { shellSort(arr, n, step); } }
int main() { srand(time(NULL)); int arr[10] = {0}; int n = sizeof(arr) / sizeof(int); for (int i = 0; i < n; ++i) { arr[i] = rand() % 100; } printf("before:\n"); for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } printf("\n"); shell(arr, n); printf("after:\n"); for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } printf("\n"); return 0; }
Quick Sort
#include #include #include #include
int partition(int* arr, int low, int high) { int pivot = arr[low]; int left = low, right = high; while (left < right) { while (left < right && arr[right] >= pivot) right--; arr[left] = arr[right]; while (left < right && arr[left] <= pivot) left++; arr[right] = arr[left]; } arr[left] = pivot; return left; }
void quickSort(int* arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi + 1); quickSort(arr, pi + 1, high); } }
int main() { srand(time(NULL)); int arr[10] = {0}; memset(arr, 0, sizeof(arr)); int len = sizeof(arr) / sizeof(int); for (int i = 0; i < len; ++i) { arr[i] = rand() % 100; } printf("before: \n"); for (int i = 0; i < len; ++i) { printf("%d ", arr[i]); } printf("\n");
quickSort(arr, 0, len - 1);
printf("after: \n");
for (int i = 0; i < len; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Merge Sort
#include #include #include #include
void merge(int* arr, int low, int mid, int high) { int tmp[high - low + 1], k = 0; int i = low, j = mid + 1; while (i <= mid && j <= high) { tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; } while (i <= mid) { tmp[k++] = arr[i++]; } while (j <= high) { tmp[k++] = arr[j++]; } memcpy(arr + low, tmp, sizeof(tmp)); }
void mergeSort(int* arr, int low, int high) { if (low < high) { int mid = low + (high - low) / 2; mergeSort(arr, low, mid); mergeSort(arr, mid + 1, high); merge(arr, low, mid, high); } }
int main() { srand(time(NULL)); int arr[10] = {0}; memset(arr, 0, sizeof(arr)); int len = sizeof(arr) / sizeof(int); for (int i = 0; i < len; ++i) { arr[i] = rand() % 100; } printf("before: \n"); for (int i = 0; i < len; ++i) { printf("%d ", arr[i]); } printf("\n");
mergeSort(arr, 0, len - 1);
printf("after: \n");
for (int i = 0; i < len; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Heap Sort
#include #include #include #include
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
void heapfy(int* arr, int i, int n) { int father = i; int son = 2 * father + 1; while (son <= n) { if (son + 1 <= n && arr[son + 1] > arr[son]) son++; if (arr[father] > arr[son]) return; swap(&arr[son], &arr[father]); father = son; son = 2 * father + 1; } }
void heapSort(int* arr, int len) { for (int i = (len - 1) / 2; i >= 0; --i) heapfy(arr, i, len - 1); for (int i = len - 1; i > 0; --i) { swap(&arr[0], &arr[i]); heapfy(arr, 0, i - 1); } }
int main() { srand(time(NULL)); int arr[10] = {0}; memset(arr, 0, sizeof(arr)); int len = sizeof(arr) / sizeof(int); for (int i = 0; i < len; ++i) { arr[i] = rand() % 100; } printf("before: \n"); for (int i = 0; i < len; ++i) { printf("%d ", arr[i]); } printf("\n");
heapSort(arr, len);
printf("after: \n");
for (int i = 0; i < len; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Counting Sort
#include #include #include #include
int argMax(int* arr, int len) { int maxValue = -1; for (int i = 0; i < len; ++i) { maxValue = arr[i] > maxValue ? arr[i] : maxValue; } return maxValue; }
void countSort(int* arr, int len) { int maxValue = argMax(arr, len); int tmp[maxValue + 1]; memset(tmp, 0, sizeof(tmp)); for (int i = 0; i < len; ++i) { tmp[arr[i]]++; } for (int i = 0, k = 0; i < maxValue + 1; ++i) { while (tmp[i]--) { arr[k++] = i; } } }
int main() { srand(time(NULL)); int arr[10] = {0}; memset(arr, 0, sizeof(arr)); int len = sizeof(arr) / sizeof(int); for (int i = 0; i < len; ++i) { arr[i] = rand() % 100; } printf("before: \n"); for (int i = 0; i < len; ++i) { printf("%d ", arr[i]); } printf("\n");
countSort(arr, len);
printf("after: \n");
for (int i = 0; i < len; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Bucket Sort
#include #include #include #include
int partition(int* arr, int low, int high) { int pivot = arr[low]; int left = low, right = high; while (left < right) { while (left < right && arr[right] >= pivot) right--; arr[left] = arr[right]; while (left < right && arr[left] <= pivot) left++; arr[right] = arr[left]; } arr[left] = pivot; return left; }
void quickSort(int* arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }
void bucketSort(int* arr, int len) { int bucket[len][len]; int bucketSize[len]; memset(bucket, 0, sizeof(bucket)); memset(bucketSize, 0, sizeof(bucketSize)); for (int i = 0; i < len; ++i) { bucket[arr[i] / 10][bucketSize[arr[i] / 10]++] = arr[i]; } for (int i = 0; i < len; ++i) { quickSort(bucket[i], 0, bucketSize[i] - 1); } for (int i = 0, k = 0; i < len; ++i) { for (int j = 0; j < bucketSize[i]; ++j) { arr[k++] = bucket[i][j]; } } }
int main() { srand(time(NULL)); int arr[10]; int len = sizeof(arr) / sizeof(int); memset(arr, 0, sizeof(arr)); for (int i = 0; i < len; ++i) { arr[i] = rand() % 100; } printf("before: \n"); for (const auto& i : arr) { printf("%d ", i); } printf("\n");
bucketSort(arr, len);
printf("after: \n");
for (const auto& i : arr) {
printf("%d ", i);
}
printf("\n");
return 0;
}
Radix Sort
#include #include #include #include
void argMax(int* arr, int len, int& maxValue) { for (int i = 0; i < len; ++i) { maxValue = arr[i] > maxValue ? arr[i] : maxValue; } }
void _radixSort(int* arr, int len, int exp) { int result[len]; int bucket[10]; memset(result, 0, sizeof(result)); memset(bucket, 0, sizeof(bucket)); for (int i = 0; i < len; ++i) { bucket[(arr[i]/exp)%10]++; } for (int i = 1; i < 10; ++i) { bucket[i] += bucket[i-1]; } for (int i = len - 1; i >= 0; --i) { int iexp = (arr[i]/exp)%10; result[bucket[iexp]-1] = arr[i]; bucket[iexp]--; } memcpy(arr, result, sizeof(result)); }
void radixSort(int* arr, int len) { int maxValue = 0; argMax(arr, len, maxValue); for (int exp = 1; maxValue / exp > 0; exp *= 10) { _radixSort(arr, len, exp); } }
int main() { srand(time(NULL)); int arr[10]; int len = sizeof(arr) / sizeof(int); memset(arr, 0, sizeof(arr)); for (int i = 0; i < len; ++i) { arr[i] = rand() % 100; } printf("before: \n"); for (const auto& i : arr) { printf("%d ", i); } printf("\n");
radixSort(arr, len);
printf("after: \n");
for (const auto& i : arr) {
printf("%d ", i);
}
printf("\n");
return 0;
}
