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

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, бүтін сандар.