Нэг тоог pivot болгож, түүнээс бага тоонуудыг зүүн тийш, бусдыг нь баруун тийш хуваагаад хоёр талыг дахин ингэж эрэмбэлдэг хурдан арга.

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

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

a = [3, 6, 1, 5, 4] array-г эрэмбэлье. Сүүлийн тоо 4-ийг pivot болгоно. 4-өөс бага 3, 1-ийг зүүн тийш, бусдыг нь баруун тийш цуглуулахад [3, 1, 4, 5, 6] болно.

4 эцсийн байрандаа орлоо. Одоо зүүн [3, 1], баруун [5, 6] хэсгийг тус тусад нь яг ингэж эрэмбэлнэ. Хариу: [1, 3, 4, 5, 6].

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

Merge Sort эхлээд хувааж, гол ажлаа нийлүүлэх үед хийдэг. Quick Sort эсрэгээрээ: эхлээд нэг тоог (pivot) сонгоод, бага тоонуудыг зүүн тийш, бусдыг нь баруун тийш хуваана. Pivot эцсийн байрандаа очих тул дараа нь нийлүүлэх шаардлагагүй.

Хуваах ажлыг (partition) ганц loop хийнэ. i нь дараагийн бага тоо очих байрыг заана. j-ээр тоо бүрийг харж, a[j] < p бол a[i]-тай солиод i-г нэмнэ. Эцэст нь pivot-ыг a[i]-тай солино.

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

p
Pivot-ын утга. Энэ кодод хэсгийн сүүлийн тоо a[r].
i
p-ээс бага тоонууд a[l]-ээс a[i - 1] хүртэл цугларна. Pivot эцэст нь i-р байранд очно.
partition
Хэсгийг p-ээс бага ба бусад гэж хоёр хуваах алхам.
quickSort(l, r)
a[l..r] хэсгийг эрэмбэлдэг recursive function.

Эхэнд: 8 3 6 1 9 2 5. Нэг тоог pivot болгоно. Түүнээс бага тоонуудыг зүүн тийш, бусдыг нь баруун тийш хуваана.

Алхам 1 / 23
Хурд
  • Энгийн
  • Pivot (p)
  • p-тэй харьцуулж буй
  • Солигдсон
  • Байрандаа орсон
  • Одоогийн хэсгээс гадуур
Слайд 1 / 7

Pivot-оор хуваана

Quick Sort нэг тоог pivot болгож сонгоно. Түүнээс бага тоонууд зүүн тийш, бусад нь баруун тийш очно.

quick-sort.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a[100005];
void quickSort(int l, int r) {
if (l >= r) return;
int p = a[r], i = l;
for (int j = l; j < r; j++) {
if (a[j] < p) {
swap(a[i], a[j]);
i++;
}
}
swap(a[i], a[r]);
quickSort(l, i - 1);
quickSort(i + 1, r);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
quickSort(0, n - 1);
for (int i = 0; i < n; i++) cout << a[i] << ' ';
return 0;
}

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

Их хэмжээний тоог нэмэлт array-гүйгээр хурдан эрэмбэлэх. Практикт хамгийн өргөн хэрэглэгддэг эрэмбэлэх аргын нэг.

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

1. Хэсгийн сүүлийн тоо pivot болно: p = a[r]. i = l нь бага тоо очих дараагийн байр. 2. a[l] … a[r − 1] тоо бүрийг p-тэй харьцуулна. a[j] < p бол a[i] ба a[j] байраа сольж, i нэгээр нэмэгдэнэ. 3. Эцэст нь a[i] ба a[r] солигдож, pivot байрандаа орно. 4. Pivot-ын зүүн, баруун хэсгийг яг ингэж эрэмбэлнэ (recursion). Оролт: эхний мөрөнд n, дараагийн мөрөнд n тоо.

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

Partition дуусахад pivot-оос зүүн талын бүх тоо p-ээс бага, баруун талынх нь p-ээс бага биш. Тиймээс pivot эцсийн байрандаа орсон. Хоёр талыг тус тусад нь эрэмбэлэхэд бүхэл array эрэмбэлэгдэнэ.

Pivot хэсгийг ойролцоогоор тэнцүү хуваавал log₂ n давхар болж, хугацаа O(n log n). Харин эрэмбэлэгдсэн array дээр сүүлийн тоо үргэлж хамгийн их тул хуваалт n - 1 ба 0 болж, O(n²) болно. n = 100 000 бол 5 тэрбум орчим харьцуулалт, хугацаандаа багтахгүй. Нэмэлт санах ой нь зөвхөн recursion-ий гүн.

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

  • Эрэмбэлэгдсэн эсвэл бүх тоо ижил array дээр O(n²) болно. Олимпиадад pivot-ыг санамсаргүй сонгох эсвэл sort() ашигла.
  • Муу тохиолдолд recursion-ий гүн n хүрч, stack overflow болж болно.
  • if (l >= r) return; мөрийг мартвал хоосон эсвэл ганц элементтэй хэсэг дээр recursion хэзээ ч зогсохгүй.
  • Эцэст нь pivot-ыг a[i]-тай солихоо мартах. Тэгвэл pivot байрандаа очихгүй, хариу буруу.

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

  • n = 1: quickSort(0, 0) шууд буцна.
  • Бүх утга ижил: a[j] < p хэзээ ч үнэн биш тул хуваалт тэнцвэргүй, O(n²).
  • Эрэмбэлэгдсэн array: pivot үргэлж хамгийн их тоо, хэсэг нэг нэгээр л багасна.
  • Хоёр элемент: ганц partition-оор шийдэгдэнэ.

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

  1. Анхдагч жишээ [8, 3, 6, 1, 9, 2, 5] дээр эхний partition хийсний дараа pivot 5 аль index-д очих вэ?

    Хариу харах

    3. Түүнээс бага 3, 1, 2 гурван тоо зүүн талд нь орно.

  2. 1000 тоотой эрэмбэлэгдсэн array дээр хэдэн харьцуулалт хийх вэ?

    Хариу харах

    999 + 998 + … + 1 = 499 500.

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

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

  1. 1.[4, 7, 2, 6, 1, 5] дээр эхний partition-ыг алхам алхмаар хий.

    Hint харах

    p = 5. j бүрт a[j] < 5 эсэхийг шалгаад, тийм бол a[i]-тай соль.

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

    Үр дүн нь [4, 2, 1, 5, 7, 6], pivot 5 нь index 3-т орлоо. Зүүн талд [4, 2, 1], баруун талд [7, 6].

  2. 2.Эрэмбэлэгдсэн array дээр удаашрахгүйн тулд pivot-ыг санамсаргүй сонгодог болго.

    Hint харах

    Санамсаргүй index дээрх тоог сүүл рүү нь шилжүүлбэл үлдсэн код хэвээр ажиллана.

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

    quickSort-ын эхэнд int k = l + rand() % (r - l + 1); swap(a[k], a[r]); нэмнэ. Ямар ч оролт дээр дунджаар O(n log n) болно.

  3. 3.Array-н k дахь хамгийн бага тоог дунджаар O(n) хугацаанд ол (Quickselect).

    Hint харах

    Partition-ы дараа pivot-ын index-ийг k-тэй харьцуул. Хоёр талыг хоёуланг нь эрэмбэлэх хэрэг бий юу?

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

    Pivot i-р байранд очсон бол: k == i үед хариу a[i]. k < i бол зөвхөн зүүн хэсэгт, үгүй бол зөвхөн баруун хэсэгт үргэлжлүүлнэ. Ганц талаар л явдаг тул дунджаар O(n).

Жишээ

Оролт

7
8 3 6 1 9 2 5

Гаралт

1 2 3 5 6 8 9

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

Бодлого

Хичээл

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