Деректерді реттеу әдістерін зерделеу және сипаттау Реттеу алгоритмдерінің бағдарламалық құралдарын талдау
Деректерді реттеу әдістерін таңдау
жүктеу/скачать 0,51 Mb.
|
отчет сортировка
| 1.2 Деректерді реттеу әдістерін таңдау
Көпіршік әдісімен реттеу. Ең белгілі әдістердің бірі көпіршік әдісімен реттеу болып табылады. Оның әйгілілігі қарапайым алгоритмімен және есте қаларлық атымен түсіндіріледі. Бірақта бұл реттеу бір кездері ойлап табылған барлық реттеулердің ішіндегі ең нашары болып табылады Көпіршік әдісімен реттеуде алмастырып реттеу әдісі қолданылады. Ол салыстыру операциясын және көршіліес элементтердің орыны алмастыру қажеттілін циклде орындауға негізделген. Оның атауы әрбір көпіршік өзінің жеке деңгейін тапқан кездегі су резервуарындағы көпіршектердің қозғалыс процесіне ұқсастығына бола пайда болған. Көпіршікті сұрыптау өзінің қарапайым нұсқауында жай орындалады. Сондықтан оны элементтерді оптималдау үшін қолданады. Барлық көпіркшікті сұрыптаудың ерекшелігі-массив элементтерінің арасындағы алмасу. Төменде көпіршік әдісімен реттеудің ең қарапайым программасы көрсетілген: { көпіршік әдісімен реттеу} procedure Bubble(var item: DataArray; count:integer); var
x : DataItem; begin for i := 2 to count do begin for j := count downto i do if item[j-1]>item[j] then begin
x := item[j-1]; item[j-1] := item[j]; item[j] := x; end;
end; end; {көпіршік әдісімен реттеу соңы} Бұл жағдайдағы "item" берілгені реттелетін "DataItem" элементінің массиві болып табылады, ал "count" берілгені массивтегі элементтер санын береді. Көпіршікті әдіспен реттеуде екі цикл бар. Сондықтан массив элементтерінің саны "count" айнымалысымен беріледі, сыртқы цикл массивті count - 1 рет қарауға шақырады. Бұл процедура аяқталғаннан кейін әрбір элементті өз позициясында табуды қамтамасыз етеді. Ішкі цикл салыстыру және алмастыру операцияларын нақты орындау үшін арналған. Көпіршік әдісімен реттеудің бұл нұсқасы символық массивті элементтерін өспелі түрде реттеуі мүмкін. Мысалы, келесі қысқаша бағдарлама "test.dat" дискілік файлнан саналатын қатарды реттейді. Бұл бағдарлама реттеудің басқа ішкі бағдарламаларында қолданылуы мүмкін. program SortDriver; {бұл бағдарлама 80 немесе одан азырақ сиволдарды "test.dat", дискілік файлдан санайды, оларды реттейді және нәтижені дисплей экранына шығарады } type
DataItem = char; DataArray = array [1..80] of char; var
t, t2: integer; testfile: file of char;
procedure Bubble(var item: DataArray; count:integer); var i,j: integer; x: DataItem; begin
for i := 2 to count do begin
for j := count downto i do if item[j-1]>item[j] then begin
x := item[j-1]; item[j-1] := item[j]; item[j] := x; end;
end; end;
Assign(testfile, 'test.dat'); Reset(testfile); t := 1;
{реттелетін символдарды санау} while not Eof(testfile) do begin read(testfile, test[t]); t := t+1; end;
end.
Көпіршік әдісімен реттеу жұмысын иллюстрациялау үшін төменде "dcab" массивін реттеудің әрбір кезеңінің нәтижесі берілген: Бастапқы күйі: d c a b; Бірінші айналым: a d c b; Екінші айналым: a b d c; Үшінші айналым: a b c d. Әрбір реттеуді талдау кезінде жақсы, орташа және нашар жағдайларда орындалатын салыстыру және алмастыру операцияларының саны анықталады. Көпіршік әдісімен реттеу үшін салыстыру саны тұрақты болып қала береді, сондықтан екі цикл үнемі берілген санды бір рет реттелген бастапқы массивке тәуелділіктен тыс орындайды. Бұл көпіршік әдісімен реттеу кезінде әрдайым 1/2 (n2-n) салыстыру операциясы орындалатынын білдіреді, мұндағы "n" массивтің реттелетін элементтерінің санын береді. Бұл формула мына себептен шыққан, көпіршік әдісімен реттеудегі сыртқы цикл n-1 рет орындалады, ал ішкі цикл n/2 рет орындалады. Олады көбейту көрсетілген формуланы береді. Алмастыру операциясының саны жақсы жағдай үшін нөлдік болады, егер бастапқы массив реттелген болса. Алмастыру операциясының саны орташа жағдай үшін 3/4 (n2-n) тең болады, ал нашар жағдай үшін 3/2 (n2-n) тең болады. Реттелген бастапқы массивтің нашарлауынша реттелмеген элементтердің саны салыстыру санына жуықтайтындығын байқаймыз (әрбір реттелмеген элемент үш алмастыру операциясын талап етеді). Көпіршік әдісімен реттеу алгоритмі квадраттық алгоритм деп аталады, сондықтан оны орындау уақыты реттелетін элементтер санының квадратына пропорционал. Көпіршік әдісімен элементтердің үлкен санын реттеу өте көп уақытты талап етеді, яғни реттеуді орындау уақыты массив элементтерінің санынан квадраттық тәуелділікте болады. Мысалы, егер реттелмеген элементтердің орынын ауыстыру үшін орындалатын алмастыру операциясының уақытын есептемесек, онда бір салыстыру операциясын орындау кезінде 0,001 секунд аралығында он элементті реттеу 0,05 секундт алады, жүз элементті реттеу 5 секундты алады, ал 1000 элементті реттеу 500 секундты алады. 100 000 элементті реттеу (мұндай өлшем үлкенірек телефондық анықтамада бар) 5 000 000 секундты немесе шамамен 1400 сағатты талап етеді (яғни, екі ай бойы үздіксіз жұмыс істеу)! Көпіршік әдісімен реттеуде кейбір жағдайда оның уақытша сипаттамасын аздап жақсартуға болады. Мысалы, көпіршік әдісімен реттеу бір ерекшелікті иеленетінін байқауға болады: өз орнында емес массивтің соңында орналасқан элемент (мысалы, "dcab" массивындағы "а" элементі) өз орнына бір айналымда жетеді, ал массвитің басында орналасқан элемент (мысалы, "d" элементі), өз орнына өте баяу жетеді. Барлық қарап шығуларды бір бағытқа жасау міндетті емес. Оның орнына әрбір келесі қарап шығуды кері бағытта жасауға болады. Бұл жағдайда өз орнынан өте қашықта тұрған элементтер сәйкес орындарына жылдам орын ауыстыратын болады. Төменде массив бойынша қозғалысының сәйкес сипатынан "қайықтық реттеу" атауымен алынған көпіршік әдісімен реттеудің жақсы нұсқасы көрсетілген. Бұл реттеу жақсы көпіршік әдісі болып табылғанымен, оны қолдану үшін ұсынуға болмайды, сондықтан орындау уақыты бұрынғыша элемент санына квадратты тәуелді. Салыстыру саны өзгермейді, ал алмастыру саны аз ғана шамаға азаяды. {қайықтық реттеу көпіршік әдісімен реттеудің ең жақсы нұсқасы болып табылады } procedure Shaker(var item: DataArray; count:integer); var j, k, l, r: integer; x: DataItem; begin
l := 2; r := count; k := count; repeat
for j := r downto l do if item[j-1] then begin { обмен } x := item[j-1]; item[j-1] := item[j]; item[j] := x; k := j; end;
for j := l to r do if item[j-1]>item[j] then begin { обмен } x := item[j-1]; item[j-1] := item[j]; item[j] := x; k := j; end;
until l>r
жүктеу/скачать 0,51 Mb. Достарыңызбен бөлісу:
|