Laboratoriya ishi

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