Деректерді реттеу әдістерін зерделеу және сипаттау Реттеу алгоритмдерінің бағдарламалық құралдарын талдау

жүктеу/скачать 0,51 Mb.

бет	4/15
Дата	06.01.2022
өлшемі	0,51 Mb.
	#14296
түрі	Құрамы

1 2 3 4 5 6 7 8 9 ... 15

Байланысты:
отчет сортировка

Таңдау әдісімен реттеу.Таңдау әдісі реттеудің айқын әдісі болып табылады. Таңдау әдісімен реттеу идеясының маңызы әрбір берілген орын ауыстырған элемент тіке өзінің қажетті орнына орналасады. Таңдаумен реттеу кезінде ең кіші элемент таңдап алынады және оны массивтің бірінші элементімен алмастыру орындалады. Сонан соң қалған n-1 элементтің ішінен ең кіші элемент табылады және оны екінші элементпен алмастырады және т.с.с.соңғы екі элементті алмастырғанға дейін орындалады. Бұл әдіс ең кіші элементті әлі реттелмеген жиын бөлігінен таңдауға негізделгендіктен таңдау әдісімен реттеу деп аталады. Таңдау әдісімен реттеу қаншалықты салыстыруды орындаудың таңдаулы тәсілі болғанымен ол реттеудің тиімді әдісі емес. Таңдау әдісімен реттеу жылдамдығы көпіршік әдісімен реттеудің жылдамдығымен бірдей. Іс жүзінде таңдау әдісін қолдану тиімді емес. Мысалы, егер таңдаумен реттеуді "bdac" массиві үшін қолданатын болсақ, онда келесі айналымдар атынады:

Бастапқы күйі: b d a c;

Бірінші айналым: a d b c;

Екінші айналым: a b b c;

Үшінші айналым: a b c d.

Өкінішке орай көпіршік әдісімен реттеудегідей сыртқы цикл n-1 рет орындалады, ал ішкі цикл n/2 рет орынлады. Бұл таңдаумен реттеу үшін салыстыру саны 1/2 (n²-n) тең болатындығын және бұл реттеу элменттердің үлкен саны үшін өте баяу орындалатынын білдіреді. Жақсы жағдайда алмастыру операциясының саны 3(n-1) тең, ал нашар жағдайда n²/4+3(n-1) тең болады. Жақсы жағдайда /бастапқы массив реттеліп қойғанда/ тек n-1 элементтің ғана орнын ауыстыруын талап етеді, ал әрбір алмасу операциясы үш салып жіберу операциясын талап етеді.

{таңдаумен реттеу}

procedure Selekt(var item: DataArray; count:integer);

var

i, j, k: integer;

x: DataItem;

begin

for i := i to count-1 do

begin

k := i;

x := item[i];

for j := i+1 to count do {ең кіші элементті табу}

if item[j]

begin

k := j;

x := item[j];

end;

item[k] := item[i]; {алмастыру}

item[i] := x;

end;

end; {таңдаумен реттеудің соңы}

Алмастырудың орташа саны n(ln+y) тең, мұндағы "y" Эйлер тұрақтысы болып табылады, шамамен 0,577216 тең.

жүктеу/скачать 0,51 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7 8 9 ... 15