Үлдсэн тоонуудаас хамгийн багыг нь олж, урд нь тавьсаар эрэмбэлдэг энгийн арга.

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

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

a = [4, 1, 3, 2] array-г өсөхөөр эрэмбэлье. Эхлээд бүх тооноос хамгийн багыг нь хайна: 1. Түүнийг хамгийн урд байгаа 4-тэй сольж [1, 4, 3, 2] болгоно.

Дараа нь үлдсэн [4, 3, 2] хэсгээс хамгийн бага 2-ыг олоод 4-тэй солино: [1, 2, 3, 4]. 3 аль хэдийн байрандаа байгаа тул бэлэн.

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

Хамгийн энгийн санаа: хамгийн бага тоог олж эхэнд нь тавина. Дараа нь үлдсэн хэсгээс дахин хамгийн багыг нь олж хоёр дахь байранд тавина. Ингэж давтсаар бүх байрыг дүүргэнэ.

Хамгийн багыг олохын тулд mn гэсэн index хадгална. Араас нь байгаа тоо бүрийг a[mn]-тэй харьцуулаад, илүү бага нь гарвал mn-ийг шинэчилнэ. Pass дуусахад ганцхан swap хийнэ.

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

i
Одоо дүүргэж буй байр. Түүнээс зүүн талын хэсэг аль хэдийн эрэмбэлэгдсэн.
mn
Үлдсэн хэсэг дэх хамгийн бага тооны index. Утгыг нь биш, index-ийг нь хадгална.
pass
Гадна loop-ын нэг эргэлт. Pass бүр нэг тоог эцсийн байранд нь тавина.
swap(a[i], a[mn])
Олсон хамгийн бага тоог урд нь гаргана.

Эхэнд: 64 25 12 22 11. Хамгийн бага тоог олоод хамгийн урд тавина. Дараа нь үлдсэн тоонуудаас дахин хамгийн багыг нь хайна.

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

Хамгийн багыг нь урд нь

Ангийнхан өндрөөрөө жагсахад хамгийн намхан нь урд зогсдог. Selection Sort ч хамгийн бага тоог хайж олоод урд нь тавина.

selection-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++) {
int mn = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[mn]) {
mn = j;
}
}
swap(a[i], a[mn]);
}
for (int i = 0; i < n; i++) cout << a[i] << ' ';
return 0;
}

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

Тоонуудыг багаас нь их рүү эрэмбэлэх. "Хамгийн багыг нь олох" санаа олон бодлогод хэрэг болно. Swap цөөхөн, ердөө n − 1 удаа хийнэ.

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

1. i-р байранд орох тоог хайна. Эхлээд a[i]-г хамгийн бага гэж үзнэ: mn = i. 2. Араас нь байгаа тоо бүрийг a[mn]-тэй харьцуулна. Илүү бага нь олдвол mn = j. 3. Pass дуусахад a[i] ба a[mn] байраа солино. Хамгийн бага тоо байрандаа орлоо. 4. i = 0, 1, …, n − 2 гэж давтахад бүх тоо эрэмбэлэгдэнэ. Оролт: эхний мөрөнд n, дараагийн мөрөнд n тоо.

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

i дахь pass дуусахад a[i] нь үлдсэн тоонуудын хамгийн бага нь болно. Тэгэхээр эхний i + 1 тоо эрэмбэлэгдсэн, тэдгээр нь үлдсэн тоо бүрээс их биш. n - 1 pass-ын дараа сүүлийн тоо ч өөрөө байрандаа үлдэнэ.

Харьцуулалт үргэлж (n - 1) + (n - 2) + … + 1 = n(n - 1) / 2 удаа хийгдэнэ: хугацаа O(n²), нэмэлт санах ой O(1). n = 10 000 бол 50 сая орчим харьцуулалт. Харин swap ердөө n - 1 удаа хийгддэг нь давуу тал.

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

  • Дотор loop j = i + 1 гэж эхлэх ёстой. j = 0 гэж эхлүүлбэл аль хэдийн эрэмбэлсэн хэсгийг дахин хөндөж, бүгдийг эвдэнэ.
  • mn = a[j] гэж утгыг нь хадгалах. Тэгвэл swap(a[i], a[mn]) огт өөр байрыг солино. mn = j гэж index хадгална.
  • Swap-ыг дотор loop дотор хийх. Ингэвэл swap олширч, Selection Sort-ын давуу тал алга болно. Swap pass дууссаны дараа ганц удаа хийгдэнэ.
  • Selection Sort stable биш: swap хийхэд ижил хоёр тооны анхны дараалал солигдож болно.

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

  • n = 1: гадна loop огт ажиллахгүй, array хэвээрээ.
  • Аль хэдийн эрэмбэлэгдсэн: mn үргэлж i хэвээр үлдэж, тоо өөрийнхөө байранд үлдэнэ. Харьцуулалтын тоо өөрчлөгдөхгүй.
  • Бүх утга ижил: a[j] < a[mn] хэзээ ч үнэн болохгүй, юу ч хөдлөхгүй.
  • Урвуу эрэмбэтэй array: харьцуулалт мөн л n(n - 1) / 2. Selection Sort-д "амар" эсвэл "хүнд" оролт гэж байхгүй.

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

  1. Анхдагч жишээ [64, 25, 12, 22, 11] дээр эхний pass-ын дараа array ямар болох вэ?

    Хариу харах

    [11, 25, 12, 22, 64]. Хамгийн бага 11 нь 64-тэй байраа сольсон.

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

    Хариу харах

    15: 5 + 4 + 3 + 2 + 1.

  3. Хамгийн ихдээ хэдэн swap хийх вэ?

    Хариу харах

    n - 1. Pass бүрт яг нэг swap.

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

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

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

    Hint харах

    Pass бүрт үлдсэн хэсгийн хамгийн багыг олоод a[i]-тай соль.

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

    1-р pass: [1, 2, 4, 5, 3]. 2-р pass: өөрчлөлтгүй, 2 аль хэдийн байрандаа. 3-р pass: [1, 2, 3, 5, 4]. 4-р pass: [1, 2, 3, 4, 5].

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

    Hint харах

    Хамгийн багын оронд хамгийн ихийг хай.

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

    if (a[j] > a[mn]) болгоно. Тэгвэл mn нь хамгийн их тооны index болж, түүнийг урд нь тавина.

  3. 3.Array-н хамгийн бага k тоог өсөх дарааллаар нь хэвлэ (n ≤ 1000, k ≤ 10).

    Hint харах

    Бүтэн эрэмбэлэх шаардлагагүй. Хэдэн pass хангалттай вэ?

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

    Гадна loop-ыг i < k хүртэл л ажиллуулна. k pass-ын дараа эхний k байранд хамгийн бага k тоо өсөх дарааллаар байна. Ойролцоогоор k · n харьцуулалт.

Жишээ

Оролт

5
64 25 12 22 11

Гаралт

11 12 22 25 64

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

Бодлого

Хичээл

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