Ma’lumotlarni saralash. Saralashning birlashtirish (sliyanie) usuli
![Ushbu jadvalda, n saralanadigan yozuvlar soni. "O'rtacha" va "Eng yomoni"
ustunlari quyidagilarni beradi vaqtning murakkabligi har bir holda, har bir
tugmachaning uzunligi doimiy va shuning uchun barcha taqqoslashlar,
almashtirishlar va boshqa kerakli operatsiyalar doimiy vaqt ichida davom etishi
mumkin degan taxmin ostida. "Xotira", xuddi shu taxmin asosida, ro'yxatning o'zi
ishlatadigan hajmdan tashqarida zarur bo'lgan qo'shimcha saqlash hajmini
bildiradi. Ishlash vaqtlari va quyida keltirilgan xotira talablari uning ichida bo'lishi
kerak katta O yozuvlari , shuning uchun logarifmlarning asosi muhim emas;
yozuv jurnal 2
n degani (log n ) 2
.
Taqqoslash turlari
Quyida jadval mavjud taqqoslash turlari . Taqqoslash tartibini quyidagidan ko'ra
yaxshiroq bajarish mumkin emas O ( n jurnal n ). [4]
Taqqoslash turlari
Ism Eng
yaxs
hi O'rtac
ha Eng
yomoni Xoti
ra Barqa
ror Usul Boshqa eslatmalar
Quicksort Yo'q Bo'linish Quicksort odatda
joyida amalga
oshiriladi O (log n ) b
o'sh joy. [5] [6]
Saralashni
birlashtirish n Ha Birlashti
rish Juda
parallel (qadar O (lo
g n ) Uch venger
algoritmi
yordamida). [7]
Joyda birlashma
saralash — — 1 Ha Birlashti
rish O'z o'rnida barqaror
birlashishga
asoslangan barqaror
tur sifatida amalga
oshirilishi mumkin.
[8]
Introsort Yo'q Partition
ing &
Selectio
n Bir nechtasida
ishlatiladi STL amal
ga oshirish.
Heapsort 1 Yo'q Tanlash
Kiritish tartibi n 1 Ha Kiritish O ( n + d ), mavjud
bo'lgan ketma-
ketliklar bo'yicha
eng yomon
holatda d inversiyala
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_7.png)
![r .
Blok saralash n 1 Ha Kiritish
va
birlashtir
ish Blokka asoslangan
holda
birlashtiring jo
yida birlashtirish
algoritmi [9]
bilan pas
tdan yuqoriga
birlashma saralash .
Kvadort n n Ha Birlashti
rish 4-kirish usulidan
foydalanadi tarmoqn
i saralash . [10]
Timsort n n Ha Kiritish
va
birlashtir
ish Qilayapti n ma'lumo
tlar allaqachon
saralangan yoki
teskari tartiblangan
bo'lsa taqqoslash.
Tanlov tartibida 1 Yo'q Tanlash Bilan barqaror
qo'shimcha joy yoki
bog'langan
ro'yxatlardan
foydalanilganda. [11]
Kubesort n n Ha Kiritish Qilayapti n ma'lumo
tlar allaqachon
saralangan yoki
teskari tartiblangan
bo'lsa taqqoslash.
Shellsort 1 Yo'q Kiritish Kichik kod hajmi.
Bubble sort n 1 Ha Almashi
sh Kichik kod hajmi.
Daraxtlarni
saralash (muv
ozanatli) n Ha Kiritish A dan
foydalanganda o'z-
o'zini
muvozanatlashtiradi
gan ikkilik qidiruv
daraxti .
Velosiped
saralash 1 Yo'q Kiritish Nazariy jihatdan
maqbul sonli
yozuvlar bilan
joyida.
Kutubxonani
saralash n Yo'q Kiritish Bo'sh joy qo'shish
tartibiga o'xshash.
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_8.png)
![Buning uchun katta
ehtimollik bilan
chegaralarni
kafolatlash uchun
kirishni tasodifiy
ravishda
almashtirish talab
etiladi, bu esa uni
barqaror qilmaydi.
Sabrni saralash n — n Yo'q Kiritish
va
tanlash Hammasini
topadi eng uzun
o'sib boradigan
ketma-ketliklar yild
a O ( n jurnal n ).
Smoothsort n 1 Yo'q Tanlash An moslashuvchan a
sosida tuzilgan
gipsort
varianti Leonardo
ketma-ketligi an'ana
viy emas ikkilik
uyum .
Ip navlari n n Ha Tanlash
Turnir turi n [12]
Yo'q Tanlash Uyma tartiblashning
o'zgarishi.
Kokteyl shaker
turi n 1 Ha Almashi
sh Bubblesortning
varianti, bu ro'yxat
oxiridagi kichik
qiymatlar bilan
yaxshi ishlaydi
Taroq saralash 1 Yo'q Almashi
sh O'rtacha
pufakchalardan
ko'ra tezroq.
Gnome sort n 1 Ha Almashi
sh Kichik kod hajmi.
Shuffle sort [13]
n kn kn n Yo'q Tarqatis
h va
birlashtir
ish Hech qanday
almashinuv amalga
oshirilmaydi.
Parametr k kirishdag
i entropiya bilan
mutanosib. k Tartibl
angan yoki teskari
tartibli kirish uchun
= 1.
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_9.png)
![Franceschini
usuli [14] — 1 Ha ? Amalga
oshiradi O ( n ) ma'lu
motlar harakat
qiladi.
Toq - juft n 1 Ha Almashi
sh Parallel
protsessorlarda
osongina boshqarish
mumkin.
Taqqoslanmaydigan turlar
Quyidagi jadvalda tasvirlangan butun sonni saralash bo'lmagan algoritmlar va
boshqa saralash algoritmlari taqqoslash turlari . Shunday qilib, ular cheklanib
qolmaydi Ω ( n jurnal n ). [15]
Quyidagi murakkabliklar taxmin qilinadi n o'lchamlari
tugmachalari bilan saralash kerak bo'lgan narsalar k , raqam
kattaligi d va r saralanadigan raqamlar diapazoni. Ularning aksariyati kalit hajmi
etarlicha katta, chunki barcha yozuvlar noyob kalit qiymatlarga ega bo'lishi
mumkin va shuning uchun n ≪ 2 k
, bu erda ≪ "nisbatan kamroq" degan ma'noni
anglatadi. Birlik tannarxida tasodifiy kirish mashinasi modeli, ishlash vaqti bilan
algoritmlar , masalan, radix sort, shunga mutanosib vaqt talab etadi Θ
( n jurnal n ), chunki n dan oshmasligi bilan cheklangan va saralash uchun
ko'proq sonli elementlar kattaroq qismini talab qiladi k ularni xotirada saqlash
uchun. [16]
Taqqoslanmaydigan turlar
Ism Eng
yaxshi O'rtacha Eng
yomoni Xotira Barqaror n ≪
2 k Izohlar
Kabutar
teshiklari — Ha Ha
Paqir
navi (yagona
kalitlar) — Ha Yo'q Massivdagi
domendan
elementlarning bir
xil taqsimlanishini
nazarda tutadi. [17]
Paqir
navi (tamsayı
tugmachalari) — Ha Ha Agar r bu ,
keyin o'rtacha vaqt
murakkabligi .
[18]
Sanoq turi — Ha Ha
Agar r bu ,
keyin o'rtacha vaqt
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_10.png)
![murakkabligi .
[17]
LSD Radix
Saralash — Ha Yo'q rekursiya
darajasi,
2 d
hisoblash qatori
uchun. [17] [18]
MSD Radix
Saralash — Ha Yo'q Barqaror versiyada
tashqi o'lchamdagi
massiv
ishlatiladi n barcha
axlat qutilarini
ushlab turish.
MSD Radix
Saralash (joyida) — Yo'q Yo'q joyida uchun d =
1, rekursiya
darajalari,
hisoblash massivi
yo'q.
Spreadsort n Yo'q Yo'q Asimptotik degan
taxminga
asoslanadi n ≪ 2 k
,
ammo algoritm
buni talab
qilmaydi.
Burstsort — Yo'q Yo'q Qatorlarni saralash
uchun radix sortiga
qaraganda
yaxshiroq doimiy
omilga ega. Garchi
bir oz tez-tez
uchraydigan
torlarning o'ziga
xos xususiyatlariga
tayanadi.
Flashsort n n Yo'q Yo'q Lineer vaqt ichida
ishlash uchun
massivdagi
domendan
elementlarning bir
xil taqsimlanishini
talab qiladi. Agar
tarqatish o'ta
chayqalgan bo'lsa,
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_11.png)
![mavjud, ammo
ishlash muddati
bo'ladi ,
qayerda S saralan
adigan barcha
butun sonlarning
yig'indisi, kichik
sonlar bo'lsa,
ularni chiziqli deb
hisoblash
mumkin.
Oddiy
pancake
sort — n n Yo'q Ha Count - bu
varaqalar soni.
Spagetti
(So'rovno
ma) n n n Ha Ovoz
berish Bu talab
qilinadigan
elementlarning
ketma-ketligini
saralash uchun
chiziqli, analog
algoritm O ( n )
stack space va
tartib barqaror. Bu
talab
qiladi n parallel
protsessorlar.
Qarang spagetti
saralash # Tahlil .
Tarmoqni
saralash Turli xil
(barqaror
saralash
tarmoqla
ri
ko'proq
taqqoslas
hni talab
qiladi) Ha Taqqoslash tartibi
oldindan
belgilangan
tarmoq hajmiga
qarab belgilanadi.
32 dan ortiq
narsalar uchun
amaliy emas.
[ bahsli – muhokama qilish ]
Bitonik
saralash Yo'q Ha Tarmoqlarni
saralashning
samarali
o'zgarishi.
Bogosort n cheksiz 1 Yo'q Ha Tasodifiy
aralashtirish.
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_13.png)
![(aniq), (kut
ilgan) Faqat misol uchun
ishlatiladi, chunki
kutilgan eng
yaxshi ish vaqti
ham dahshatli. [19]
Stooge
sort n Yo'q Ha Vaqtning
murakkabligi
bilan saralash
algoritmlarining
aksariyatiga
nisbatan sekinroq
(hattoki sodda
ham) O ( n jurnal 3 /
jurnal 1.5
)
= O ( n 2.7095...
).
Nazariy kompyuter olimlari, bundan yaxshiroqini ta'minlaydigan boshqa saralash
algoritmlarini batafsil bayon qildilar O ( n jurnal n ) qo'shimcha cheklovlarni o'z
ichiga olgan vaqtning murakkabligi, shu jumladan:
Thorup algoritmi , cheklangan kattalikdagi domendan kalitlarni saralash
uchun tasodifiy algoritm O ( n log log n ) vaqt va O ( n ) bo'sh joy. [20]
Tasodifiy butun sonni saralash algoritmni qabul qilish kutilgan vaqt
va O ( n ) bo'sh joy. [21]
4 Mashhur saralash algoritmlari
Saralash algoritmlari juda ko'p bo'lsa-da, amaliy dasturlarda bir nechta
algoritmlar ustunlik qiladi. Kiritish saralashi kichik ma'lumotlar to'plamlari uchun
keng qo'llaniladi, katta ma'lumotlar to'plamlari uchun asimptotik jihatdan samarali
saralash, birinchi navbatda, yig'indilarni saralash, birlashtirish tartiblari yoki
tezkorlar. Samarali dasturlar odatda a dan foydalanadi gibrid algoritm , umumiy
saralash uchun asimptotik jihatdan samarali algoritmni rekursiyaning pastki
qismidagi kichik ro'yxatlar uchun qo'shish bilan birlashtirish. Yuqori darajada
sozlangan dasturlar kabi murakkab variantlardan foydalaniladi,
masalan Timsort (birlashtirish saralash, qo'shish tartibini va qo'shimcha mantiq),
Android, Java va Python-da ishlatiladigan va introsort (quicksort va heap sort),
ba'zilarida ishlatilgan (variant shaklida) C ++ saralash dasturlari va .NET-da.
Belgilangan oraliqdagi raqamlar kabi cheklangan ma'lumotlar uchun, tarqatish
turlari sanash sort yoki radix sort kabi keng qo'llaniladi. Bubble sort va variantlari
amalda kamdan kam qo'llaniladi, lekin odatda o'quv va nazariy munozaralarda
uchraydi.
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_14.png)
![Ob'ektlarni jismoniy tartiblashda (masalan, qog'ozlar, testlar yoki kitoblar) alfavit
qilishda odamlar intuitiv ravishda odatda kichik to'plamlar uchun qo'shilish
turlaridan foydalanadilar. Kattaroq to'plamlar uchun odamlar ko'pincha birinchi
chelakni, masalan, boshlang'ich harflar bilan, va bir nechta chelaklar juda katta
to'plamlarni amaliy saralashga imkon beradi. Ko'pincha bo'shliq nisbatan arzon,
masalan, erga yoki katta maydonga narsalarni yoyish, ammo operatsiyalar
qimmatga tushadi, ayniqsa ob'ektni uzoq masofaga ko'chirish - mos yozuvlar
joylashuvi muhim ahamiyatga ega. Birlashtirish turlari jismoniy ob'ektlar uchun
ham amaliydir, chunki ikkita qo'l ishlatilishi mumkin, har bir ro'yxat birlashtirilishi
mumkin, boshqa algoritmlar, masalan, yig'ish tartibida yoki tezkor tartiblash, odam
uchun juda mos emas. Kabi boshqa algoritmlar kutubxona , bo'sh joy qoldiradigan
qo'shilish tartibining bir varianti ham jismoniy foydalanish uchun amaliydir.
Oddiy navlar
Eng oddiy ikkita turdan biri - qo'shimchalarni saralash va tanlash saralashi, ikkalasi
ham kichik ma'lumotlarda samarali bo'ladi, chunki qo'shimcha xarajatlar past,
ammo katta ma'lumotlarda samarali emas. Kiritish saralashi amalda tanlov
saralashiga qaraganda tezroq bo'ladi, chunki taqqoslashlar kamligi va deyarli
saralangan ma'lumotlarda yaxshi ishlashi va shuning uchun amalda afzal ko'rilgan,
ammo tanlov saralash kamroq yozishlardan foydalanadi va shu bilan yozish
ishlashi cheklovchi omil bo'lganda ishlatiladi.
Kiritish tartibi
Asosiy maqola: Kiritish tartibi
Kiritish tartibi kichik saralashlar va asosan saralangan ro'yxatlar uchun nisbatan
samarali bo'lgan va ko'pincha murakkab algoritmlarning bir qismi sifatida
ishlatiladigan oddiy saralash algoritmidir. Bu ro'yxatdagi elementlarni birma-bir
olish va ularni o'zlarining to'g'ri holatiga hamyonimizga qanday pul qo'yishimizga
o'xshash yangi tartiblangan ro'yxatga kiritish orqali ishlaydi. [22]
Massivda yangi
ro'yxat va qolgan elementlar massivning bo'sh joyini bo'lishishi mumkin, ammo
kiritish juda qimmat, shuning uchun quyidagi barcha elementlarni birma-bir
almashtirish kerak. Shellsort (quyida ko'rib chiqing) - bu katta ro'yxatlar uchun
samaraliroq bo'lgan qo'shilish tartibining bir variantidir.
Tanlov tartibida
Asosiy maqola: Tanlov tartibida
Tanlov tartibida bu joyida taqqoslash . Unda bor O ( n 2
) murakkabligi, uni katta
ro'yxatlarda samarasiz qiladi va umuman o'xshashidan yomonroq ishlaydi qo'shish
tartibi . Tanlovni saralash soddaligi bilan ajralib turadi, shuningdek, muayyan
vaziyatlarda murakkab algoritmlarga nisbatan ishlashning afzalliklariga ega.
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_15.png)
![Algoritm minimal qiymatni topadi, uni birinchi holatdagi qiymat bilan almashtiradi
va ro'yxatning qolgan qismida ushbu amallarni takrorlaydi. [23]
Bu ko'proq
emas n almashtirish, shuning uchun almashtirish juda qimmat bo'lgan joyda
foydalidir.
Samarali navlar
Amaliy umumiy saralash algoritmlari deyarli har doim o'rtacha vaqt murakkabligi
(va umuman olganda eng yomon holatdagi murakkablik) algoritmiga
asoslanadi. n jurnal n ), ulardan eng keng tarqalgani - yig'ma saralash, birlashma va
tezkor tortish. Ularning har birining afzalliklari va kamchiliklari bor, eng muhimi,
birlashma tartibini oddiy amalga oshirish O ( n ) qo'shimcha maydon va tezkor
kortni oddiy bajarish O ( n 2
) eng yomon murakkablik. Ushbu muammolarni yanada
murakkab algoritm evaziga hal qilish yoki yaxshilash mumkin.
Ushbu algoritmlar tasodifiy ma'lumotlarda asimptotik jihatdan samarali bo'lsa, real
ma'lumotlar uchun amaliy samaradorlik uchun turli xil modifikatsiyalar
qo'llaniladi. Birinchidan, ushbu algoritmlarning qo'shimcha xarajatlari kichikroq
ma'lumotlarda muhim ahamiyat kasb etadi, shuning uchun ko'pincha gibrid
algoritm ishlatiladi, odatda ma'lumotlar etarlicha kichik bo'lgandan so'ng qo'shish
tartibiga o'tadi. Ikkinchidan, algoritmlar allaqachon saralangan ma'lumotlar yoki
deyarli saralangan ma'lumotlarda yomon ishlaydi - bular real dunyo ma'lumotlarida
keng tarqalgan va ularni O ( n ) tegishli algoritmlar bo'yicha vaqt. Nihoyat, ular ham
bo'lishi mumkin beqaror va barqarorlik ko'pincha biron bir tarzda kerakli
xususiyatdir. Shunday qilib, ko'pincha murakkab algoritmlardan foydalaniladi,
masalan Timsort (birlashma tartibiga asoslangan) yoki introsort (tez yig'ilishga
asoslangan holda, yana uyumga tushish).
Saralashni birlashtirish
Asosiy maqola: Saralashni birlashtirish
Saralashni birlashtirish allaqachon saralangan ro'yxatlarni yangi tartiblangan
ro'yxatga birlashtirish qulayligidan foydalanadi. Har ikkala elementni taqqoslash
bilan boshlanadi (ya'ni, 1 bilan 2, keyin 3 bilan 4 ...) va agar birinchisi
ikkinchisidan keyin kelishi kerak bo'lsa, ularni almashtirish. Keyinchalik, natijada
olingan ikkita ro'yxatning har birini to'rtta ro'yxatga birlashtiradi, so'ngra to'rtta
ro'yxatni birlashtiradi va hokazo; oxirgi ikki ro'yxat yakuniy saralangan ro'yxatga
birlashtirilguncha. [24]
Bu erda tavsiflangan algoritmlardan biri bu juda katta
ro'yxatlarning o'lchovidir, chunki uning eng yomon ish vaqti O ( n jurnal n ).
Bundan tashqari, u nafaqat massivlarga, balki ro'yxatlarga ham osonlikcha
qo'llaniladi, chunki u tasodifiy kirishni emas, balki ketma-ket kirishni talab qiladi.
Biroq, u qo'shimcha O ( n ) kosmik murakkablik va oddiy dasturlarda juda ko'p
nusxalarni o'z ichiga oladi.
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_16.png)
![Birlashtirish navi murakkab algoritmda ishlatilganligi sababli amaliy qo'llanmalar
uchun nisbatan yaqinda ommalashgan Timsort , bu dasturlash tillarida standart
tartib uchun ishlatiladi Python [25]
va Java (sifatida JDK7 [26]
). Birlashtirish
tartibining o'zi odatdagi tartibdir Perl , [27]
boshqalar qatorida va kamida 2000 yildan
beri Java-da ishlatilgan JDK1.3 . [28]
Heapsort
Asosiy maqola: Heapsort
Heapsort ning ancha samarali versiyasidir tanlov saralash . Shuningdek, u
ro'yxatning eng katta (yoki eng kichik) elementini aniqlab, ro'yxatning oxiriga
(yoki boshiga) qo'yib, so'ngra ro'yxatning qolgan qismida davom etish orqali
ishlaydi, ammo bu vazifani a deb nomlangan ma'lumotlar tuzilishi yordamida
samarali bajaradi. uyum , maxsus turi ikkilik daraxt . [29]
Ma'lumotlar ro'yxati
uyumga aylantirilgandan so'ng, ildiz tuguni eng katta (yoki eng kichik) element
bo'lishiga kafolat beradi. U olib tashlanib, ro'yxatning oxiriga qo'yilganda, uyum
qayta tartibga solinadi, shunda qolgan eng katta element ildizga o'tadi. To'pni
ishlatib, keyingi eng katta elementni topish O (log) ni oladi n ) O, o'rniga vaqt ( n )
oddiy tanlov tartibidagi kabi chiziqli skanerlash uchun. Bu Heapsort-ga O
( n jurnal n ) vaqt, va bu ham eng yomon murakkablik.
Quicksort
Asosiy maqola: Quicksort
Quicksort a algoritmni ajratish va yutish a ga asoslangan bo'lim operatsiya:
massivni ajratish, element deb nomlangan burilish tanlangan. [30] [31]
Burilishdan
kichik bo'lgan barcha elementlar undan oldin va barcha katta elementlar undan
keyin harakatlanadi. Buni chiziqli vaqt ichida samarali bajarish mumkin va joyida .
Keyinchalik kichik va katta sublistlar rekursiv tartibda saralanadi. Bu o'rtacha vaqt
murakkabligini O ( n jurnal n ), kam xarajatli va shuning uchun bu mashhur
algoritm. Quicksort-ning samarali qo'llanilishi (joyida bo'linish bilan) odatda
beqaror va biroz murakkab, ammo amalda eng tez tartiblash algoritmlari qatoriga
kiradi. Uning oddiy O (log) bilan birga n ) bo'sh joydan foydalanish, tezkor saralash
eng mashhur saralash algoritmlaridan biri bo'lib, ko'plab standart dasturlash
kutubxonalarida mavjud.
Quicksort haqida muhim ogohlantirish shundaki, uning eng yomon ko'rsatkichi O
( n 2
); Bu kamdan-kam hollarda, sodda dasturlarda (birinchi yoki oxirgi elementni
pivot sifatida tanlash) bu tartiblangan ma'lumotlar uchun sodir bo'ladi, bu odatiy
hol. Quicksortdagi eng murakkab masala - bu yaxshi burilish elementini tanlashdir,
chunki burilishlarning doimiy ravishda yomon tanlovi O ning pasayishiga olib
kelishi mumkin ( n 2
) ishlash, lekin pivotlarni yaxshi tanlash O ( n jurnal n )
asimptotik jihatdan maqbul bo'lgan ishlash. Masalan, agar har bir
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_17.png)
![qadamda o'rtacha burilish sifatida tanlanadi, keyin algoritm O ( n jurnal n ). Kabi
mediani topish medianlar medianasi tanlash algoritmi ammo O ( n ) tartiblanmagan
ro'yxatlarda ishlash va shuning uchun saralash bilan katta xarajatlarni amalga
oshiradi. Amalda tasodifiy burilishni tanlash deyarli aniq O ( n jurnal n ) ishlash.
Shellsort
Shell sorti, ko'pikli sortdan farq qiladi, chunki u elementlarni ko'p sonli harakatga
keltiradi pozitsiyalarni almashtirish .
Asosiy maqola: Qobiq navlari
Shellsort tomonidan ixtiro qilingan Donald Shell 1959 yilda. [32]
Bu buyurtma
elementlarini bir vaqtning o'zida bir nechta pozitsiyadan chiqib ketish orqali
qo'shish tartibini yaxshilaydi. Shellsortning kontseptsiyasi shundan iboratki,
qo'shish tartibini amalga oshiradi vaqt, bu erda $ k $ - joyidan ikkita element
orasidagi eng katta masofa. Bu shuni anglatadiki, ular umuman olganda O ( n 2
),
lekin asosan saralangan, faqat bir nechta elementlari bo'lmagan ma'lumotlar uchun
ular tezroq ishlaydi. Shunday qilib, avval elementlarni uzoqdan saralash va
saralash uchun elementlar orasidagi bo'shliqni asta-sekin qisqartirish orqali
yakuniy saralash ancha tezroq hisoblab chiqiladi. Bitta dasturni ma'lumotlar ketma-
ketligini ikki o'lchovli massivda joylashtirish va keyin qo'shma tartib yordamida
massiv ustunlarini saralash deb ta'riflash mumkin.
Shellsortning eng yomon vaqt murakkabligi - bu ochiq muammo va ma'lum
bo'lgan murakkabliklar bilan ishlatilgan bo'shliqlar ketma-ketligiga bog'liq O ( n 2
)
ga O ( n 4/3
) va Θ ( n jurnal 2
n ). Bu, Shellsort ekanligi bilan birlashtirilgan joyida ,
faqat nisbatan kam miqdordagi kodga muhtoj va undan foydalanishni talab
qilmaydi chaqiruv to'plami , kabi xotira yuqori darajadagi holatlarda
foydalidir o'rnatilgan tizimlar va operatsion tizim yadrolari .
Bubble sort va variantlari
Bubble sort, va kabi variantlar qobiq saralash va mexnat turi , oddiy, juda samarasiz
saralash algoritmlari. Tahlil qilish qulayligi tufayli ular kirish matnlarida tez-tez
uchraydi, ammo amalda kamdan kam qo'llaniladi.
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_18.png)
![Bubble sort
Ko'piklarni saralash, doimiy ravishda ro'yxatdan o'tuvchi tartiblash
algoritmi, almashtirish buyumlar to'g'ri tartibda paydo bo'lguncha.
Asosiy maqola: Bubble sort
Bubble sort oddiy tartiblash algoritmi. Algoritm ma'lumotlar to'plamining boshidan
boshlanadi. U dastlabki ikkita elementni taqqoslaydi va agar birinchisi
ikkinchisidan kattaroq bo'lsa, ularni almashtiradi. Ma'lumotlar to'plamining
oxirigacha qo'shni elementlarning har bir juftligi uchun buni davom ettiradi. Keyin
yana dastlabki ikkita element bilan boshlanadi va oxirgi o'tkazishda hech qanday
svop bo'lmaguncha takrorlanadi. [33]
Ushbu algoritmning o'rtacha vaqti va eng
yomon ko'rsatkichi O ( n 2
), shuning uchun u kamdan-kam hollarda katta, tartibsiz
ma'lumotlar to'plamlarini saralash uchun ishlatiladi. Bubble sorti oz sonli
narsalarni saralash uchun ishlatilishi mumkin (bu erda uning asimptotik
samarasizligi yuqori jazo emas). Ko'pikni saralash deyarli har qanday uzunlikdagi
ro'yxatda ham samarali ishlatilishi mumkin (ya'ni, elementlar sezilarli darajada
joyida emas). Misol uchun, agar biron bir sonli element faqat bitta pozitsiya bilan
mos kelmasa (masalan, 0123546789 va 1032547698), qabariq tartiblash
almashinuvi ularni birinchi o'tish paytida tartibda oladi, ikkinchi o'tish barcha
elementlarni tartibda topadi, shuning uchun tartiblash bo'ladi faqat 2 ni oling n vaqt.
Taroq saralash
Asosiy maqola: Taroq saralash
Taroq saralash ga asoslangan nisbatan sodda tartiblash algoritmi qabariq turi va
dastlab Wlodzimierz Dobosiewicz tomonidan 1980 yilda ishlab chiqilgan.
[35]
Keyinchalik u Stiven Leysi va Richard Boks tomonidan qayta kashf etilib,
ommalashtirildi Bayt Jurnal 1991 yil aprelda chop etilgan maqola. Asosiy g'oya
yo'q qilishdir toshbaqalar yoki ro'yxat oxiriga yaqin kichik qiymatlar, chunki
ko'pikli tartibda ular saralashni juda sekinlashtiradi. ( Quyonlar , ro'yxat boshidagi
katta qiymatlar, qabariq tartibida muammo tug'dirmaydi) Bunga dastlab
elementlarni faqat bir-biriga ulashgan holda almashtirish o'rniga, qatorda bir-
biridan ma'lum masofada joylashgan elementlarni almashtirish orqali erishiladi. va
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_19.png)
![kichik bo'lgani uchun diskni almashtirish muammosini samarali ravishda yo'q
qilib, butun massiv ishlamaydigan xotiraga osongina joylashadi. Ushbu protsedura
ba'zan "yorliqlarni saralash" deb nomlanadi. [36]
Xotira hajmi muammosini bartaraf etishning yana bir usuli qo'llaniladi tashqi
tartiblash , for example one of the ways is to combine two algorithms in a way that
takes advantage of the strength of each to improve overall performance. For
instance, the array might be subdivided into chunks of a size that will fit in RAM,
the contents of each chunk sorted using an efficient algorithm (such as tezkor ),
and the results merged using a k -way merge similar to that used in mergesort . This
is faster than performing either mergesort or quicksort over the entire list. [37] [38]
Techniques can also be combined. For sorting very large sets of data that vastly
exceed system memory, even the index may need to be sorted using an algorithm
or combination of algorithms designed to perform reasonably with virtual xotira ,
i.e., to reduce the amount of swapping required.
Tegishli algoritmlar
Bunga tegishli muammolar kiradi partial sorting (sorting only the k smallest
elements of a list, or alternatively computing the k smallest elements, but
unordered) and tanlov (computing the k th smallest element). These can be solved
inefficiently by a total sort, but more efficient algorithms exist, often derived by
generalizing a sorting algorithm. The most notable example is tez tanlash bilan
bog'liq bo'lgan tezkor . Conversely, some sorting algorithms can be derived by
repeated application of a selection algorithm; quicksort and quickselect can be seen
as the same pivoting move, differing only in whether one recurses on both sides
(quicksort, bo'ling va zabt eting ) or one side (quickselect, decrease and conquer ).
A kind of opposite of a sorting algorithm is a shuffling algorithm . These are
fundamentally different because they require a source of random numbers.
Shuffling can also be implemented by a sorting algorithm, namely by a random
sort: assigning a random number to each element of the list and then sorting based
on the random numbers. This is generally not done in practice, however, and there
is a well-known simple and efficient algorithm for shuffling: the Fisher-Yeyts
aralashmasi .
7 Xulosa
Bizning miyamiz o`zi optimal deb bilgan yo`nalishdan ketadi va biz uchun faqat
bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb bo`lmaydi.
Dasturlashga talab ortib, bu soha rivojlanib borgani sari unda bir qator sohalardagi
kabi tezlikni oshirish muammosi paydo bo`ladi. Chunki ilk kompyuter tizimlarida
kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu
o`rinda savol tug`iladi, operatsion tizimlarda ham saralashdan foydalaniladimi?
PAGE \* MERGEFORMAT 22](/data/documents/06b37716-c9d5-4c78-bba4-33d003978295/page_22.png)
MAVZU: Ma’lumotlarni saralash. Saralashning birlashtirish (sliyanie) usuli Mundarija 1-bob 1 Tarix 2 Tasnifi 2.1 Barqarorlik 3 Algoritmlarni taqqoslash 3.1 Taqqoslash turlari 3.2 Taqqoslanmaydigan turlar 3.3 Boshqalar 2-bob 4 Mashhur saralash algoritmlari 4.1 Oddiy navlar 4.1.1 Kiritish tartibi 4.1.2 Tanlov tartibida 4.2 Samarali navlar 4.2.1 Saralashni birlashtirish 4.2.2 Heapsort 4.2.3 Quicksort PAGE \* MERGEFORMAT 22
4.2.4 Shellsort 4.3 Bubble sort va variantlari 4.3.1 Bubble sort 4.3.2 Taroq saralash 4.4 Tarqatish tartibi 4.4.1 Sanoq turi 4.4.2 Paqir navi 4.4.3 Radix sort 5 Xotiradan foydalanish tartibi va indekslarni saralash 6 Tegishli algoritmlar 3-bob 7 Xulosa 8 Adabiyotlar KIRISH “Dasturlash asoslari” fanining bosh maqsadi talabalarga qo‘yilgan tatbiqiy masalani anglash, yechish algoritmini ishlab chiqish va dasturiy ta’minotini yaratish asoslarini o‘rgatishdir. Shu maqsadda mazkur o‘quv qo‘llanmada masala echish matematik modellari, usullari va algoritmlar yaratish asoslari hamda kompyuterda masalalarni yechish uchun C++ dasturlash tilining tayanch tushunchalari keltirilgan. O‘quv qo‘llanmada kompyuter vositasida dasturlashga kirishning nazariy asosi bo‘lgan “algoritm” tushunchasiga alohida e’tibor qaratilgan. Mazkur qo’llfnmada algoritmlarni tavsiflash va keyinchalik kompyuter vositasida bajarish uchun zarur bo‘lgan bir qator matematik tushunchalar – chiziqli, tarmoqlanuvchi va takrorlanuvchi jarayonlar, yordamchi algoritm, massiv, PAGE \* MERGEFORMAT 22
indeks, rekursiya, funksiya va parametr kiritilgan bo‘lib, turli sohalarga oid masalalarni echish algoritmlari va dasturlariga oid mavzular yoritilgan. Dasturlash tili – tadqiq qilinadigan jarayonga mos keladigan matematik modeldagi munosabatni yechish usuli uchun tuzilgan algoritmni kompyuterda amalga oshirish vositasidir. Shu sababli o‘quv qo‘llanmada tatbiqiy masalalar yyechishning algoritmik asoslarini o‘rganish, kompyuterda berilganlar va buyruqlarni tasvirlash, shuningdek C++ tilida dasturlash asoslariga alohida e’tibor berilgan. Shu bilimlarga tayangan holda talaba kompyuter vositasida 1.Tarix Hisoblashning boshidan boshlab, saralash muammosi juda ko'p tadqiqotlarni jalb qildi, ehtimol bu oddiy, tanish bayonotga qaramay, uni samarali hal qilishning murakkabligi tufayli. Dastlabki saralash algoritmlari mualliflari orasida 1951 yil ham bo'lgan Betti Xolberton (tug'ilgan Snayder), kim ishlagan ENIAC va UNIVAC . Bubble sort 1956 yilidayoq tahlil qilingan. Taqqoslash tartiblash algoritmlari asosiy talabga ega Ω ( n jurnal n ) taqqoslashlar (ba'zi kirish ketma-ketliklari ko'paytmani talab qiladi n jurnal n taqqoslashlar, bu erda n - qatorga ajratiladigan elementlar soni). Kabi taqqoslashga asoslanmagan algoritmlar hisoblash turi , yaxshi ishlashga ega bo'lishi mumkin. Asimptotik optimal algoritmlar 20-asr o'rtalaridan beri ma'lum bo'lgan - foydali yangi algoritmlar hali ham ixtiro qilinmoqda, hozirda keng qo'llanilmoqda Timsort 2002 yilga tegishli va kutubxona birinchi marta 2006 yilda nashr etilgan. tanishishni ta'minlaydigan sinflar. katta O yozuvlari , algoritmlarni ajratish va yutish , ma'lumotlar tuzilmalari kabKirish qismida saralash algoritmlari keng tarqalgan Kompyuter fanlari masalan, algoritmlarning ko'pligi turli xil asosiy algoritm tushunchalari bilan yumshoq i uyumlar va ikkilik daraxtlar , tasodifiy algoritmlar , eng yaxshi, eng yomon va o'rtacha ish tahlil, vaqt-makon savdo- sotiqlari va yuqori va pastki chegaralar . Kichik massivlarni maqbul (hech bo'lmaganda taqqoslash va almashtirish) yoki tez (masalan, mashinaning o'ziga xos tafsilotlarini hisobga olgan holda) saralash hali ham juda kichik massivlar uchun ma'lum bo'lgan echimlarga ega bo'lgan ochiq tadqiqot muammosi (<20 element). Xuddi shunday maqbul (har xil ta'rifga ko'ra) parallel mashinada saralash ham ochiq tadqiqot mavzusi. 2. Tasnifi PAGE \* MERGEFORMAT 22
Saralash algoritmlari ko'pincha quyidagicha tasniflanadi: Hisoblashning murakkabligi ( eng yomon, o'rtacha va eng yaxshi xatti- harakatlar) ro'yxat kattaligi bo'yicha ( n ). Odatda ketma-ket tartiblash algoritmlari uchun yaxshi xatti-harakatlar O ( n jurnal n ), parallel saralash bilan O (log 2 n ) va yomon xulq O ( n 2 ). (Qarang Big O notation .) Ketma-ket tartiblash uchun ideal xatti-harakatlar O ( n ), ammo bu o'rtacha holatda bu mumkin emas. Optimal parallel saralash O (log) n ). Taqqoslashga asoslangan saralash algoritmlari kamida need (kerak n jurnal n ) ko'pgina kirishlar uchun taqqoslashlar. Hisoblashning murakkabligi svoplar ("joyida" algoritmlari uchun). Xotira foydalanish (va boshqa kompyuter resurslaridan foydalanish). Xususan, ba'zi bir saralash algoritmlari " joyida ". To'liq aytganda, joyida tartiblash tartiblangan narsalardan tashqari faqat O (1) xotiraga muhtoj; ba'zan O (log ( n )) qo'shimcha xotira "joyida" deb hisoblanadi. Rekursiya. Ba'zi algoritmlar rekursiv yoki rekursiv bo'lmagan, boshqalari esa ikkalasi ham bo'lishi mumkin (masalan, birlashtirish navi). Barqarorlik: barqaror saralash algoritmlari yozuvlarning nisbiy tartibini teng tugmachalar (ya'ni, qiymatlar) bilan saqlash. Ular yo'qmi yoki yo'qmi a taqqoslash . Taqqoslash saralashi ma'lumotlarni faqat taqqoslash operatori bilan taqqoslash orqali tekshiradi. Umumiy usul: qo'shish, almashtirish, tanlash, birlashtirish, va boshqalar. Birja turlariga pufakchali saralash va tezkor kort kiradi. Tanlash turlariga shaker sort va hepsort kiradi. Algoritm ketma-ket yoki parallel bo'ladimi. Ushbu munozaraning qolgan qismi deyarli faqat ketma-ket algoritmlarga asoslangan va ketma-ket ishlashni nazarda tutadi. Moslashuvchanlik: Kirishning oldindan belgilanishi ish vaqtiga ta'sir qiladimi yoki yo'qmi. Buni hisobga oladigan algoritmlar ma'lum moslashuvchan . . Barqarorlik PAGE \* MERGEFORMAT 22
O'yin kartalarida barqaror turga misol. Kartalar barqaror navbati bilan saralash bo'yicha tartiblanganida, har ikkala 5-lar avval chiqarilgan tartibda bir xil tartibda qolishi kerak. Agar ular barqaror bo'lmagan tartib bilan saralansa, 5-lar qarama- qarshi tomonga o'tishi mumkin tartiblangan chiqishda tartib. Barqaror saralash algoritmlari takrorlangan elementlarni kiritishda paydo bo'ladigan tartibda tartiblaydi. Ma'lumotlarning ayrim turlarini saralashda saralash tartibini aniqlashda ma'lumotlarning faqat bir qismi tekshiriladi. Masalan, o'ng tomonda kartalarni saralash misolida kartalar ularning darajalariga qarab saralanmoqda va ularning kostyumiga e'tibor berilmaydi. Bu asl ro'yxatning turli xil to'g'ri tartiblangan versiyalarini olish imkoniyatini beradi. Barqaror saralash algoritmlari, ulardan birini quyidagi qoidaga binoan tanlaydi: agar ikkita 5 ta karta singari ikkita narsa teng taqqoslansa, unda ularning nisbiy tartibi saqlanib qoladi, shuning uchun agar kiritishda biri ikkinchisidan oldin kelsa, u ham bo'ladi chiqishda bir-biridan oldin keling. Barqarorlik quyidagi sabablarga ko'ra muhimdir: ism va sinf qismidan iborat bo'lgan talabalar yozuvlari veb-sahifada dinamik ravishda, avval nomi bilan, so'ngra ikkinchi bo'limda sinf bo'limi bo'yicha tartiblanganligini ayting. Agar har ikkala holatda ham tartiblashning barqaror algoritmi ishlatilsa, "sinflar bo'yicha bo'lim" operatsiyasi nom tartibini o'zgartirmaydi; beqaror tartib bilan, bo'lim bo'yicha saralash nom tartibini aralashtirib yuborishi mumkin. Barqaror saralashdan foydalanib, foydalanuvchilar birinchi navbatda ism yordamida saralash orqali, so'ngra bo'lim yordamida yana saralash orqali bo'limlar bo'yicha, so'ngra ismlar bo'yicha saralashni tanlashi mumkin, natijada ismlar tartibi saqlanib qoladi. (Ba'zi bir elektron jadval dasturlari ushbu xatti-harakatga bo'ysunadi: ismlar bo'yicha saralash, keyin bo'lim bo'yicha talabalarning alifbo ro'yxati bo'limlar bo'yicha berilgan.) PAGE \* MERGEFORMAT 22