Бажарди: 2 – курс талабаси мултимедиа технология факултети

Shell caralash (Shellsort).

1 variyant

void shellsort(int* l, int* r) {
int sz = r - l;
int step = sz / 2;
while (step >= 1) {
for (int *i = l + step; i < r; i++) {
int *j = i;
int *diff = j - step;
while (diff >= l && *diff > *j) {
swap(*diff, *j);
j = diff;
diff = j - step;
}
}
step /= 2;
}
}

2 variyant

void shellsorthib(int* l, int* r) {
int sz = r - l;
if (sz <= 1) return;
int step = 1;
while (step < sz) step <<= 1;
step >>= 1;
step--;
while (step >= 1) {
for (int *i = l + step; i < r; i++) {
int *j = i;
int *diff = j - step;
while (diff >= l && *diff > *j) {
swap(*diff, *j);
j = diff;
diff = j - step;
} }
step /= 2;}}
Tanlash orqali saralash (Selection sort)
Navbatdagi iterasiya bo‘yicha massivdagi minimumni joriy elementdan keyin topamiz va kerak bo‘lsa u bilan o‘zgartiramiz. Shunday qilib, i-iterasiyadan keyin birinchi i elementlar o‘z joylarida qoladi. murakkabligi eng yaxshi, o‘rtacha va eng yomon holatlarda O(n²). Bu saralashni ikki yo‘l bilan amalga oshirilishi mumkinligini unutmang - minimal va uning indeks tutib, yoki shunchaki ular noto‘g‘ri tartibda bo‘lsa, ko‘rib chiqilayotgan va joriy element o‘rin almashtirish kerak. Birinchi usul bir oz tezroq.
void selectionsort(int* l, int* r) {
for (int *i = l; i < r; i++) {
int minz = *i, *ind = i;
for (int *j = i + 1; j < r; j++) {
if (*j < minz) minz = *j, ind = j;
} swap(*i, *ind);
}}