Х. ДосмҰхамедов
Сұрыптау әдістері. Көпіршікпен сұрыптау
жүктеу/скачать 3 Mb.
|
- Бұл бет үшін навигация:
- Сұрыптау әдістері . Біріктірумен сұрыптауда
| Сұрыптау әдістері. Көпіршікпен сұрыптау
Біріктірумен сұрыптау Тізім мәннің өсуі бойынша сұрыптау Сұрыптау әдістері Сұрыптау – мәліметтерді белгілі бір ретпен жүйелеу. Сұрыптау алгоритмінің өзі мәліметтерді оқылатын форматқа қажет болса, деректерді іздеуді оңтайландыру үшін сұрыптау әдісін таңдауды көздейді. Python сұрыптау үшін бірнеше алгоритмді қолданады: көпіршік, кірістіру, біріктіру және қосымша сұрыптау. Кейбір алгоритмдердің Python тілінде жүзеге асуын қарастырайық. Көпіршікпен сұрыптау массивті сұрыптаудың қарапайым алгоритмдерінің бірі болып табылады. Яғни массивтің сол жағынан бастап көрші екі элментін салыстырады, кішісін сол жаққа, үлкенін оң жаққа алмастырып орналастырады. Бірінші жүріп өту нәтижесінде ең үлкен элемент массивтің соңына орналасады. Келесі айналымда тура сондай салыстыру амалдарын массивтің реттелмеген бөлігі үшін жалғастырады. Мысалы: [6, 82, -6, 48, 24, 35] берілген массивті көпіршікті сұрыптаумен реттеу керек. 0 1 2 3 4 5 массив элементтерінің нөмірленуі [6, 82, -6, 48, 24, 35] 0 және 1- элементтер салыстырылады, элементтер орнында қалады, себебі 6<82 [6, -6, 82, 48, 24, 35] 1 және 2- элементтер салыстырылды, элементтер орындарымен ауысты, себебі -6<82 [6, -6, 48, 82, 24, 35] осындай рет бойынша массивтің аяғына дейін [6, -6, 48, 24, 82, 35] [6, -6, 48, 24, 35, 82] Әр айналым сайын соңғы элемент қатыспайтындықтан, салыстырылатын элменттер саны 1-ге азайып, соңында ең кіші екі элемент салыстырылып, ретімен орналасады. Нәтижесінде келесі массив алынады: [-6, 6, 24, 35, 48, 82] Алгоритмнің бағдарламалық коды келесідей: 1-сурет Бағдарламаның нәтижесі: 2-сурет Көпіршікті сұрыптау алгоритмінің орныдалу жылдамдығы «кірістіру арқылы сұрыптау» алгоритміне қарағанда баяу. Кірістіру арқылы сұрыптау – бұл қарапайым сұрыптау алгоритмі, онда сұрыпталған массив бір рет бір жазба бойынша құрылады. Кірістіру арқылы сұрыптау бірнеше артықшылық береді: жүзеге асырудың қарапайымдылығы; кішігірім мәліметтер жинағы үшін тиімді; іске қосылу кезінде жадтың белгілі бір көлемін қолданады. Кірістіру арқылы сұрыптау: массивті реттелген және реттелмеген екі бөлікке бөліп сұрыптауға негізделген. Реттелмеген бөліктен таңдалған элемент реттелген бөліктегі орнына кірістіріліп орналастырылады. Әдетте сұрыптау қосымша жадты қолданбай орнында орындалады. Сұрыптау k итерация нәтижесінде k+1 элменттерді реттеп орналастырады. Әр итерация сайын кірістірілген элементтің алдыңғы орны жойылады. Кірістіру арқылы сұрыптаудың орныдалуын қарастыр, төмендегі мысалда әр итерацияның қасына жақшада кірістірілген элменттің неше позицияға ауысқанын білдіреді. Қарастырылған массив 7 итерацияда сұрыпталды. 0 1 2 3 4 5 массив элементтерінің нөмірленуі [6, 82, -6, 48, 24, 35] (0) [6, 82, -6, 48, 24, 35] (0) [-6, 6, 82, 48, 24, 35] (2) [-6, 6, 48, 82, 24, 35] (1) [-6, 6, 24, 48, 82, 35] (2) [-6, 6, 24, 35, 48, 82] (2) Кірістіру арқылы сұрыптау әдісін жүзеге асырудың бағдарламалық коды: 3-сурет Сұрыпталған массивтің нәтижесі: 4-сурет Сұрыптау әдістері. Біріктірумен сұрыптауда жүктеу/скачать 3 Mb. Достарыңызбен бөлісу:
|