Э. А. Абдыкеримова
Тура алмастыру кӛмегімен сҧрыптау (кӛпіршікті әдіс)
жүктеу/скачать 1,31 Mb. Pdf көрінісі
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
- Бұл бет үшін навигация:
- Шейкерлік сҧрыптау.
| 13.10 Тура алмастыру кӛмегімен сҧрыптау (кӛпіршікті әдіс)
Тура алмастыру алгоритмі кӛршілес элементтердің пар жҧбын салыстыру және орнын алмастыруға негізделген, мҧндай салыстыру мен алмастырулар барлық элементтер реттелгенше жалғастырылады. Егер массивтерді горизонталь емес вертикаль тҥрде қарастырсақ ондағы элементтерді судың кӛпіршіктері деп алуға болады. Оның әрбіреуінің салмағы оның кілтіне сәйкес келеді. Бҧл жағдайда әрбір жҥрісте бір кӛпіршік оның салмағына қарай деңгейге кӛтеріледі. Мысалы. Бҧл әдіс бойынша кӛрші тҧрған екі элемент салыстырылып, одан кейін сҧрыптау шартына тәуелді орындары алмасады. I = 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 PROCEDURE BybbleSort; VAR i,j, x: integer; BEGIN FOR i: =2 TO n DO FOR j: = n TO i DO If a[j-1]> a[j] THEN begin x: = a[j - 1]; a[j-1]:=a[j]; a[j]: = x end END; - + - + басы n , a 1 … a n енгізу i:=2 j:=n a j-1 > a j x:= a j-1 a j-1 := a j a j :=x j:=j-1 j i i:=i+1 i n a 1 … a n шығару соңы + - 100 Шейкерлік сҧрыптау. Кӛпіршік сҧрыптау алгоритмін жақсарту тәсілі – қандай да бір жҥріс процесінде ауыстырулар болды ма, болмады ма соны сақтап отыру болып табылады. Егер соңғы жҥрісте ауыстырулар болмаса, онда алгоритмді аяқтауға болады. Алайда, егер ауыстырулар болғандығы туралы фактыны ғана сақтап қоймай, сонымен қатар соңғы ауыстыру орнын (индексін) да сақтаса бҧл жақсартуды тағы да жақсартуға болады. Осы k индексінен жоғары орналасқан барлық кӛрші элементтердің жҧптары керекті ретпен орналасқан. Сондықтан қарастыруды осы индекспен аяқтауға болады. Алдын ала анықталған i-дің тӛменгі шегіне дейін жетпей-ақ қарастыруды осы k индекімен аяқтауға болады. Ҥшінші жақсарту: тізбектеп қарастырулардың бағытын алмастыру. Осылайша алынған алгоритм « шейкерлік » сұрыптау (ShakerSort) деп аталады. Шейкерлік сҧрыптау мысалы L = 2 3 3 4 4 R = 8 8 7 7 4 Dir = 44 06 06 06 06 55 44 44 12 12 12 55 12 44 18 94 12 42 18 42 18 94 18 55 55 06 18 67 67 67 67 67 94 94 94 PROCEDURE ShakerSort; VAR j, k, L, R, x: integer; BEGIN L: = 2; R: = n; k: = n; REPEAT FOR j: = R DOWNTO L DO IF a[j-1]>a[j] THEN BEGIN x: = a[j-1]; a[j-1]:=a[j]; a[j]: = x; k: = j END; L: = k+1; FOR j:=L to R do IF a[j-1]>a[j] THEN BEGIN x:=a[j-1];a[j-1]:=a[j];a[j]:=x;k:=j END; R:=k-1 UNTIL L>R END; { ShakerSort} жүктеу/скачать 1,31 Mb. Достарыңызбен бөлісу:
|