Array-г хоёр хувааж, хэсэг бүрийг эрэмбэлээд, буцааж нийлүүлдэг хурдан арга.

IntermediateХугацаа: O(n log n)Санах ой: O(n)
HackerRank дээр бодох Өөр алгоритмтай уралдуулах

Эхлээд жижиг бодлого

a = [6, 2, 5, 1] array-г эрэмбэлье. Хоёр хувааж [6, 2] ба [5, 1] болгоод, тус бүрийг эрэмбэлбэл [2, 6] ба [1, 5].

Одоо хоёр эрэмбэлэгдсэн хэсгийг нийлүүлнэ: 2 ба 1-ээс 1-ийг, 2 ба 5-аас 2-ыг, 6 ба 5-аас 5-ыг авна. Үлдсэн 6-г нэмэхэд [1, 2, 5, 6].

Энгийн аргаас санаа руу

Bubble Sort n² хугацаа зарцуулдаг. Гэтэл эрэмбэлэгдсэн хоёр хэсгийг нийлүүлэх нь маш хурдан: хоёулангийнх нь эхнийг харьцуулаад багыг нь авахад л болно.

Тиймээс array-г дахин дахин хоёр хуваасаар нэг элементтэй болгоно. Нэг элемент өөрөө эрэмбэлэгдсэн. Дараа нь доороос дээш нийлүүлсээр бүтэн array-г эрэмбэлнэ.

Нэр томьёо ба тэмдэглэгээ

mergeSort(l, r)
a[l..r] хэсгийг эрэмбэлдэг recursive function.
m
Хуваах цэг: (l + r) / 2. Зүүн хэсэг [l, m], баруун хэсэг [m + 1, r].
merge
Эрэмбэлэгдсэн хоёр хэсгийг нэг эрэмбэлэгдсэн хэсэг болгох алхам.
t[]
Нийлүүлэхэд ашиглах туслах array. Эцэст нь a-д буцааж хуулна.

Эхэнд: 38 27 43 3 9 82 10. Array-г хоёр хувааж, хэсэг бүрийг эрэмбэлээд, буцааж нийлүүлнэ.

Алхам 1 / 34
Хурд
  • Энгийн
  • Харьцуулж буй
  • Үлдсэн тоо
  • a руу хуулсан тоо
  • Эрэмбэлэгдсэн
  • Одоогийн хэсгээс гадуур
Слайд 1 / 6

Хувааж ял

Том ажлыг жижиг хэсэгт хуваавал амархан. Merge Sort array-г хоёр хувааж, хэсэг бүрийг эрэмбэлээд, буцааж нийлүүлдэг.

merge-sort.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a[100005], t[100005];
void mergeSort(int l, int r) {
if (l == r) return;
int m = (l + r) / 2;
mergeSort(l, m);
mergeSort(m + 1, r);
int i = l, j = m + 1, k = l;
while (i <= m && j <= r) {
if (a[i] <= a[j]) {
t[k++] = a[i++];
} else {
t[k++] = a[j++];
}
}
while (i <= m) {
t[k++] = a[i++];
}
while (j <= r) {
t[k++] = a[j++];
}
for (int p = l; p <= r; p++) a[p] = t[p];
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
mergeSort(0, n - 1);
for (int i = 0; i < n; i++) cout << a[i] << ' ';
return 0;
}

Юунд хэрэгтэй вэ?

Их хэмжээний тоог хурдан эрэмбэлэх. "Хувааж ял" гэдэг чухал санааг сурах.

Яаж ажилладаг вэ?

1. Array-г дундуур нь хоёр хуваана: m = (l + r) / 2. 2. Зүүн, баруун хэсгийг тус тусад нь эрэмбэлнэ. Function өөрийгөө дуудна, өөрөөр хэлбэл recursion. 3. Хоёр хэсгийн эхний тоонуудаас багыг нь t-д хийсээр нийлүүлнэ. 4. t-ээс a руу буцааж хуулна. Оролт: эхний мөрөнд n, дараагийн мөрөнд n тоо.

Яагаад зөв, хэр хурдан бэ?

Recursion l == r үед зогсоно, нэг элемент өөрөө эрэмбэлэгдсэн. Хоёр хэсэг эрэмбэлэгдсэн бол merge алхам үргэлж үлдсэнүүдийн хамгийн багыг нь авдаг тул үр дүн нь эрэмбэлэгдсэн байна.

Хуваалт log₂ n давхар болно. Давхар бүрт нийт n элемент нийлүүлэгдэнэ. Иймээс хугацаа O(n log n), туслах array-д O(n) санах ой. n = 100 000 бол 2 сая орчим үйлдэл.

Түгээмэл алдаа

  • if (l == r) return; мөрийг мартвал recursion хэзээ ч зогсохгүй.
  • Merge-ийн дараа t доторх утгуудыг a руу буцааж хуулахаа мартах.
  • a[i] <= a[j] биш < гэж бичвэл ижил утгуудын дараалал солигдоно. Эрэмбэ зөв хэвээр ч stable биш болно.
  • Нэг хэсгийн элементүүд дуусахад нөгөө хэсгийн үлдсэнийг нэмэхээ мартах.

Хязгаарын тохиолдол

  • n = 1: mergeSort(0, 0) шууд буцна.
  • Сондгой урт: зүүн хэсэг нэгээр илүү элементтэй болно, асуудалгүй.
  • Бүх утга ижил: зөвхөн зүүнээс авна, дараалал хадгалагдана.

Өөрийгөө шалга

  1. [2, 6], [1, 5] хоёрыг нийлүүлэхэд хэдэн харьцуулалт хийх вэ?

    Хариу харах

    3: (2, 1), (2, 5), (6, 5). Үлдсэн 6-г харьцуулалтгүй нэмнэ.

  2. n = 8 бол хуваалт хэдэн давхар болох вэ?

    Хариу харах

    3 давхар: 8 → 4 → 2 → 1. log₂ 8 = 3.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.[3, 8, 1, 4, 2] array-г Merge Sort-оор эрэмбэлэхэд хуваах, нийлүүлэх алхмуудыг зур.

    Hint харах

    m = (0 + 4) / 2 = 2 тул эхлээд [3, 8, 1] ба [4, 2] болно.

    Хариу ба тайлбар

    [3, 8, 1] → [3, 8] ба [1] → [1, 3, 8]. [4, 2] → [2, 4]. Нийлүүлэхэд [1, 2, 3, 4, 8].

  2. 2.Кодыг буурахаар эрэмбэлдэг болго.

    Hint харах

    Зөвхөн merge доторх харьцуулалт л өөрчлөгдөнө.

    Хариу ба тайлбар

    if (a[i] >= a[j]) болгоно. Үлдсэн бүх код хэвээрээ.

  3. 3.Merge хийх үед array дахь inversion-ий тоог тоолдог болго.

    Hint харах

    Баруун хэсгээс a[j] авах бүрт зүүн хэсэгт хэдэн тоо үлдсэн бэ?

    Хариу ба тайлбар

    Баруунаас авах бүрт cnt += m - i + 1; нэмнэ. Зүүн хэсгийн үлдсэн бүх тоо a[j]-гээс их тул тэр бүр нэг inversion. Нийт хугацаа O(n log n) хэвээр.

Жишээ

Оролт

7
38 27 43 3 9 82 10

Гаралт

3 9 10 27 38 43 82

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.