}

Delphi.int.ru — Портал программистов

Вход Регистрация | Забыли пароль?

Просмотр кода

Идентификатор: b41576c7 Описание: MergeSort (+Inversions) Код загружен: 27 октября 2012, 13:01 (IlluminatI)

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int merge(int *arr, int l, int split, int r) {
  6. int *buf = new int[r - l + 1];
  7.  
  8. int pos1 = l;
  9. int pos2 = split + 1;
  10. int pos3 = 0;
  11.  
  12. int k = 0;
  13. while ((pos1 <= split)&&(pos2 <= r)) {
  14. if (arr[pos1] < arr[pos2])
  15. buf[pos3++] = arr[pos1++];
  16. else {
  17. buf[pos3++] = arr[pos2++];
  18. k +=(split - pos1 + 1);
  19. }
  20. }
  21.  
  22. while (pos2 <= r)
  23. buf[pos3++] = arr[pos2++];
  24. while (pos1 <= split)
  25. { buf[pos3++] = arr[pos1++]; k++; }
  26.  
  27. for (pos3 = 0; pos3 < r-l+1; pos3++)
  28. arr[l + pos3] = buf[pos3];
  29.  
  30. delete[] buf;
  31. return (k);
  32. }
  33.  
  34. int merge_sort(int *arr, int l, int r) {
  35. long split;
  36. int k = 0;
  37. if (l < r) {
  38. split = (l+r)/2;
  39. merge_sort(arr, l, split);
  40. merge_sort(arr, split + 1, r);
  41. k += merge(arr, l, split, r);
  42. }
  43. return (k);
  44. }
  45.  
  46. int main(void) {
  47. int n = 4;
  48. //cin >> n;
  49. // int *src_bread = new int[n];
  50. // int *needed_br = new int[n];
  51. // for (int i = 0; i < n; i++)
  52. // cin >> src_bread[i];
  53. // for (int i = 0; i < n; i++)
  54. // cin >> needed_br[i];
  55.  
  56. int src_bread[4] = {1, 3, 4, 2};
  57. int needed_br[4] = {4, 3, 2, 1};
  58.  
  59. int k1 = merge_sort(src_bread, 0, n - 1);
  60. int k2 = merge_sort(needed_br, 0, n - 1);
  61.  
  62. cout << "INV1: " << k1 << " INV2 = " << k2 << endl;
  63.  
  64. // if (k1 % 2 != k2 % 2)
  65. // cout << "Impossible";
  66. // else cout << "Possible";
  67.  
  68. int slp;
  69. cin >> slp;
  70.  
  71. return 0;
  72. }

Ссылка на данный код:

На главную страницу сервиса обмена кодом »