Misol:
#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 <= 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(nlong(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;
}
Xulosa
Saralash informatika fanida muhim operatsiya bo'lib, har xil turdagi tartiblash algoritmlari mavjud. Taqqoslashga asoslangan saralash algoritmlari, masalan, qabariqni saralash, tanlashda saralash, qo‘shishni saralash, birlashtirish, tez tartiblash va yig‘ish tartiblash, belgilangan taqqoslash funksiyasi asosida elementlarni solishtirish va almashtirishga tayanadi. Bu algoritmlar turli vaqt murakkabligiga ega, baʼzilarida eng yomon vaqt murakkabligi O(n^2) va boshqalarida eng yomon vaqt murakkabligi O(n log n) ga ega.Taqqoslashsiz saralash algoritmlari, masalan, Hisoblash va Radix Saralash, elementlarni taqqoslashga tayanmasdan, boshqacha yondashuvni qo'llaydi. Counting Sort har bir elementning takrorlanishini hisoblaydi va ularni tartibda joylashtiradi, Radix Sort esa elementlarni raqamlariga qarab tartiblaydi.Saralash algoritmlarining samaradorligi muhim ahamiyatga ega. Algoritmlarning samaradorligini baholash uchun vaqt murakkabligidan foydalaniladi va kamroq vaqt murakkabligi bo'lgan algoritmlar odatda samaraliroqdir. Biroq, maʼlumotlar toʻplamining hajmi va taqsimoti, mavjud xotira va ilovaning oʻziga xos talablari kabi boshqa omillarni ham hisobga olish muhim. Xulosa qilib aytganda, saralash algoritmini tanlash saralanadigan ma'lumotlarning o'ziga xos ehtiyojlari va xususiyatlariga bog'liq. Saralash algoritmlarining har xil turlarini va ularning samaradorligini tushunish muayyan stsenariy uchun eng mos algoritmni tanlashda yordam beradi.
Foydalanilgan adabiyotlar:
1.[EN] Adam Drozdek. Data structures and algorithms in C++. Fourth edition.Cengage Learning, 2013.
2.[UZ] Narzullaev U.X., Qarshiev A.B., Boynazarov I.M. Ma’lumotlar tuzilmasi va algoritmlar. //O’quv qo’llanma. Toshkent: Tafakkur nashriyoti, 2013 y. – 192 b.
3.[UZ] Boynazarov I.M., To’xtayeva M.Sh. Ma’lumotlar tuzilmasi fanidan mustaqil ishlarni bajarish uchun uslubiy ko’rsatma. -Samarqand, TATU Samarqand filiali, 2018 y. 53 bet.
4.[RU] Алфред В. Ахо., Джон Э. Хопкрофт, Джефри Д. Ульман. Структура данных и алгоритмы. //Учеб.пос., М.: Изд.дом: "Вильямс", 2000, — 384 с.
5.[RU] Лойко В.И. Структуры и алгоритмы обработки данных. Учебное пособие для вузов. - Краснодар: КубГАУ. 2000. - 261 с., ил.
|
