Тоо бүр хэдэн удаа байгааг тоолоод, багаас нь эхлэн тоолсон ёсоор нь хэвлэдэг харьцуулалтгүй эрэмбэлэлт.

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

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

a = [3, 1, 3, 0, 1] array-г эрэмбэлье. Тоо бүр хэдэн удаа байгааг тоолбол: 0 нэг удаа, 1 хоёр удаа, 2 огт байхгүй, 3 хоёр удаа.

Одоо 0-ээс эхлээд тоо бүрийг тоолсон ёсоор нь хэвлэнэ: 0 1 1 3 3. Нэг ч харьцуулалт хийсэнгүй.

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

Ердийн эрэмбэлэх аргууд тоонуудыг хооронд нь харьцуулдаг. Ийм аргууд n log n орчим алхмаас цөөн алхамд эрэмбэлж чаддаггүй. Гэтэл утга нь бага (жишээ нь 1 000 000 хүртэл) бол харьцуулах огт хэрэггүй.

c[v] нь v гэсэн тоо хэдэн удаа байгааг хадгална. Эхлээд тоо бүрээр c[a[i]]++ хийнэ. Дараа нь v = 0, 1, 2, … гэж явж, v-г c[v] удаа хэвлэнэ. Багаас нь эхэлж явсан тул хэвлэсэн тоонууд өөрөө эрэмбэлэгдсэн байна.

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

c
Тоолох array. c[v] нь v хэдэн удаа гарсныг заана. Хэмжээ нь хамгийн их утгаас нэгээр их.
v
Хэвлэж буй утга. 0-ээс хамгийн их утга хүртэл явна.
k
Утгын хүрээ. Энэ кодод утга 1 000 000 хүртэл.
a
4
0
2
1
2
2
8
3
3
4
3
5
1
6
c
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
хэвлэсэн

Эхэнд: 4 2 2 8 3 3 1. Тоо бүр хэдэн удаа байгааг c-д тоолно. Дараа нь багаас нь эхлээд тоолсон ёсоор нь хэвлэнэ.

Алхам 1 / 15
Хурд
  • Тоолж буй тоо
  • Сая нэмэгдсэн / хэвлэсэн
  • Хэвлэж буй утга (v)
  • Тоолсон / хэвлэсэн
  • Дууссан нүд
Слайд 1 / 6

Тоолоод л болно

Ангийнхнаасаа насыг нь асуугаад нас бүрээр тоолбол жагсаалт шууд гарна. Counting Sort харьцуулдаггүй, зүгээр л тоолдог.

counting-sort.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a[100005], c[1000005];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {
c[a[i]]++;
}
for (int v = 0; v <= 1000000; v++) {
while (c[v] > 0) {
c[v]--;
cout << v << ' ';
}
}
return 0;
}

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

Утга нь бага (жишээ нь 1 000 000 хүртэл) олон тоог маш хурдан эрэмбэлэх. Тоолох санаа олимпиадын олон бодлогод хэрэг болно.

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

1. c[v] нь v гэсэн тоо хэдэн удаа байгааг тоолох нүд. Эхэндээ бүгд 0. 2. a доторх тоо бүрт c[a[i]] нэгээр нэмэгдэнэ. 3. v = 0, 1, 2 … гэж багаас нь явна. c[v] хэд байна, v-г төдий удаа хэвлэнэ. Оролт: эхний мөрөнд n, дараагийн мөрөнд 0-ээс 1 000 000 хүртэлх n тоо.

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

Тоо бүр яг c[v] удаа хэвлэгдэнэ, тэгэхээр хариунд бүх тоо байна. v өсөх дарааллаар явдаг тул бага тоо үргэлж урд нь хэвлэгдэнэ.

Тоолоход n алхам, хэвлэхэд k + n алхам: хугацаа O(n + k), нэмэлт санах ой O(k). n = 100 000, k = 1 000 000 бол 1.1 сая орчим алхам. Харин утга 10⁹ хүртэл бол c санах ойд багтахгүй.

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

  • Сөрөг тоо: c[-5] гэж array-гээс гадуур бичнэ. Бүх тоонд ижил тоо нэмж эерэг болгоод, хэвлэхдээ буцааж хас.
  • c-г хэтэрхий жижиг зарлах. c[1000000] хэрэгтэй бол хэмжээ нь дор хаяж 1 000 001 байна.
  • Том c-г main дотор зарлах. Ийм local array stack-д багтахгүй. Global зарлавал бас бүх утга 0-ээр эхэлнэ.
  • Утгын хүрээ их (жишээ нь 10⁹ хүртэл) үед Counting Sort тохирохгүй, sort() ашигла.

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

  • n = 1: нэг тоо тоологдож, нэг удаа хэвлэгдэнэ.
  • Бүх утга ижил: ганц нүд n болж, тэр тоо n удаа хэвлэгдэнэ.
  • Утгууд хоорондоо хол: хоосон нүднүүдийг алгасна, гэхдээ v хамгийн их утга хүртэл явсаар байна.
  • Утга 0: c[0] ч ажиллана, 0 хамгийн түрүүнд хэвлэгдэнэ.

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

  1. Анхдагч жишээ [4, 2, 2, 8, 3, 3, 1] дээр тоолж дуусахад c[3] хэд байх вэ?

    Хариу харах

    2. 3 гэсэн тоо хоёр удаа гарсан.

  2. Яагаад тоонуудыг хооронд нь харьцуулах шаардлагагүй вэ?

    Хариу харах

    v-г багаас нь их рүү гүйлгэдэг тул хэвлэх дараалал өөрөө эрэмбэтэй.

  3. n = 10, утга нь 0-ээс 10⁹ хүртэл бол яагаад тохирохгүй вэ?

    Хариу харах

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

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

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

  1. 1.Array [5, 0, 2, 5, 2, 2] дээр тоолж дуусахад c[0], c[1], …, c[5] ямар утгатай болох вэ? Юу хэвлэгдэх вэ?

    Hint харах

    Тоо бүр хэдэн удаа байгааг л тоол.

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

    c = [1, 0, 3, 0, 0, 2]. Хэвлэгдэх нь 0 2 2 2 5 5.

  2. 2.Тоонууд -1000-аас 1000 хүртэл байж болно. Кодыг өөрчил.

    Hint харах

    Тоо бүрт ижил тоо нэмбэл бүгд эерэг болно.

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

    Тоолохдоо c[a[i] + 1000]++. Хэвлэхдээ v = 0 … 2000 гэж явж, cout << v - 1000 гэж хэвлэнэ.

  3. 3.n ≤ 100 000 сурагчийн оноо (0–100) өгөгдсөн. Хамгийн олон сурагчийн авсан оноог ол.

    Hint харах

    Эрэмбэлэхгүй ч c array өөрөө хариуг өгнө.

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

    c[v] нь яг v оноо авсан сурагчийн тоо. c[0], …, c[100] дундаас хамгийн их утгатайг нь олоод v-г хэвлэнэ. O(n + 101).

Жишээ

Оролт

7
4 2 2 8 3 3 1

Гаралт

1 2 2 3 3 4 8

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

Бодлого

Хичээл

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