Mustaqil ishi Mavzu : Ustuvor navbatlar

Algoritm	Ma’lumotlar tuzilmasi	Vaqt bo’yicha murakkabligi
Qo’shimcha ma’lumotlar
		Yaxshi	O’rta	Yomon	Yomon holatda
Tezkor saralash	Massiv	O(n log(n))	O(n log(n))	O(n^2)	O(n)
Surish orqali saralash	Massiv	O(n log(n))	O(n log(n))	O(n log(n))	O(n)
Piramidali saralash	Massiv	O(n log(n))	O(n log(n))	O(n log(n))	O(1)
Pufakchali saralash	Massiv	O(n)	O(n^2)	O(n^2)	O(1)
Qo’yish orqali saralash	Massiv	O(n)	O(n^2)	O(n^2)	O(1)
Tanlash orqali saralash	Massiv	O(n^2)	O(n^2)	O(n^2)	O(1)
Blokli saralash	Massiv	O(n+k)	O(n+k)	O(n^2)	O(nk)
Razryad bo’yicha saralash	Massiv	O(nk)	O(nk)	O(nk)	O(n+k)

Qidirish algoritmlari tahlili:

Algoritm	Ma’lumotlar tuzilmasi	Vaqt bo’yicha murakkablik		Xotira bo’yicha murakkabligi
		O’rta	Yomon	Yomon
Chuqurlik bo’yicha qidirish (DFS)	|V| tepalik va |E| bog’lovchili graf	-	O(|E|+|V|)	O(|V|)
Kenglik bo’yicha qidirish (BFS)	|V| tepalik va |E| bog’lovchili graf	-	O(|E|+|V|)	O(|V|)
Binar qidirish	n elementdan iborat saralangan massiv	O(log(n))	O(log(n))	O(1)
Chiziqli qidirish	Massiv	O(n)	O(n)	O(1)
Deykstraning algoritmi bo’yicha ustuvor navbatlar (двоичная куча)dan foydalangan holda qisqa masofani toppish	|V| tepalik va |E| bog’lovchili graf	O((|V|+|E|)log|V|)	O((|V|+|E|)log|V|)	O(|V|)
Deykstraning algoritmi bo’yicha ustuvor navbatlar sifatida massivdan foydalangan holda qisqa masofani toppish	|V| tepalik va |E| bog’lovchili graf	O(|V|^2)	O(|V|^2)	O(|V|)
Bellman-Ford algoritmidan foydalangan holda qisqa masofani topish	|V| tepalik va |E| bog’lovchili graf	O(|V| |E|)	O(|V| |E|)	O(|V|)

TOPSHIRIQ
1 – topshiriq.
Berilgan variant bo’yicha C++ (Python, Java) tilida har uchala saralash metodini bajaring va jadval shaklida solishtirib analiz qiling.
Birinchi topshiriq bo’yicha variantlar

Ro’yhat bo’yicha variant nomeri	Massivni to’ldirish	Saralash metodi	Har bir metod uchun massivdagi elementlarning soni
1,2,3	Tasodifiy elementlar bilan to’ldirilgan massiv	Sanash Pufakchali Shell	300	1200	4000
4,5,6	Tasodifiy elementlar bilan to’ldirilgan massiv	Surish Tezkor Tanlash	400	1300	4500
7,8,9	Tasodifiy elementlar bilan to’ldirilgan massiv	Pufakchali Tezkor Kiritish	200	1500	4000
10,11,12	Tasodifiy elementlar bilan to’ldirilgan massiv	Surish Sheyker Tezkor	500	1600	5000
13,14,15	Tasodifiy elementlar bilan to’ldirilgan massiv	O’rniga qo’yish Pufakchali Tanlash	350	2000	6000
16,17,18	Tasodifiy elementlar bilan to’ldirilgan massiv	Sheyker Tezkor Surish	450	1800	5500

Adabiyotlar ro’yhati:

1. 
   Абрамов С.А. Лекции о сложности алгоритмов.- М.: МЦНМО, 2009.- 256 с.
   
2. 
   Дональд Кнут Искусство программирования, том 1. Основные алгоритмы— 3-е изд. — М.: «Вильямс», 2006. — С. 720.
   
3. 
   Кнут В. Искусство программирования. Т.3. Сортировка и поиск. – 2-е изд. - Издательский дом “Вильямс”, 2000.
   
4. 
   Вирт Н. Алгоритмы и структуры данных. Пер. с англ. – М.: Мир, 1989. – 360.
   
5. 
   Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992.
   

Xulosa:
Ustuvor navbat - bu har bir element ustuvorlik bilan bog'liq bo'lgan va uning ustuvorligiga muvofiq xizmat ko'rsatadigan navbatning maxsus turi. Agar bir xil ustuvorlikka ega elementlar yuzaga kelsa, ular navbatdagi navbatga muvofiq xizmat ko'rsatiladi.

Odatda ustunlikni belgilash uchun elementning o'zi hisobga olinadi.
Masalan, eng yuqori qiymatga ega element eng yuqori ustuvor element sifatida qabul qilinadi. Ammo, boshqa holatlarda, biz eng past ustuvor element sifatida eng past qiymatga ega elementni qabul qilishimiz mumkin. Boshqa hollarda, biz ehtiyojlarimizga qarab ustuvor vazifalarni belgilashimiz mumkin.