Python сұрыптау түрлері ұбт дайындық

Таңдау арқылы сұрыптау

Таңдау арқылы сұрыптауды өсу ретімен орындаудың бірінші қадамында массивтің минималды элементі табылады да, ол бірінші тұрған элементпен ауыстырылады. Массив екінші қадамды екінші элементтен бастап қарастырады. Ең кіші элемент тауып, екінші элементпен орын алмастырады. Әр элементтің ретін табу үшін осындай қадамдар қайталанады. Әрбір жаңа қадам массивтің сұрыпталмаған бөлігінен минимум мәнді тауып, оны ағымдағы элементпен ауыстырады. Әрекеттер n-1 рет қайталанады.

Кему ретімен сұрыптау үшін әрбір қадамда массивтің максималды элементін тауып отырады.

а=[3,6,2,1,5] массивін таңдау арқылы сұрыптап, өсу ретімен орналастырайық.

Әрбір i-қадамда a[i+1] ... a[n] элементтерінің минимумін тауып, оны a[і]-мен ауыстыру керек.

Код мысалы

Нәтижесі: а=[1,2,3,5,6]

Программада таңдау арқылы сұрыптау кіріктірілген циклдер негізінде жүзеге асырылады.

а rr массивін өсу ретімен таңдау арқылы сұрыптаудың коды

1-мысал.

0-ден 100-ге дейінгі кездейсоқ 10 саннан тұратын массивті өсу реті бойынша таңдау арқылы сұрыптау

Программалау коды

Көпіршікті сұрыптау

Әр итерацияда массив элементтерін жұбымен салыстырады. Егер жұптың орналасу тәртібі дұрыс болмаса, онда элементтер ауыстырылады. n-1 итерациялар өткеннен кейін массив сұрыпталады.

а=[9,4,2,5,1] массивінің элементтерін өсу ретімен орналастыру керек. Осы массивті көпіршікті әдіспен сұрыптап көрейік.

Әр итерациядан кейін массивтің соңындағы ең үлкен элемент алдыңғы максимум элементінің қасында тұрады. Минималды элемент әр уақытта массивтің басына қарай бір позициямен жылжытылады (көпіршіктің суда көтерілген сияқты).

Өсу ретімен көпіршікті сұрыптаудың коды

Сыртқы цикл n-1 итерацияларының орындалуына мүмкіндік береді. Ішкі цикл 0-ден (n-i-1)-ге дейінгі массивтің ағымдағы элементінің индексін таңдауға арналған. Әр итерациядан кейінгі ең үлкен элементтер массивтің соңында жинақталғандықтан, келесі қайталануларда оларды салыстыру кезінде ескерудің қажеті жоқ. Сондықтан ішкі цикл 0-ден (n-i-1) дейінгі аралықты қамтиды.

Егер элементтерді салыстыру кезінде «>» таңбасын «<» таңбасымен алмастыратын болсаң, онда массив кему ретімен орналасады.

2-мысал.

0-ден 100-ге дейінгі кездейсоқ 10 саннан тұратын массивті көпіршікті сұрыптау

Программалау коды

Нәтижесі:

Сұрыптау алгоритмінің тиімділігі орындалу жылдамдығымен және қолданылатын жад көлемімен бағаланады. Қарастырылған сұрыптау әдістерін кішігірім мәліметтер массивтерімен жұмыс кезінде қолдану ұсынылады.

Енгізу арқылы сұрыптау

Бұл жолы енгізу арқылы сұрыптауды қарастырамыз (Insertion sort). Бұл әдіс әрбір элементтің бұрын сұрыпталған элементтер арасында белгілі бір позиция бойынша ауысуына негізделген. Барлық массив сұрыпталған және сұрыпталмаған болып шартты түрде екі бөлікке бөлінеді. Бастапқыда сұрыпталған бөлік бос болады. Әр қадамда массивтің келесі элементі сұрыпталған бөліктегі элементтермен салыстырылады және оны орналастыратын орын анықталады. Осылайша, сұрыпталған бөлікте элементтер әрдайым дұрыс тәртіпте болады. Алгоритм массивтің барлық элементі қарастырылғанға дейін орындалады.

Кему бойынша сұрыптау дәл осылай орындалады, бірақ цикл шартындағы белгіні ауыстыру керек. (A[j] > key орнына A[j] < key деп жазу керек).

Кей жағдайларда сұрыптауды жеке функция ретінде ұйымдастырған ыңғайлы. Функцияны пайдаланып, кему ретімен енгізу арқылы сұрыптаудың алгоритмін жүзеге асыруды қарастырайық.

П рограммалау коды:

1-мысал. nxn матрицасының негізгі диагоналінің элементтерін енгізу арқылы сұрыптайтын программа жазу керек.

Программалау коды:

A = [ [8, 8, 8, 8, 8] ,

[1, 1, 1, 1, 1] ,

[7, 7, 7, 7, 7] ,

[2, 2, 2, 2, 2] ,

[5, 5, 5, 5, 5] ]

2-мысал. nxn матрицасының бүйір диагоналінің элементтерін кему ретімен енгізу арқылы сұрыптайтын программа жазу керек.

Программалау коды:

A = [ [8, 8, 8, 8, 8] ,

[1, 1, 1, 1, 1] ,

[7, 7, 7, 7, 7] ,

[2, 2, 2, 2, 2] ,

[5, 5, 5, 5, 5] ]