Qisqacha nazariy ma’lumotlar
Kompyuterda ma’lumotlarni qayta ishlashda elementning axborot maydoni va uning xotirada qanday joylashishini aniqlash muhim ahamiyatga ega. Shu maqsadda saralash algoritmlari qo’llaniladi.
Saralash quyidagi turlari bilan farqlanadi:
1) ichki saralash – bu kompyuter tezkor xotirasida bajariladigan saralash hisoblanadi;
2) tashqi saralash – bu kompyuterning tashqi xotira qurilmalaridagi saralash hisoblanadi.
Agar saralanadigan ma’lumotlar xotiradan katta hajmdagi joyni egallasa, u holda ularni saralash ma’lumot elementlarining kalitlar jadvalida amalga oshiriladi, ya’ni ko’rsatkichlar o’rnini almashtirish orqali bajariladi. Bu kalitlar jadvalini saralash usuli deyiladi.
Saralash ajaryonida bir xil kalitli elementlar uchrashi mumkin. Bunday hollarda saralash jarayonida bir xil kalitlarni saralash kirish holatidagi tartibda qoldirilishi maqsadga muvofiq bo’ladi. Bu turg’un saralash deb ataladi.
Saralash samaradorligini bir necha kriteriyalar bilan tavsiflash mumkin:
- saralash uchun sarflanadigan vaqt bo’yicha;
- saralash uchun talab qilinadigan tezkor xotira hajmi bo’yicha.
Ushbu laboratoriya ishida quyidagi algoritmlardan foydalanamiz:
1) To’g’ridan-to’g’ri qo’yish usuli bilan saralash algoritmi:
InsertionSort(list,N)
list – tartiblanadigan elementlar ro’yxati
N - ro’yxatdagi elementlar soni
for i=2 to N do
newElement=list[i]
location=i–1
while (location>=1) and (list[location]>newElement) do
//navbatdagi elementdan katta barcha elementlarni surish
list[location+1]=list[location]
location=location–1
end while
list[location+1]=newElement
end for
2) To’g’ridan-to’g’ri almashtirish (“pufakcha”) usuli bilan saralash:
BubbleSort(list,N)
list – tartiblanadigan elementlar ro’yxati
N - ro’yxatdagi elementlar soni
numberOfPairs=N
swappedElements=true
while swappedElemets do
numberOfPairs=numberOfPairs-1
swappedElements=false
for i=1 to numberOfPairs do
if list[i]>list[i+1] then
swap(list[i], list[i+1])
swappedElements=true
end if
end for
end while
3) Shell saralash algoritmi:
ShellSort(list,N)
list saralanadigan ro’yxat nomi
N ro’yxatdagi elementlar soni
passes=[log_2N]
while (passes>=1) do
increment=2^passes-1
for start=1 to increment do
InsertionSort(list,N,start,increment)
end for
passes=passes-1
end while
4) Tez saralash algoritmi:
QuickSort (list, first, last)
list – tartiblanadigan elementlar ro’yxati
first –ro’yxatning tartiblanadigan qismining birinchi elementi
last – ro’yxatning tartiblanadigan qismining oxirgi elementi
if first
pivot=PivotList(list, first, last)
QuickSort(list, first, pivot-1)
QuickSort(list, pivot+1, last)
end if
Bu algoritm tarkibidagi PivotList algoritmi quyidagicha tavsiflanadi:
PivotList (list, first, last)
list – qayta ishlanadigan ro’yxat
first – birinchi element nomeri
last – oxirgi element nomeri
PivotValue=list[first]
PivotPoint=first
for index=first+1 to last do
if list[index]
PivotPoint=PivotPoint+1
Swap(list[PivotPoint], list[index])
end if
end for
//o’q elementni kerakli o’ringa o’tkazish
Swap(list[first], list[PivotPoint])
return PivotPoint
Do'stlaringiz bilan baham: |