![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Дәріс № 2. «Көпіршік» әдісі.
Дә рістің мақ саты- студенттерді сұ рыптаудың ең қ арапайым тү рімен таныстыру, сұ рыптау алгоритмінің спецификасымен таныстыру. Бұ л ә діс тиімділік жағ ынан ең соң ғ ы орынғ а ие болғ ан, ең қ арапайым ә дістердің классына жатады. Бірақ, оғ ан қ арамастан, бұ л ә діс кең танымал, ө те тез еске сақ талатын атының арқ асында – судың бетіне шығ атын кө піршік ә дісі немесе батып бара жатқ ан доп ә дісі, кімге қ алай ұ найды. 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 бү тін сандар.
Нә тижесінде, алтя элемент ү шін 5+4+3+2+1 = 15 салыстыру жә не 8 орын ауыстырулар ө ткізілді. Жалпы жағ дайда, ә р n-1 қ адамда орташа n/2 салыстырулар ө ткізіледі, сондық тан салыстырулар саны ү шін бағ алау n(n-1)/2 жазбасымен бейнеленеді, яғ ни берілген ә діс O(n2) классына байланысты. Аналогті тү рде, орын ауыстырулар саны да n2 мә ніне пропорционалды. Бұ л ә діс ең тиімді емес сұ рыптау ә дісі болып табылады. Мысалы, 1000 элементтер ү шін салыстырулар саны 500 мың ғ а жұ ық болады. Бағ дарламалық тү рде іске асыру екі циклдан тұ рады: сыртқ ы нә тижі –алгоритмнің негізгі қ адамдары, ішкі – элементтерді салыстырады жә не орындарын массивтің соң ынан бастап ауыстырады. for i: = 2 to n do Begin for j: = n downto i do
|