Деректерді реттеу әдістерін зерделеу және сипаттау Реттеу алгоритмдерінің бағдарламалық құралдарын талдау
жүктеу/скачать 0,51 Mb.
|
отчет сортировка
| Қосу әдісімен реттеу. Қосумен реттеу реттеудің қарапайым алгоритмінің ішіндегі соңғысы болып табылады. Қосумен реттеу кезінде алдымен массивтің екі элементі реттеледі. Содан кейін алғашқы екі элементке қатысты үшінші элементті сәйкес орнына қосу орындалады. Бұл процесс барлық элементтер реттелгенге шейін қайталанады. Мысалы, "dcab" массиві үшін қосумен реттеу келесі түрде жүреді:
Бастапқы күйі: d c a b; Бірінші айналым: c d a b; Екінші айналым: a c d b; Үшінші айналым: a b c d. Төменде қосумен реттеу алгоритмі көрсетілген: { қосумен реттеу } procedure Inser(var item: DataArray; count:integer); var i, l: integer; x: DataItem; begin
for i := 2 to count do begin
x := item[i]; j := i-1; while (x begin
item[j+1] := item[j]; j := j-1; end; item[j+1] := x; end; end; { қосумен реттеудің соңы } Қосумен реттеудің көпіршік әдісімен реттеуден айырмашлығы салыстыру операциясының саны қосумен реттеу үшін бастапқы реттелген массив элементтеріне байланысты. Егер бастапқы массив реттеліп қойған болса, онда салыстыру операциясының саны n-1 тең болады. Егер массив кері ретпен реттелген болса, онда салыстыру операциясының саны 1/2 (n2 +n)-1 тең, орташа мәні 1/4 (n2+n-2) береді. Алмастыру операциясының саны төмендегідей болады: жақсы жағдай үшін: 2 (n-1); орташа жағдай үшін: 1/4 (n2+9n-10); нашар жағдай үшін: 1/2 (n2+3n-4). Сол себепті, алмастыру операциясының саны көпіршік әдісімен реттеу және таңдаумен реттеу сияқты нашар жағдай үшін айтарлықтай үлкен болады. Алмастыру операциясының саны орташа жағдай үшін тек аздап кіші болады. Бірақта қоусмен реттеудің екі артықшылығы бар. Біріншіден, ол табиғи күйді иеленеді, яғни ол реттелген массив үшін жылдам орындалады және егер массив кері ретпен орналасқан болса ұзағырақ орындалады. Бұл реттелген массивтер үшін қосумен реттеуді пайдалы етеді. Екіншіден, бір кілті бар элементтер қайта қосылмайды: егер элементтер тізімі қолданылған екі кілт арқылы реттелсе, онда қосумен реттеу аяқталғаннан кейін ол бұрынғыша екі кілт бойынша реттелетін болады. Салыстыру саны деркетер жиынтығын анықтау үшін айтарлықтай үлкен болмауы мүмкін, массвитің үнемі жылжуы салып жіберу операциясының үлкен санын орындауды талап етеді. Бірақта, қосумен реттеу реттелейін деп қалған тізім үшін алмастыру операциясының аз санын және кері бағытта реттлеген массив үшін алмастыру операциясының үлкен санын талап ете отырып табиғи күйді иеленеді. жүктеу/скачать 0,51 Mb. Достарыңызбен бөлісу:
|