SHARE
TWEET

Untitled

a guest Oct 21st, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void bubbleSortVolume1(int arr[], int n) {
  2.     for (int i = 0; i < n - 1; i++) { // number of iterations needed
  3.         for (int j = 0; j < n - i - 1; j++) { // iterations for sorted elements;
  4.             if (arr[j] > arr[j + 1]) {
  5.                 int temp = arr[j];
  6.                 arr[j] = arr[j + 1];
  7.                 arr[j + 1] = temp;
  8.                 //swap(arr[j], arr[j+1]);
  9.             }
  10.         }
  11.     }
  12. }
  13. void bubbleSortVolume2(int arr[], int n) {
  14.     bool sorted;
  15.     do {
  16.         sorted = true; //until the array is not sorted;
  17.         for (int i = 0; i < n - 1; i++) { //number of iterations needed
  18.             if (arr[i] > arr[i + 1]) {
  19.                 sorted = false; // there is a swap made
  20.                 swap(arr[i], arr[i + 1]);
  21.             }
  22.         }
  23.     } while (sorted == false); // until there is no swaps made
  24. }
  25. //selectionsort - O(n^2)
  26. void selectionSort(int arr[], int n) {
  27.     for (int i = 0; i < n - 1; i++) { // number of iterations/keys;
  28.         int iMin = i; // choosing the key
  29.         for (int j = i + 1; j < n; j++) { //searching for the lowest of the rest to swap with the key;
  30.             if (arr[j] < arr[iMin]) {
  31.                 iMin = j;
  32.             }
  33.         }
  34.         if (iMin != i) {
  35.             swap(arr[i], arr[iMin]);
  36.         }
  37.     }
  38. }
  39.  
  40. //insertion sort - O(n^2)
  41. void insertionSort(int arr[], int n) {
  42.     for (int i = 1; i < n; i++) // for every element;
  43.     {
  44.         int currentIndex = i;
  45.         while (arr[currentIndex] < arr[currentIndex - 1] && currentIndex > 0) { // moving the element to the left until there is a lower number;
  46.             swap(arr[j], arr[j - 1]);
  47.             j--;
  48.         }
  49.     }
  50. }
  51.  
  52. //merge sort - 0(n * log n) и O(n) - сложност по памет
  53. //изисква допълнителна памет, но е по-бърз за огромни
  54. void merge(int *originalArray, int* mergeArray, int start, int mid, int end) {
  55.     int left = start;
  56.     int right = mid + 1;
  57.     for (int i = start; i <= end; i++)
  58.     {
  59.         if (left <= mid && (right > end || originalArray[left] <= originalArray[right])) // ako vsichki desni sa vzeti veche ili lqvoto chislo e po-malko ot dqsnoto
  60.         {
  61.             mergeArray[i] = originalArray[left];
  62.             left++;
  63.         }
  64.         else { // vuv vsichki drugi sluchai
  65.             mergeArray[i] = originalArray[right];
  66.             right++;
  67.         }
  68.     }
  69.     for (int i = start; i < end; i++) {
  70.         originalArray[i] = mergeArray[i];
  71.     }
  72. }
  73. void _mergeSort(int *originalArray, int *mergeArray, int start, int end) {
  74.     if (start < end) {
  75.         int mid = (start + end) / 2;
  76.         _mergeSort(originalArray, mergeArray, start, mid); // sorting the first half of the array;
  77.         _mergeSort(originalArray, mergeArray, mid + 1, end); // sorting the second half of the array;
  78.         merge(originalArray, mergeArray, start, mid, end); // final merge
  79.     }
  80. }
  81. void mergeSort(int *array, int length) {
  82.     int *mergeArray = new int[length]; // temporary array
  83.     _mergeSort(array, mergeArray, 0, length - 1); // the whole merge sorting for "array"
  84.     delete[] mergeArray;
  85. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top