Қазақстан республикасының бiлiм және ғылым министрлiгi


«Көбікше» әдісі (Айырбастау бойынша сұрыптау). ( 2 сағат)



бет9/14
Дата18.12.2021
өлшемі0,78 Mb.
#102591
1   ...   6   7   8   9   10   11   12   13   14
Байланысты:
364bd4d0-c314-11e5-bf37-f6d299da70eeМетод лекцииМСП

2. «Көбікше» әдісі (Айырбастау бойынша сұрыптау). ( 2 сағат)


Дәрістің мақсаты- студенттерді сұрыптаудың ең қарапайым түрімен таныстыру, сұрыптау алгоритмінің спецификасымен таныстыру.

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

Көпіршікті әдіс алгоритмі тізім бойынша бірнеше рет өтеді. Әрбір өткенде көрші элементтерді салыстырады. Егер көрші элементтердің тізімі дұрыс емес болса, онда олар орын ауыстырады. Әрбір тәсіл тізім басынан басталады. Алдымен бірінші мен екінші элементтер, сосын екінші мен үшінші, содан кейін үшінші мен төртінші және т.с.с.; жұпта ретсіз тұрған элементтердің орны ауыстырылады. Тізімнің ең үлкен элементін бірінші өткенде тапқан кезде ол тізімнің соңына жеткенге дейін барлық кезекті элементтермен орын ауыстыра береді. Сондықтан екінші рет өткенде соңғы элементпен салыстыру қажет емес. Екінші рет өткенде тізімнің екінші элементі соңғы позициядан бастап екіншіге түседі. Процесті жалғастыра берсек әрбір өткен сайын ең болмағанда кезекті бір элемент өзінің орнында қалады. Бұл кезде ең кіші мәндер жоғары қарай жиналады. Егер қандай да бір өткен кезде ешқандай элементтердің орны ауыспаса, онда олардың барлығы қажетті ретпен тұр, және алгоритмнің орындалуын тоқтатуға болады. Әрбір өткенде бірден бірнеше элемент өзінің орнына жақындай түседі, тек біреуі ғана нақты орнында келеді.

Көбікше сұрыптау (көпіршік әдісімен сүрыптау) (Пузырьковая сортировка (сортировка методом пузырька); bublle sorting) — реттелетін жиымның көрші элементтерін тізбектік орын ауыстырудан тұратын сұрыптау тәсілі.

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

n элементтер бар дейік, олар а1 а2, а3, . . ., аn, массив ұяшаларында орналасқан. Ыңғайлылық үшін элементпен кілт бір мәнге ие дейік. Алгоритм n-1 қадамдардың қайталануларынан тұрады, оның әрқайсысында қалған өндірілмеген жиында жұптасқан көрші элементтерді салыстырулары арқылы минималды элемент табылады.

Қадам 1. аn –ді аn-1 – мен салыстырамыз, және егер аn < аn-1 онда оларды орындарымен ауыстырамыз, содан кейін аn-1 және аn-2 салыстырамыз, мүмкін, олардың да орындарын ауыстырамыз, аn-2 және аn-3 және ары қарай жалғастыра береміз, а2 және а1 элементтеріне келгенше. Нәтижесінде бірінші орында ең минималды элемент тұрады , ол содан кейін сұрыптау процессіне қактыспайды

Қадам 2. Аналогты түрде аn және аn-1, аn-1 және аn-2 және...., а3 және а2, нәтиже ретінде а2 элементінің орнына екінші минималды элемент тұрады, ол а1 элементімен бірге реттелген массивтің бастапқы бөлігін құрады.

Қадам 3. Ұқсас салыстырулар мен орын ауыстырулармен а3, а4, … , аn элементтерінің арасында а3 эелементінің орнына ең кіші элемент

. . . . .

Қадам n-1. Бұл сәтке дейін бірінші n-2 элементтер массивте реттелген болып тұрады, содан кейін тек екі аn-1 және аn арасында рет қою керек болады. Осы кезеңде сұрыптау процессі аяқталады.

Мысалы. 6 элемент берілген болсын –15, 33, 42, 07, 12, 19, бүтін сандар.



Кесте 1. Сұрыптау амалдары

 

а1

а2

а3

а4

а5

а6

Амалдар

қадам1

115

333

442

07

112

119

салыстыру 19 және 12, ауыстыру жоқ

115

333

442

07

112

119

салыстыру 12 және 07, ауыстыру жоқ

115

333

07

442

112

119

салыстыру 07 және 42, орындарын ауыстырамыз

115

07

333

442

112

119

салыстыру 07 және 33, орындарын ауыстырамыз

07

115

333

442

112

119

салыстыру 07 және 15, орындарын ауыстырамыз; 07 – минималды

қадам 2

07

115

333

442

112

119

салыстыру 19 және 12, ауыстыру жоқ

07

115

333

112

442

119

салыстыру 12 және 42, орындарын ауыстырамыз

07

115

112

333

442

119

салыстыру 12 және 33, орындарын ауыстырамыз

07

112

115

333

442

119

салыстыру 12 және 15, орындарын ауыстырамыз, 12 –екінші минималды.

қадам3



Достарыңызбен бөлісу:
1   ...   6   7   8   9   10   11   12   13   14




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет