Тоо бүрийг зүүн талын эрэмбэлэгдсэн хэсэгт зөв байранд нь оруулдаг арга. Гартаа хөзөр эрэмбэлэхтэй адил.

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

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

a = [3, 1, 2] array-г эрэмбэлье. Эхний [3] хэсгийг эрэмбэлэгдсэн гэж үзнэ.

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

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

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

Эхний i тоо аль хэдийн эрэмбэлэгдсэн гэж үзье. Дараагийн тоог гартаа авна: x = a[i]. Зүүн тийш явж x-ээс их тоо бүрийг нэг байр баруун тийш шилжүүлнэ. x-ээс их биш тоонд хүрмэгц зогсоод, сул байранд x-ийг тавина.

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

x
Гартаа авсан тоо. Шилжүүлэх үед a[i] дарагдах тул тусад нь хадгална.
j
Зүүн тийш явж шалгаж буй index. j + 1 нь одоогийн сул байр.
эрэмбэлэгдсэн хэсэг
Array-н эхний i тоо. Алхам бүрт нэг тоогоор томорно.
stable
Ижил тоонуудын анхны дарааллыг хадгалдаг эрэмбэлэх арга. Insertion Sort stable.

Эхэнд: 12 11 13 5 6. Хөзөр эрэмбэлэхтэй адил: тоо бүрийг аваад, зүүн талын эрэмбэлэгдсэн хэсэгт зөв байранд нь оруулна.

Алхам 1 / 17
Хурд
  • Энгийн
  • Гартаа авсан тоо (x)
  • x-тэй харьцуулсан
  • Шилжсэн / тавьсан
  • Эрэмбэлэгдсэн хэсэг
Слайд 1 / 6

Хөзөр эрэмбэлэх шиг

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

insertion-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 = 1; i < n; i++) {
int x = a[i];
int j = i - 1;
while (j >= 0 && a[j] > x) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}
for (int i = 0; i < n; i++) cout << a[i] << ' ';
return 0;
}

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

Тоонуудыг багаас нь их рүү эрэмбэлэх. Бараг эрэмбэлэгдсэн array-д маш хурдан, ижил тоонуудын дарааллыг ч хадгалдаг.

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

1. Эхний тоог эрэмбэлэгдсэн хэсэг гэж үзнэ. 2. Дараагийн тоог гартаа авна: x = a[i]. 3. Зүүн талд нь x-ээс их тоо бүрийг нэг байр баруун тийш шилжүүлнэ. 4. Сул үлдсэн байранд x-ийг тавина. 5. Бүх тоонд ингэж давтана. Оролт: эхний мөрөнд n, дараагийн мөрөнд n тоо.

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

i дахь алхмын өмнө эхний i тоо эрэмбэлэгдсэн байна. x-ээс их тоонууд нэг байр баруун тийш шилжиж, x нь өөрөөсөө их биш тооны яг ард орно. Тэгэхээр эхний i + 1 тоо бас эрэмбэлэгдсэн болно.

Хамгийн муудаа (урвуу эрэмбэтэй үед) n(n - 1) / 2 шилжүүлэлт: хугацаа O(n²). Харин бараг эрэмбэлэгдсэн array дээр шилжүүлэлт цөөн тул бараг шугаман хугацаанд ажиллана. Шилжүүлэлтийн тоо яг inversion-ий тоотой тэнцүү. Нэмэлт санах ой O(1).

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

  • Гартаа авсан тоог x-д хадгалахаа мартвал эхний шилжүүлэлт a[i]-г дарж устгана.
  • while (a[j] > x && j >= 0) гэж дарааллыг нь солих. j = -1 үед a[-1]-г уншина. Эхлээд j >= 0 нөхцөлийг шалгана.
  • a[j] >= x гэж бичвэл ижил тоонуудыг дэмий шилжүүлж, stable биш болно.
  • Эцэст нь a[j] = x гэж бичих. Зөв нь a[j + 1] = x, учир нь loop дуусахад j нь x-ээс их биш тоон дээр зогссон.

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

  • n = 1: гадна loop ажиллахгүй.
  • Эрэмбэлэгдсэн array: нэг ч шилжүүлэлт хийхгүй, ердөө n - 1 харьцуулалт.
  • Урвуу эрэмбэтэй: тоо бүр хамгийн урд хүртэл явна, j нь -1 болж loop зогсоно.
  • Ижил утгууд: a[j] > x нөхцөл ижил тоог давахгүй тул дараалал хадгалагдана.

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

  1. [2, 3, 4, 1] дээр нийт хэдэн шилжүүлэлт хийх вэ?

    Хариу харах

    3. Зөвхөн 1 л гурван тоог давж урагшилна.

  2. Аль оролт дээр Insertion Sort хамгийн хурдан бэ?

    Хариу харах

    Аль хэдийн эрэмбэлэгдсэн array дээр. Тоо бүрт ганц харьцуулалт хийнэ.

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

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

  1. 1.Анхдагч жишээ [12, 11, 13, 5, 6] дээр i бүрийн дараах array-г бич.

    Hint харах

    i = 1 үеэс эхэлнэ. Гартаа авсан тоо зүүн тийш хэр хол явахыг хар.

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

    i = 1: [11, 12, 13, 5, 6]. i = 2: өөрчлөлтгүй. i = 3: [5, 11, 12, 13, 6]. i = 4: [5, 6, 11, 12, 13].

  2. 2.Нийт хэдэн шилжүүлэлт хийснийг тоолж хэвлэдэг болго.

    Hint харах

    Шилжүүлэлт зөвхөн while loop дотор хийгддэг.

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

    long long cnt = 0; зарлаад a[j + 1] = a[j]; мөрийн дараа cnt++; нэмнэ. Энэ тоо нь array дахь inversion-ий тоо. Анхдагч жишээнд 7.

  3. 3.Тоонууд нэг нэгээрээ ирнэ. Шинэ тоо ирэх бүрт одоогийн эрэмбэлэгдсэн жагсаалтыг хэвлэ (n ≤ 1000).

    Hint харах

    Шинэ ирсэн тоо бол яг гартаа авсан x.

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

    Тоог уншаад a[i]-д хийж, Insertion Sort-ын ганц алхмыг ажиллуулна. Тоо бүрт O(n), нийт O(n²). Тоо ирэх бүрт бүгдийг дахин эрэмбэлэхээс хурдан.

Жишээ

Оролт

5
12 11 13 5 6

Гаралт

5 6 11 12 13

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

Бодлого

Хичээл

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