Saralash algoritmlari. Saralashning yaxshilangan usullari. Tez saralash (Quick sort) saralash usuli

Misol:

#include

using namespace std;

int a[100001];

void qsort(int L, int R) {

int m = (L+R) / 2;

int X = a[m];

inti = L;

int j = R;

while (i<= j) {

while (a[i] < X) i++;

while (a[j] > X) j--;

if (i<= j) {

int t = a[i]; a[i] = a[j]; a[j] = t;

i++;

j--;

}

}

if (L < j) qsort(L, j);

if (i < R) qsort(i, R);

}

int main() {

int n;

cin>>n;

for (int i = 0; i < n; i++)

cin>>a[i];

qsort(0, n-1);

for (int i = 0; i < n; i++)

cout<

return 0;

}

Agar bo’luvchi elementni o’rtadan emas, balki [L, R] kesmadan ixtiyoriy tanlab olinsa ishlash vaqti O(n*long(n)).

C++ dasturlash tilida saralash.

C++ da saralash juda oddiy Quick Sort bo’yicha saralaydi:

#include

#include

using namespace std;

int main() {

int n;

cin>>n;

int a[n];

for (int i = 0; i < n; i++)

cin>>a[i];

sort(a, a+n);

for (int i = 0; i < n; i++)

cout<

return 0;

}

Men bu mustaqil ish davomida yuqoridagi saralash algoritmlarini o’rganib chiqdim. O’rganishlarim davomida saralash algoritmlarining asosiy farqi ularning bajarilish vaqti va xotiradan joy egallashi jihatidan bir-biridan farqlanishini o’rgandim. Misol uchun: Pufakcha orqali saralash (bouble sort) algoritmi vaqt jihatidan qolgan algoritmlarga nisbatan sekin ishlaydi. Uning ishlash vaqti O (n²/2) ga teng. Bu ko’rsatgich Tezkor saralsh (quick sort) algoritmida O (n*log n) gat eng. Xotiraga kelsak bouble, selection saralash algoritmlarida yangi massiv e’lon qilish shart emas. Merge saralsh algoritmida hotiradan yuqoridagilarga qaraganda ikki barobar yutqazamiz. Merge saralash algoritmida xotiradan yutish uchun lincked list dan foydalanilsa xotira jihatdan ham vaqt jihatdan ham yutishni imkonini beradi.

Foydalanilgan adabiyotlar:

Fayllar.uz

Arxiv.uz

Algoritm.uz va boshqa adabiyotlar.