SHARE
TWEET

Untitled

a guest Jan 20th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void BubbleSort(int* array, size_t len) {
  5.     for (size_t j = len; j > 0; j--) {
  6.         bool sorted = true;
  7.  
  8.         for (int i = 1; i < j; i++) {
  9.             if (array[i - 1] > array[i]) {
  10.                 swap(array[i - 1], array[i]);
  11.                 sorted = false;
  12.             }
  13.         }
  14.  
  15.         if (sorted) break;
  16.     }
  17. }
  18.  
  19. void InsertionSort(int* array, size_t len) {
  20.     for (size_t j = 1; j < len; j++) {
  21.         size_t p = j;
  22.  
  23.         while (p > 0 && array[p - 1] > array[p])
  24.             swap(array[p - 1], array[p]), p--;
  25.     }
  26. }
  27.  
  28. void SelectionSort(int* array, size_t len) {
  29.     for (int i = 0; i < len; i++) {
  30.         int pos = i;
  31.  
  32.         for (int j = i + 1; j < len; j++) {
  33.             if (array[j] < array[pos])
  34.                 pos = j;
  35.         }
  36.  
  37.         swap(array[i], array[pos]);
  38.     }
  39. }
  40.  
  41. void QuickSort(int* array, size_t len) {
  42.     if (len > 1) {
  43.         size_t l = 0, r = len - 1, mid = len >> 1;
  44.         int pivot = array[mid];
  45.  
  46.         while (l <= r) {
  47.             while (array[l] < pivot) l++;
  48.             while (array[r] > pivot) r--;
  49.  
  50.             if (l < r)
  51.                 swap(array[l++], array[r--]);
  52.             else break;
  53.         }
  54.  
  55.         QuickSort(array, l);
  56.         QuickSort(array + l, len - l);
  57.     }
  58. }
  59.  
  60. void HeapSort(int* array, size_t len) {
  61.     // Building the heap
  62.     int* heap = new int[len];
  63.  
  64.     for (int i = 0; i < len; i++) {
  65.         heap[i] = array[i]; int j = i;
  66.  
  67.         while (j > 0) {
  68.             int parent = (j - 1) >> 1;
  69.  
  70.             if (heap[parent] > heap[j])
  71.                 swap(heap[parent], heap[j]),
  72.                 j = parent;
  73.             else break;
  74.         }
  75.     }
  76.  
  77.     // Extracting the heap
  78.     for (int i = 0; i < len; i++) {
  79.         array[i] = heap[0]; int j = 0;
  80.         swap(heap[0], heap[len - i - 1]);
  81.  
  82.         while (true) {
  83.             int  first_child = j * 2 + 1;
  84.             int second_child = j * 2 + 2;
  85.  
  86.             if (first_child < len - i) {
  87.                 int child;
  88.  
  89.                 if (second_child < len - i - 1) {
  90.                     if (heap[first_child] < heap[second_child])
  91.                         child = first_child;
  92.                     else
  93.                         child = second_child;
  94.                 } else {
  95.                     if (first_child < len - i - 1)
  96.                         child = first_child;
  97.                     else break;
  98.                 }
  99.  
  100.                 if (heap[child] < heap[j]) {
  101.                     swap(heap[child], heap[j]), j = child;
  102.                 } else break;
  103.             } else break;
  104.         }
  105.     }
  106.  
  107.     // Deleting the heap
  108.     delete[] heap;
  109. }
  110.  
  111. void MergeSort(int* array, size_t len) {
  112.     size_t mid = len >> 1;
  113.  
  114.     if (len > 1) {
  115.         MergeSort(array, mid);
  116.         MergeSort(array + mid, len - mid);
  117.     }
  118.  
  119.     int* temp = new int[len];
  120.     int i = 0, j = 0;
  121.  
  122.     for (int p = 0; p < len; p++) {
  123.         if (i >= mid)
  124.             temp[p] = array[mid + j], j++;
  125.         else if (mid + j >= len)
  126.             temp[p] = array[i], i++;
  127.         else if (array[i] <= array[mid + j])
  128.             temp[p] = array[i], i++;
  129.         else
  130.             temp[p] = array[mid + j], j++;
  131.     }
  132.  
  133.     for (int p = 0; p < len; p++)
  134.         array[p] = temp[p];
  135.  
  136.     delete[] temp;
  137. }
  138.  
  139. void __RadixSort__(int* array, size_t len, int digit) {
  140.     if (len > 1 && digit >= 0) {
  141.         size_t* digit_count = new size_t[256];
  142.         size_t* digit_ptr = new size_t[256];
  143.         int* buffer = new int[len];
  144.  
  145.         fill(digit_count, digit_count + 256, 0);
  146.         fill(digit_ptr, digit_ptr + 256, 0);
  147.  
  148.         for (int i = 0; i < len; i++) {
  149.             unsigned char temp = *((unsigned char*) (array + i) + digit);
  150.             digit_count[temp]++;
  151.         }
  152.  
  153.         for (int i = 1; i < 256; i++)
  154.             digit_ptr[i] = digit_ptr[i - 1] + digit_count[i - 1];
  155.  
  156.         for (int i = 0; i < len; i++) {
  157.             unsigned char temp = *((unsigned char*) (array + i) + digit);
  158.             buffer[digit_ptr[temp]++] = array[i];
  159.         }
  160.  
  161.         memcpy(array, buffer, len * sizeof(int));
  162.  
  163.         for (int i = 0; i < 256; i++) {
  164.             __RadixSort__(array + digit_ptr[i] - digit_count[i], digit_count[i], digit - 1);
  165.         }
  166.  
  167.         delete[] digit_count;
  168.         delete[] digit_ptr;
  169.         delete[] buffer;
  170.     }
  171. }
  172.  
  173. void RadixSort(int* array, size_t len) {
  174.     __RadixSort__(array, len, sizeof(int) - 1);
  175. }
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