Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef SORT_ALGORITHMS_H
- #define SORT_ALGORITHMS_H
- #include <vector>
- #include <algorithm>
- // QUICK SORT
- int partition(std::vector<int>& arr, int low, int high) {
- int pivot = arr[high];
- int i = low - 1;
- for (int j = low; j < high; j++) {
- if (arr[j] < pivot) {
- i++;
- std::swap(arr[i], arr[j]);
- }
- }
- std::swap(arr[i + 1], arr[high]);
- return i + 1;
- }
- void quickSort(std::vector<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);
- }
- }
- // MERGE SORT
- void merge(std::vector<int>& arr, int left, int mid, int right) {
- std::vector<int> leftPart(arr.begin() + left, arr.begin() + mid + 1);
- std::vector<int> rightPart(arr.begin() + mid + 1, arr.begin() + right + 1);
- int i = 0, j = 0, k = left;
- while (i < leftPart.size() && j < rightPart.size()) {
- if (leftPart[i] <= rightPart[j]) {
- arr[k++] = leftPart[i++];
- }
- else {
- arr[k++] = rightPart[j++];
- }
- }
- while (i < leftPart.size()) arr[k++] = leftPart[i++];
- while (j < rightPart.size()) arr[k++] = rightPart[j++];
- }
- void mergeSort(std::vector<int>& arr, int left, int right) {
- if (left < right) {
- int mid = (left + right) / 2;
- mergeSort(arr, left, mid);
- mergeSort(arr, mid + 1, right);
- merge(arr, left, mid, right);
- }
- }
- // BUBBLE SORT
- void bubbleSort(std::vector<int>& arr, int low, int high) {
- for (int i = low; i < high; ++i) {
- for (int j = low; j < high - (i - low) - 1; ++j) {
- if (arr[j] > arr[j + 1]) {
- std::swap(arr[j], arr[j + 1]);
- }
- }
- }
- }
- // INSERTION SORT
- void insertionSort(std::vector<int>& arr, int low, int high) {
- for (int i = low + 1; i <= high; ++i) {
- int key = arr[i];
- int j = i - 1;
- while (j >= low && arr[j] > key) {
- arr[j + 1] = arr[j];
- j--;
- }
- arr[j + 1] = key;
- }
- }
- // SELECTION SORT
- void selectionSort(std::vector<int>& arr, int low, int high) {
- for (int i = low; i < high; ++i) {
- int minIndex = i;
- for (int j = i + 1; j <= high; ++j) {
- if (arr[j] < arr[minIndex]) {
- minIndex = j;
- }
- }
- std::swap(arr[i], arr[minIndex]);
- }
- }
- #endif // SORT_ALGORITHMS_H
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
