Juda ham katta sonlar bilan ishlash 8 mavzu

Havo sharcha kabi saralash (Bubble sort).

• Massivda chapdan o‘ngga qarab amal bajariladi. Agar joriy element keyingisidan katta bo‘lsa, ularni almashtiramiz. Buni massiv tartiblanmaguncha bajaramiz. E’tibor bering, birinchi iterasiyadan keyin eng katta element massivning oxirida, to‘g‘ri joylashagan bo‘ladi. Ikkita iterasiyadan keyin ikkinchi eng katta element to‘g‘ri joylashgan bo‘ladi va hokazo. Ravshanki, n ta iterasiyadan ko‘p bo‘lmagandan keyin massiv tartiblangan bo‘ladi. Shunday qilib, eng yomon va o‘rtacha holatda murakkabligi O(n2), eng yaxshi holatda esa O(n) bo‘ladi.

• void bubblesort(int* l, int* r) {
• int sz = r - l;
• if (sz <= 1) return;
• bool b = true;
• while (b) { b = false;
• for (int* i = l; i + 1 < r; i++) {
• if (*i > *(i + 1)) {
• swap(*i, *(i + 1));
• b = true;}
• }
• r--;}

Shaker saralash (Shaker sort).

• Havo sharcha saralash oxirida kichik elementlar joylashtirilgan testlarda sekin ishlaydi (ba’zan "tashboqa" deb ataladi). Bu element algoritmning har bir qadamida chap tomonga faqat bitta pozitsiyaga harakat qiladi. Shuning uchun nafaqat chapdan o‘ngga, balki o‘ngdan chapga ham o‘tadi. Massivning tartiblanmagan qismini aniqlash uchun ikkita begin va end ko‘rsatikichni qo‘llab quvvatlaydi. Keyingi iterasiyada endga yetganimizda undan birini ayiramiz va o‘ngdan chapga ko‘chamiz. Xuddi shunday, beginga yetganimizda unga birini qo‘shamiz va chapdan o‘ngga ko‘chamiz . Algoritm havo sharcha saralash bilan bir xil murakkabligi bor, lekin real vaqtda yaxshi ishlaydi.

• void shakersort(int* l, int* r) {
• int sz = r - l; if (sz <= 1) return;
• bool b = true;
• int* beg = l - 1;
• int* end = r - 1;
• while (b) { b = false;
• beg++;
• for (int* i = beg; i < end; i++) {
• if (*i > *(i + 1)) {
• swap(*i, *(i + 1));
• b = true;}}
• if (!b) break; end--;
• for (int* i = end; i >
• beg; i--) {
• if (*i < *(i - 1)) {
• swap(*i, *(i - 1));
• b = true;}}}}