Қазақстан республикасының бiлiм және ғылым министрлiгi
жүктеу/скачать 0,78 Mb.
|
364bd4d0-c314-11e5-bf37-f6d299da70eeМетод лекцииМСП
Алгоритм тектен тек жылдам деп атамаған, өйткені, оның салыстырулар және алмасулар саны O(n?log n) жазбасымен бағаланады. Жылдам сұрыптау әдісі бағдарламасының мәтіні class QuckSorter : FileSorter {int M;QuckSorter(string name, string[] files, int m) : base(name, files) {.M = m;
}override FileSorter Copy(string name, string [] files) {new QuckSorter(name, files, M); }void simpleSort(ref int[] list, int start, int end) {(int i = start; i <= end; i++)(int j = i; j <= end; j++)(list[i] > list[j]) {loc = list[i];[i] = list[j];[j] = loc; } }override void beginSort(ref int[] list, int start, int end) {len = end - start + 1;(len <= 0) {; }if (len <= M) {(ref list, start, end); }if (len > M) {x = list[(start + end) / 2];i = start;j = end; {(list[i] < x) ++i;(list[j] > x) --j;(i <= j) {loc = list[i];[i] = list[j];[j] = loc;++; j--; } } while (i <= j);(start < j)(ref list, start, j);(i < end)(ref list, i, end); } } } Разряд бойынша сұрыптау әдісінің бағдарламалық мәтіні class RadixSorter : FileSorter {RadixSorter(string name, string[] files) : base(name, files) { }int getDigit(int i, int digit) {(i / (int)Math.Pow(10, digit - 1)) % 10; } override void beginSort(ref int[] list, int start, int end) {range = 10;m = 10; { //тізімді таңдаймыз(int j = 0; j < list.Length; j++) {temp = getDigit(list[j], i);[temp].Insert(0, list[j]); } //Тізімдерді желімдейміз l = 0;(int j = 0; j < range; j++) {(int z = arr[j].Count - 1; z >= 0; z--)[l++] = arr[j][z];[j].Clear(); } } }override FileSorter Copy(string name, string[] files) {new RadixSorter(name, files); } }
Екі айнымалы еңгізейік: i және j. Алгоритмнің басында олар массивтің сол жақ және оң жақтарын белгілейді. I белгісін 1 элементке тең қадамымен массивтің соңына a[i] >= p элементі табылғанша жылжытамыз. Содан кейңн ұқсас түрде j массивтың соңынан басына қарай a[j] <= p элементі табылғанша жылжытамыз. Содан кейін, егер i <= j шарты орындалса, a[i] және a[j] элементтерін орындарымен алмастырамыз, және i және j белгілерін тура сол бағыттар бойынша жылжыта береміз... Үшінші қадамды i <= j шарты орындалғанша қайталай береміз. a[0]...a[6] массиві үшін процедураның жұмысын қарастырайық, p = a[3]. Енді массив екі бөлікке бөлінген: сол жақ элементтерінің барлығы р-ға тең немесе одан кіші, оң жақтың элементтері р-ға тең немесе одан үлкен. Бөлу процессі аяқталды. Жалпы алгоритм quickSort ( a массиві, N жоғарғы шек) { p – массивтің ортасын табу Массивті бұл элемент бойынша бөлу Егер сол жақтағы массивте элементтер саны бірден асса, quickSort процедурасын ол үшін шақыру. Егер оң жақтағы массивте элементтер саны бірден асса, quickSort процедурасын ол үшін шақыру. Сурет 9. Алгоритмнің блок-сұлбасы Бұл сұрыптауды лездік деп, ол салыстырулар арқылы орындалатын сұрыптаулар ішіндегі ең жылдамы болғандықтан аталады. Әдістің әр қадамында біз ортақ мәнді табамызда, және массивті үш массивке бөлінгендей көрсетеміз: басында ортақ мәннен кіші элементтер қойлады, содан кейін оған тең, ең соңында одан үлкен элементтер. Енді жаңағы айтылған алгоритмді бағдарлама түрінде жазайық procedure Sort; procedure QuickSort(a, b: Longint); Var
x: Longint; { «ортақ» элементтің индексі} begin
x := ортақ_элемент; ...үш бөлікке бөлу: 1) A[a]..A[i]; 2) A[i+1]..A[j-1]; 3) A[j]..A[b] if i>a then QuickSort(a, i); if b>j then QuickSort(j, b); end;
begin Sort(1, N); end; ортақ мәнді табу – оңай процесс емес i := A[l]; y := A[(l+r)div 2]; j := A[r]; if i<=y then if y<=j then x := (l+r)div 2 else if i<=j then x := r else
x := l else
if y>=j then x := (l+r)div 2 else if i>=j then x := r else
x := l; Енді массивті A[x] элементі бойынша бөлу керек. A[x] ортақ элемент. i := l; j := r; x := A[x]; repeat
while A[i] < x do Inc(I); while x < A[j] do Dec(j); if i <= j then begin
y := A[i]; A[i] := A[j]; A[j] := y; Inc(i); Dec(j); end; until i > j; енді бізге тек бағдарламаның үш бөлігін біріктіру ғана қалды procedure Sort; procedure QuickSort(a, b: Longint); Var
x: Longint; { «ортақ» элементтің индексі} begin
i := A[l]; y := A[(l+r)div 2]; j := A[r]; if i<=y then if y<=j then x := (l+r)div 2 else if i<=j then x := r else
x := l else
if y>=j then x := (l+r)div 2 else if i>=j then x := r else
x := l; i := l; j := r; x := A[x]; repeat while A[i] < x do Inc(i); while x < A[j] do Dec(j); if i <= j then begin y := A[i]; A[i] := A[j]; A[j] := y; Inc(i); Dec(j); end;
until i > j; if l-j begin
if l < j then QuickSort(l, j); end else
begin if i < r then Sort(i, r); if l < j then Sort(l, j); end;
end; begin
QuickSort(1, N); end;
Ең жаман жағдайда бұл алгоритм уақытша күрделілік береді Tmax(N2) (егер ортақ элементті таңдаулардың барлығы сәтсіз өтсе), бірақ теориялық зерттеулер көрсеткендей мұндай жағдайдың пайда болу ықтималдылығы өте төмен. Ортақ және ең үздік жағдайда T(N*log(N)) осындай күрделілікке ие боламыз. Мысалы:
60, 79, 82, 58, 39, 9, 54, 92, 44, 32 60, 79, 82, 58, 39, 9, 54, 92, 44, 32 9,79, 82, 58, 39, 60, 54, 92, 44, 32 9,79, 82, 58, 39, 60, 54, 92, 44, 32 9, 32, 82, 58, 39, 60, 54, 92, 44, 79 9, 32, 44, 58, 39, 60, 54, 92, 82, 79 9, 32, 44, 58, 39, 54, 60, 92, 82, 79 9, 32, 44, 58, 39, 92, 60, 54, 82, 79 9, 32, 44, 58, 39, 54, 60, 79, 82, 92 9, 32, 44, 58, 54, 39, 60, 79, 82, 92 9, 32, 44, 58, 60, 39, 54, 79, 82, 92 9, 32, 44, 58, 54, 39, 60, 79, 82, 92 9, 32, 44, 58, 54, 39, 60, 79, 82, 92 9, 32, 44, 58, 54, 39, 60, 79, 82, 92 9, 32, 39, 58, 54, 44, 60, 79, 82, 92 9, 32, 39, 58, 54, 44, 60, 79, 82, 92 9, 32, 39, 44, 54, 58, 60, 79, 82, 92 9, 32, 39, 44, 58, 54, 60, 79, 82, 92 9, 32, 39, 44, 54, 58, 60, 79, 82, 92 9, 32, 39, 44, 54, 58, 60, 79, 92, 82 9, 32, 39, 44, 54, 58, 60, 79, 82, 92 N нақты сандарынан тұратын А массивін өсу реті бойынша жылдам сұрыптау. program Quick_Sort; var A:array[1..100] of integer; N,i : integer; {Ішкі программаға сұрыпайтын бөліктің оң және сол жақ шекаралары беріледі} procedure QSort(L,R:integer); var X,y,i,j:integer; begin X:=A[(L+R) div 2]; i:=L; j:=R; while i<=j do begin while A[i] while A[j]>X do j:=j-1;
if i<=j then begin
y:=A[i]; A[i]:=A[j]; A[j]:=y; i:=i+1; j:=j-1;
end;
if L if i end;
write('массив элементтерінің саны'); read(N);
for i:=1 to n do read(A[i]); QSort(1,n); {элементтерді біріншіден n-шіге дейін реттеу}
for i:=1 to n do write(A[i],' '); {реттелген массив} end.
жүктеу/скачать 0,78 Mb. Достарыңызбен бөлісу:
|