tezkor saralash algoritmi (quick sort)

DOCX 1 sahifa 341,0 KB Bepul yuklash

1 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 341,0 KB

Fayl turi DOCX

Sahifalar 1

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 1

5-laboratoriya ishi. mavzu: tezkor saralash algoritmi(quick sort). · bu algoritm 1964 yilda charlz hoar tamonidan taklif qilingan. charlz hoar ingliz olimi, informatika va hisoblash texnikasi sohasida yetuk mutaxassis. uning “tezkor saralash” algoritmi saralash bo’yicha eng ommobop algoritm. · bu algoritm ham “bo’lib tashla va hukmronlik qil” metodiga asoslanadi. algoritmning g’oyasi: · massivda bo’luvchi element x tanlanadi. · elementlarni shunday joylashtiramizki, dastlab x dan kichik yoki teng bo’lgan elementlar joylashsin, keyin undan katta bo’lgan elementlar joylashsin. · natijada chap tamonda barcha kichik elementlar, o’ng tamonda esa barcha katta sonlar joylashib qoladi. bu qismlarning endi bir-biriga aloqasi yo’q. keyin ularni alohida saralaymiz. bu jarayon rekursiv jarayon bo’ladi. · [l, r] saralanishi kerak bo’lgan kesma. · m = (l+r) / 2 – bu kesmanig o’rtasi. · x=a[m] - bo’luvchi element. ya’ni uni o’rtasidan tanlab olamiz. keyin quyidagi amallarni bajaramiz: · chap tamondan x dan katta yoki teng bo’lgan birinchi elementni topamiz. · o’ng …

2 / 1

ilgan interval ikkita qismga ajralib qoldi: [l, j] va [i,r] intervallar. bu qismlarning bir-biriga aloqasi yo’q, chunki o’ng tamondagi barcha sonlar chap tamondagi barcha sonlardan katta(aniqrog’i kichik emas). endi bu qismlarni huddi shunday jarayon bo’yicha saralashni davom ettirish mumkin. buni amalaga oshirish uchun eng yaxshi usul bu rekursiv usuldan foydalanish. [l, r] ni saralash kerak bo’lgan masala undan kichikroq ikkita masalaga [l, j] va [i,r] intervallarni saralashga keltirldi. bu esa bo’lib tashla va hukmronlik qil metodi deb nomlanadi. algoritmning c++ dagi kodini keltiramiz: #include using namespace std; int a[100001]; void qsort(int l, int r) { int m = (l+r) / 2; int x = a[m]; int i = l; int j = r; while (i x) j--; if (i >n; for (int i = 0; i >a[i]; qsort(0, n-1); for (int i = 0; i · #include · using namespace std; · int main() { · int n; · cin>>n; …

3 / 1

eriladi. ularning qiymatlari butun va modul jihatidan 106 dan oshmaydi. chiquvchi ma’lumotlar bitta butun sonni – maksimal ko’paytmaning qiymatini chiqaring. misollar № kiruvchi ma’lumotlar chiquvchi ma’lumotlar 1 5 5 6 -9 4 3 120 2 3 -5 -7 -2 -70 2-topshiriq sizga bir o’lchamli massiv berilgan. sizning vazifangiz unda nechta har xil sonlarqatnashganligi topishdan iborat. kiruvchi ma’lumotlar birinchi qatorda butun son n−massiv elementlari soni berilgan(1≤n≤105). ikkinchiqatorda massiv elementlari bitta probel bilan ajratilib berilgan. massiv elementlari butunva modul jihatdan 109 dan oshmaydi. chiquvchi ma’lumotlar birinchi qatorda bitta sonni – so’ralgan sonni chiqaring. misollar № kiruvchi ma’lumotlar chiquvchi ma’lumotlar 1 1 5 1 2 5 8 -7 7 8 -7 3 3 3 3 3 1 2 3-topshiriq s sart berilgan. s satrning qism satrlari deb barcha 0≤i≤j≤n-1 (bu yerda n − s satrninguzunligi)juftliklar uchun si…sj lardan tuzilgan satrlarga aytiladi. masalan aab satrningqism satrlari: a, aa, aab, a, ab, b. sizning vazifangiz …

4 / 1

hanchi sonni chiqarish kerakliginiifodalovchi ki sonidan iborat(1≤ ki ≤n). chiquvchi ma’lumotlar dastlabki q ta satrda har bir so’rovga javobni ular berilish tartibida chiqaring. misollar № kiruvchi ma’lumotlar chiquvchi ma’lumotlar 1 10 7 8 4 7 10 5 7 1 5 3 6 847 227 427 19 227 91 319 5-topshiriq elementlari soni n ta, 1 dan boshlab indekslangan bir o’lchamli massiv quyidagiformula bilan aniqlangan: ai = (b∙i2+c∙i+d) mod 2147483647; bu yerda “mod” amali qoldiq hisoblanadi. sizning vazifangiz bu massiv elentlarinikamaymaslik tartibda saralangandan xolatdagi k-o’rinda turan elementi qiymatinitopishdan iborat. kiruvchi ma’lumotlar birinchi qatorda n va k butun sonlari berilgan(1≤k≤n≤107). ikkinchi qatorda b, c, d butun sonlari bitta probel bilan ajratib berilgan(1≤b,c,d ≤104). chiquvchi ma’lumotlar birinchi qatorda masalaning javobini chiqaring. misollar № kiruvchi ma’lumotlar chiquvchi ma’lumotlar 1 10 6 8 4 7 319 6-topshiriq the word is an anagram of another word, if it can be obtained by rearrangement of its letters. …

5 / 1

’g’ri chiziqustma-ust tushsa ular bitta to’g’ri chiziq hisoblanadi. nechta har xil to’g’ri chiziqborligini toping. kiruvchi ma’lumotlar birinchi qatorda bitta butun son n – to’g’ri chiziqlar soni berilgan(1≤n≤50000).keyingi n ta qatorda har birida to’rttadan son – navbatdagi to’g’ri chiziqqa tegishlibo’lgan ikki nuqta koordinatalari x1, y1, x2, y2 sonlari bitta probel bilan ajratibberilgan(bu nuqtalar ustma-ust tushmaydi). koordinatalar butun va mudul jihatdan 104dan oshmaydi. chiquvchi ma’lumotlar birinchi qatorda bitta sonni – nechta har xil to’g’ri chiziq borligini chiqaring. misollar № kiruvchi ma’lumotlar chiquvchi ma’lumotlar 1 4 -1 -1 2 2 6 6 9 9 -1 2 2 5 0 0 7 8 3 9-topshiriq for each three prime numbers p1, p2 and p3, let’s define hamming sequence hi(p1,p2, p3), i=1,… as containing in increasing order all the natural numbers whose only prime divisors are p1, p2 or p3. for example, h(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, …

Ko'proq o'qimoqchimisiz?

Barcha 1 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"tezkor saralash algoritmi (quick sort)" haqida

5-laboratoriya ishi. mavzu: tezkor saralash algoritmi(quick sort). · bu algoritm 1964 yilda charlz hoar tamonidan taklif qilingan. charlz hoar ingliz olimi, informatika va hisoblash texnikasi sohasida yetuk mutaxassis. uning “tezkor saralash” algoritmi saralash bo’yicha eng ommobop algoritm. · bu algoritm ham “bo’lib tashla va hukmronlik qil” metodiga asoslanadi. algoritmning g’oyasi: · massivda bo’luvchi element x tanlanadi. · elementlarni shunday joylashtiramizki, dastlab x dan kichik yoki teng bo’lgan elementlar joylashsin, keyin undan katta bo’lgan elementlar joylashsin. · natijada chap tamonda barcha kichik elementlar, o’ng tamonda esa barcha katta sonlar joylashib qoladi. bu qismlarning endi bir-biriga aloqasi yo’q. keyin ularni alohida saralaymiz. bu jarayon rekursiv jarayon bo’ladi...

Bu fayl DOCX formatida 1 sahifadan iborat (341,0 KB). "tezkor saralash algoritmi (quick sort)"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: tezkor saralash algoritmi (quic… DOCX 1 sahifa Bepul yuklash Telegram