Хажуу хажуугийн хоёр тоог харьцуулж, их нь баруун тийш шилжсээр эрэмбэлэгддэг хамгийн энгийн эрэмбэлэх арга.

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

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

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

Эхний удаа зүүнээс баруун тийш явахад: 5 ба 1-ийг солиод [1, 5, 4, 2], 5 ба 4-ийг солиод [1, 4, 5, 2], 5 ба 2-ыг солиод [1, 4, 2, 5]. Хамгийн том 5 төгсгөлдөө очлоо.

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

Нэг удаа зүүнээс баруун тийш явахад хамгийн том тоо усан дахь бөмбөлөг шиг төгсгөл рүүгээ хөвж гарна. Дараагийн удаад түүнийг дахин харах хэрэггүй.

Тиймээс i дахь удаад сүүлийн i элемент аль хэдийн байрандаа байгаа. Дотор loop n - 1 - i хүртэл л явна.

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

pass
Array-г зүүнээс баруун тийш нэг удаа бүтэн туулах. Гадна loop-ын нэг эргэлт нь нэг pass.
swap
Хоёр элементийн байрыг солих. C++-д swap(a[j], a[j + 1]).
inversion
i < j байхад a[i] > a[j] байх хос. Bubble Sort яг inversion-ий тоогоор swap хийнэ.

Эхэнд: 5 1 4 2 8. Хажуу хажуугийн хоёр тоог харьцуулна. Зүүн тал нь их бол байрыг нь солино.

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

Bubble Sort гэж юу вэ?

Хажуу хажуугийн хоёр тоог харьцуулаад, их нь баруун тийш шилждэг. Ингэж явсаар хамгийн их тоо хамгийн сүүлд очно.

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

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

Тоонуудыг багаас нь их рүү эрэмбэлэх. Эрэмбэлэх санааг ойлгоход хамгийн тохиромжтой анхны алгоритм.

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

1. Зүүнээс эхлээд хажуу хажуугийн хоёр тоог (a[j], a[j + 1]) харьцуулна. 2. Зүүн талынх нь их бол swap хийж байрыг нь солино. 3. Нэг pass дуусахад хамгийн их тоо хамгийн сүүлд очно. 4. Үүнийг n − 1 удаа давтахад бүх тоо эрэмбэлэгдэнэ. Оролт: эхний мөрөнд n, дараагийн мөрөнд n тоо.

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

i дахь pass дуусахад үлдсэн хэсгийн хамгийн том тоо n - 1 - i байранд очно: тэр тоо хаана ч байсан, баруун хөрш бүрээсээ том тул swap-аар баруун тийш явсаар төгсгөлд хүрнэ. n - 1 pass-ын дараа бүх тоо байрандаа очно.

Хоёр давхар loop тул ойролцоогоор n² / 2 харьцуулалт хийнэ: хугацаа O(n²), нэмэлт санах ой O(1). n = 10 000 бол 50 сая харьцуулалт, n = 100 000 бол хэт удаан.

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

  • Дотор loop-ыг j < n - 1 - i биш j < n - i гэж бичвэл a[j + 1] нь array-гээс гарч, буруу утга уншина.
  • Буурахаар эрэмбэлэх бол харьцуулалтыг a[j] < a[j + 1] болгоно. Тэмдгийг солихоо мартаж болохгүй.
  • Том n дээр Bubble Sort ашиглах. Олимпиадад sort(a, a + n) эсвэл Merge Sort хэрэглэ.

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

  • n = 1: loop огт ажиллахгүй, array хэвээрээ.
  • Аль хэдийн эрэмбэлэгдсэн: нэг ч swap хийхгүй, гэхдээ харьцуулалт бүгд хийгдэнэ.
  • Урвуу эрэмбэтэй [5, 4, 3, 2, 1]: хамгийн олон swap, яг n(n - 1) / 2.
  • Ижил утгууд: > ашигладаг тул ижил хоёр тоог солихгүй, дараалал нь хадгалагдана.

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

  1. [3, 2, 1] array-г эрэмбэлэхэд хэдэн swap хийх вэ?

    Хариу харах

    3 swap. Inversion-ууд нь (3, 2), (3, 1), (2, 1) гэсэн гурав.

  2. Эхний pass дууссаны дараа юу баталгаатай вэ?

    Хариу харах

    Хамгийн том тоо сүүлийн байранд очсон. Бусад нь эрэмбэлэгдээгүй байж болно.

  3. n = 1000 бол ойролцоогоор хэдэн харьцуулалт хийх вэ?

    Хариу харах

    1000 · 999 / 2 ≈ 500 000.

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

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

  1. 1.[4, 3, 1, 2] дээр pass бүрийн дараах array-г бич.

    Hint харах

    Pass бүрт хажуу хажуугийн хосыг зүүнээс нь эхлэн шалга.

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

    1-р pass: [3, 1, 2, 4]. 2-р pass: [1, 2, 3, 4]. 3-р pass: өөрчлөлтгүй.

  2. 2.Pass бүрт ядаж нэг swap хийгдсэн эсэхийг хадгалж, swap хийгдээгүй бол эрт зогсдог болго.

    Hint харах

    Дотор loop-ын өмнө bool swapped = false; гэж зарла.

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

    Swap хийх бүрт swapped = true;. Дотор loop дууссаны дараа if (!swapped) break;. Эрэмбэлэгдсэн array дээр нэг л pass хийгээд зогсоно.

  3. 3.Bubble Sort-ыг ашиглан array-д нийт хэдэн inversion байгааг тоол.

    Hint харах

    Swap бүр яг нэг inversion-ийг арилгадаг.

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

    Swap хийх бүрт тоолуурыг 1-ээр нэмэхэд л болно. Эцсийн тоо нь inversion-ий тоо.

Жишээ

Оролт

5
5 1 4 2 8

Гаралт

1 2 4 5 8

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

Бодлого

Хичээл

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