Алгоритмын сан
Хоёр алгоритмыг нэг ижил тоонууд дээр зэрэг гүйлгээд аль нь түрүүлж дуусахыг хараарай. Аль нь цөөн харьцуулалт хийнэ, тэр нь ялна.
Quick Sort
Дунджаар O(n log n)
8
3
5
1
9
2
7
4
0
1
2
3
4
5
6
7
- Алхам
- 1/30
- Харьцуулалт
- 0
- Солилт/бичилт
- 0
Эхэнд: 8 3 5 1 9 2 7 4. Нэг тоог pivot болгоно. Түүнээс бага тоонуудыг зүүн тийш, бусдыг нь баруун тийш хуваана.
Merge Sort
O(n log n)
8
3
5
1
9
2
7
4
0
1
2
3
4
5
6
7
- Алхам
- 1/40
- Харьцуулалт
- 0
- Солилт/бичилт
- 0
Эхэнд: 8 3 5 1 9 2 7 4. Array-г хоёр хувааж, хэсэг бүрийг эрэмбэлээд, буцааж нийлүүлнэ.
Алхам 1 / 40
Хурд
- Space тоглуулах
- ←→ алхам
- −+ хурд
- Энгийн
- Pivot (p)
- p-тэй харьцуулж буй
- Солигдсон
- Байрандаа орсон
- Одоогийн хэсгээс гадуур
Цөөн харьцуулалт хийсэн нь ялна, тэнцвэл бичилт цөөтэй нь. Алгоритмын хурдыг яг ингэж хэмждэг юм. «Урвуу», «Эрэмбэлэгдсэн» жишээн дээр ялгаа нь илүү тод харагдана.