Juda ham katta sonlar bilan ishlash 8 mavzu

Taroqsimon caralash (Comb sort).

• Shaker saralashning yana bir o‘zgartirilgani. "Toshbaqalar" dan qutulish uchun masofada turgan elementlarni qayta tashkil qilamiz. Keling, uni tuzatamiz va chapdan o‘ngga boramiz, bu masofada turgan elementlarni taqqoslaymiz, agar kerak bo‘lsa, ularni qayta tartibga solaylik. Shubhasiz, bu "toshbaqalar"ni tez qator boshiga olish imkonini beradi. Dastlab qator uzunligiga teng masofani olib, so‘ngra uni taxminan 1.247 ga teng bo‘lgan biror koeffitsientga bo‘lish maqbuldir. Masofa bir biriga teng bo‘lganda shaker saralash bajariladi. Eng yaxshisi, murakkabligi O(nlogn), eng yomoni, u O(n2). O‘rtacha murakkabligi nima uchun juda aniqmas, amalda O(nlogn) kabi ko‘rinadi.

• void combsort(int* l, int* r) {
• int sz = r - l;
• if (sz <= 1) return;
• double k = 1.2473309;
• int step = sz - 1;
• while (step > 1) {
• for (int* i = l; i + step < r; i++) {
• if (*i > *(i + step))
• swap(*i, *(i + step));
• }
• step /= k;
• }
• 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;}}}}

Qo‘shish orqali saralash (Insertion sort).

• Algoritm yakunlangandan keyin javobni o‘z ichiga olgan bir yangi massiv yaratiladi. Javob massividagi elementlar har doim tartiblanib turishi uchun manba massividan elementlarni birma-bir kiritamiz. Murakkabligi o‘rtacha va eng yomon hol O(n2) va eng yaxshi O(n) bo‘ladi. Boshqa algoritmlarga nisbattan joriy qilish yaxshiroq (yangi massiv yaratish va albatta u nimanidir qo‘yish qiyin): joriy massivning ba’zi bir prefikslari tartiblashtirilganiga ishonch hosil qilish va modomiki ular noto‘g‘ri tartibda ekan uni kiritish o‘rniga joriy elementni avvalgisi bilan o‘zgartiramiz.

• void insertionsort(int* l, int* r) {
• for (int *i = l + 1; i < r; i++) {
• int* j = i;
• while (j > l && *(j - 1) > *j) {
• swap(*(j - 1), *j);
• j--;
• }
• }
• }