Saralash tushunchasiga kirish - Musobaqaviy dasturlash uchun C++ dasturlash tili

Modul 1: Dasturlashga kirish

Dasturlash nima?
Nega bizga dasturlash kerak?
Dasturlash muhitini sozlash

Modul 2: Birinchi dasturingiz

Hello World dasturi
Dastur tuzilishi
Masalalar

Modul 3: Kiritish/chiqarish va arifmetik operatorlar

Ma'lumotlarni kiritish/chiqarish
Arifmetik operatorlar
Masalalar

Modul 4: Shartli operatorlar

Taqqoslash operatorlari
Shart operatorlari
Masalalar
Masalalar

Modul 5: Ma'lumot turlari

Ma'lumot turlari
Masalalar
Masalalar
Masalalar
Masalalar

Modul 6: Takrorlash operatorlari

For sikli
While sikli
Masalalar
Masalalar
Masalalar
Masalalar

Modul 7: Massivlar

Massiv ta'rifi
Ko'p o'lchamli massivlar
Masalalar
Masalalar

Modul 8: Funksiyalar

Funksiya
Mash qilish uchun masalalar

Modul 9: Ichma-ich sikllar va ko'p o'lchamli massiv

Ichma-ich sikllar va ko‘p o‘lchovli massivlar
Mashq qilish uchun masalalar

Modul 10: Chiziqli qidiruv

Chiziqli qidiruv
Masalalar

Modul 11: STL ma'lumot tuzilmalari 1

STL ma'lumot tuzilmalari
Masalalar

Modul 12: Sodda saralash algoritmlari

Saralash tushunchasiga kirish
Bubble Sort
Selection Sort
Insertion Sort
Masalalar

Modul 13: STL ma'lumot tuzilmalari 1

STL ma'lumot tuzilmalari: set va map
Masalalar

Module 14: Brute-forces

Bruteforce'ga kirish
Masalalar

Module 15: Recursion

Rekursiyaga kirish
Masalalar

Module 16: Structs in C++

Structs

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Courses/Musobaqaviy dasturlash uchun C++ dasturlash tili/Modul 12: Sodda saralash algoritmlari/Saralash tushunchasiga kirish

Saralash tushunchasiga kirish

Saralash tushunchasiga kirish

Saralash algoritmlariga kirish

Saralash algoritmlari - bu ma'lumotlarni ma'lum tartibda (odatda o'sish yoki kamayish tartibida) joylashtirish uchun ishlatiladigan usullar.

Keling, klassik masala bayonini ko'rib chiqamiz:

$N$ ta elementdan iborat $A$ massiv berilgan. Ularni shunday qayta joylashtiringki, $A[1] \leq A[2] \leq \ldots \leq A[N]$ bo'lsin (yoki kamayish tartibida).

To'g'ri yechim quyidagilarni bajarishi kerak:

Up next

Bubble Sort

Bubble sort algoritmi

Elementlarni qayta tartiblashi (qiymatlarini o'zgartirmasligi)

To'liq saralangan ketma-ketlik hosil qilishi

Buni to'g'ri bajarishi va imkon qadar samarali bo'lishi

Saralash algoritmlari qayerda foydali

Saralash kompyuter fanida asosiy vosita hisoblanadi va ko'plab real vazifalarda uchraydi:

Binary search saralangan ma'lumotni talab qiladi
Ko'plab dinamik dasturlash va greedy algoritmlar avval saralaydi
Talabalarni ballari bo'yicha reyting qilish
Dublikatlarni aniqlash (saralangandan keyin teng elementlar yonma-yon turadi)
Nuqtalarni x-koordinatasi bo'yicha saralash
Qirralarni og'irligi bo'yicha saralash (masalan, Kruskal MST algoritmida)
Vazifalarni deadline yoki davomiyligi bo'yicha saralash

Sodda saralash algoritmlari

Bubble Sort — qo'shni elementlar noto'g'ri tartibda bo'lsa, ularni joyini almashtiradi.
Selection Sort — eng kichik elementni tanlab, to'g'ri joyiga qo'yadi.
Insertion Sort — har bir elementni saralangan prefiksdagi to'g'ri joyiga kiritadi.