Немного о сортировке слиянием.

Основная идея:

mergesort(l, r):
  • middle = (l + r) / 2
  • mergesort(l, middle)
  • mergesort(middle + 1, r)
  • объединить обе отсортированных части в одну отсортированную часть.


Особенно актуально освоить сортировки пишущим на языке Pascal, потому что о стандартных сортировках на этом языке я не знаю. И никто из моих знакомых не знает. Печаль. А уметь быстро сортировать нужно.

Более подробно на языке С++ (мой код):
  1. void
  2. mergesort(int *a, int *b, int l, int r){
  3.     if (l == r)
  4.         return;
  5.     int middle = (l + r) / 2;
  6.     mergesort(a, b, l, middle);
  7.     mergesort(a, b, middle + 1, r);
  8.  
  9.     int begin1 = l, end1 = middle;
  10.     int begin2 = middle + 1, end2 = r;
  11.     int pos = l;
  12.  
  13.     while (begin1 <= end1 && begin2 <= end2){
  14.         if (a[begin1] < a[begin2]){
  15.             b[pos] = a[begin1];
  16.             begin1++, pos++;
  17.         }
  18.         else{
  19.             b[pos] = a[begin2];
  20.             begin2++, pos++;
  21.         }
  22.     }
  23.     while (begin1 <= end1){
  24.         b[pos] = a[begin1];
  25.         begin1++, pos++;
  26.     }
  27.     while (begin2 <= end2){
  28.         b[pos] = a[begin2];
  29.         begin2++, pos++;
  30.     }
  31.  
  32.     for (int i = l; i <= r; ++i)
  33.         a[i] = b[i];
  34. }
Последнее изменение: Суббота, 15 Август 2020, 02:34