Дәріс № 2. «Көпіршік» әдісі.

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

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

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

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

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

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

.....

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

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

Нә тижесінде, алтя элемент ү шін 5+4+3+2+1 = 15 салыстыру жә не 8 орын ауыстырулар ө ткізілді.

Жалпы жағ дайда, ә р n-1 қ адамда орташа n/2 салыстырулар ө ткізіледі, сондық тан салыстырулар саны ү шін бағ алау n(n-1)/2 жазбасымен бейнеленеді, яғ ни берілген ә діс O(n²) классына байланысты. Аналогті тү рде, орын ауыстырулар саны да n² мә ніне пропорционалды. Бұ л ә діс ең тиімді емес сұ рыптау ә дісі болып табылады. Мысалы, 1000 элементтер ү шін салыстырулар саны 500 мың ғ а жұ ық болады.

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

for i: = 2 to n do

Begin

for j: = n downto i do