Деректерді реттеу әдістерін зерделеу және сипаттау Реттеу алгоритмдерінің бағдарламалық құралдарын талдау
жүктеу/скачать 0,51 Mb.
|
отчет сортировка
| 1.3 Деректерді реттеу әдістерін қою
Реттеудің жақсартылған алгоритмі.Осыған шейін қарастырған реттеу алгоритмдердің өте маңызды кемшілігі бар, дәлірек айтсақ, оларды орындау уақыты элементтер санының квадратна пропорционалды. Үлкен көлемдегі деректер үшін бұл реттеулер баяу болады, ал кейбір шамалармен бастауда олар өте баяу болады. Әрбір бағдарламашы «үш күн бойы орындалған реттеу» туралы естіген немесе айтқан болар. Өкінішке орай бұл әңгіме жаңсақ әңгіме емес болып табылады. Егер реттеу ұзақ орындалатын болса, онда оның себебі қолданылған алгоритмде болуы мүмкін. Бірақ, реттеудің мұндай күйдегі бірінші реакциясы сөзбен көрсетіледі: "Оданша бағдарламаны ассемблерде жазайық". Ассемблерді қолдану үнемі бағдарламаның жылдамдығын арттырады, бірақ егер алынған алгоритм айтарлықтай жақсы болмаса, онда реттеу кодтың оптималдылығынан тәуелділігінен тыс бұрынғыша ұзақ орындалатын болады. Уақыттың квадраттық тәуелділігі кезінде бағдарламаны орындау массив элементтерінің санынан кодтың оптималдылғын көтеру немесе ЭЕМ –нің жылдамдығын арттыру тек болмашы ғана жақсаруға алып келетінін естен шығармауымыз керек, сондай –ақ бағдарламаны орындау уақыты экспонент бойынша артатын болады. Егер Паскаль тілінде жазылған қандай –да бір программа айтарлықтай жылдам орындалмаса, онда ол жеткілікті түрде жылдам орындалмайтын болады, егер оны ассемблерде жазбасақ. Оның шешімі реттеудің ең жақсы алгоритмін қолдануда жатыр. Бұл бөлімде екі өте жақсы реттеу қарастырылатын болады. Біріншісі Шелла реттеуі деп аталады, ал екіншісі ең жақсы алгоритм деп танылған жылдам реттеу деп аталады. Бұл реттеулер өте жылдам орындалады.
жүктеу/скачать 0,51 Mb. Достарыңызбен бөлісу:
|