Ќазаќ мемлекеттік ќыздар педагогика институты

Тікелей алмастыру көмегімен сұрыптау

жүктеу/скачать 1,32 Mb. бет 25/53 Дата 06.06.2022 өлшемі 1,32 Mb. #36433 түрі Сабақ

Бұл бет үшін навигация:

• көпіршікті

Тікелей алмастыру көмегімен сұрыптау Сұрыптау әдістерін топтау барлық уақытта түсінікті бола бермейді. Тікелей таңдау мен тікелей қосу әдістерін «алмастырылатын» сұрыптау ретінде қарастыруға болады. Бұл қарастырылатын әдісте екі элементті орындарымен алмастырудың өзіне тән ерекшелігі бар. Тікелей алмастыру алгоритмі көрші элементтер жұбының салыстырылып, олардың орнын алмастыруға негізделеді және бұл процесс барлық элементтер реттелгенше жалғасады. Жоғарыда келтірілген тікелей таңдау әдісінде әрбір қайталануда ең кіші элементті ығытыра отырып, тізбектің сол жақ шетіне жеткенше массив элементтерін електен өткіземіз. Егер біз массивті горизонталь құрылым емес, вертикаль құрылымда қарастыратын болсақ, онда элементтерді судан ұшып шыққан көпіршік ретінде қарастыруға болады. Оның әрқайсысының салмағы олардың кілтіне сәйкес келеді. Бұл жағдайда әрбір қайталауда өзінің салмағына сәйкес келетін бір көпіршік деңгейге дейін көтеріледі. Мұндай әдіс «көпіршікті» сұрыптау деген кеңінен танымал. і= 1 2 3 4 5 6 7 8 44 06 06 06 06 06 06 06 55 44 12 12 12 12 12 12 12 55 44 18 18 18 18 18 42 12 55 44 42 42 42 42 94 42 18 55 44 44 44 44 18 94 42 42 55 55 55 55 06 18 94 67 67 67 67 67 67 67 67 94 94 94 94 94 Оның алгоритмі төмендегідей: «Көпіршікті» әдіс бойынша сұрыптау. Program suruptau1; Uses crt; var c:array[1..100] of word; і,j,n,r:іnteger; Begіn wrіte('n='); {массивтің өлшемін енгізу} readln(n); Randomіze; for і:=1 to n do {массивті толтыру} c[і]:=random(100); for і:=1 to n do {алғашқы массив элементтерін шығару} wrіteln('c[',і,']=',c[і],' '); {массив элементтерін сұрыптау} for і:=1 to n-1 do for j:=і+1 to n do іf c[j]begіn r:=c[і]; c[і]:=c[j]; c[j]:=r; end; {сұрыпталған массив элементтерін шығару} wrіteln('suruptalgan massіv'); for і:=1 to n do wrіteln('c[',і,']=',c[і]); repeat untіl keypressed; end. Бұл әдіс бойынша көрші тұрған екі элемент салыстырылып, одан кейін сұрыптау шартына тәуелді орындары алмасады. Бұл алгоритмді жетілдіру керек екені схемадан көрініп тұр. Кестеде көрсетілгендей соңғы 3 електен өткізу элементтер сұрыпталып тұрғандықтан элементтердің орналасуына әсер етпейді. Бұл алгоритмді жетілдірудің бір тәсілі кейбір електен өткізуде алмастыру болмаса, онда алгоритм аяқталуы тиіс. Бұл алгоритмді тағы да жетілдіруге болады, тек алмастырудың өзі ғана сақталмай, соңғы алмастырудың орны да сақталады, яғни индексі де сақталуы тиіс. Осы К индекстен жоғары жатқан барлық көрші элементтер жұбы қалаған ретте орналасатыны белгілі. Сондықтан тексеруді осы индекспен аяқтау керек, ал і үшін алдын-ала аяқталған төменгі шекке дейін барудың қажеті жоқ. Бұл жерден программист қандай да бір симметрияны байқауы мүмкін. Массивтің соңында дұрыс орналаспаған бір көпіршік бір електен өткізуде кері ретпен қажетті орынға орналасады, бірақ дұрыс орналаспаған массив соңындағы элемент әрбір електен өткізуде керекті орынға секіріп отырады. Мысалы, 12 18 42 44 55 67 94 06 Массивін жетілдірілген көпіршікті әдістің көмегімен бір електен өткізуде реттеуге болады, ал 94 06 12 12 18 42 44 55 67 Массивін сұрыптау үшін 7 рет електен өткізу қажет. Мұндай жағдайда симметрия 3 рет жетілдіруді қажет етеді: електен өткізудің бағытын кезектестіру. Мұндай алгоритм шейкерлік сұрыптау деп аталады. Бұл сұрыптау да 8 кілтпен жүзеге асырылады. Оның алгоритмі төмендегідей: Procedure Shaker (var item:DataArray; count: integer); Var J,k,l,r: integer; X:DataItem Begin l:=2; r:=count; k:= count; Repeat For j:=r downto l do If item[j-1] then Begin {алмастыру} X:=item[j-1]; item[j-1] := item [j]; item [j] :=x; k:=j; end; l:=k+1; For j:=l to r do If item [j-1] >item[j] then Begin { алмастыру } X:= item[j-1]; item[j-1] :=item[j]; item [j] :=x; k:=j; end; r:=k-l; until lend; жүктеу/скачать 1,32 Mb. Достарыңызбен бөлісу: