Odpowiedzi

Najlepsza Odpowiedź!
2010-01-16T11:44:56+01:00
Np. bardzo szybki algorytm sortowania przez zliczanie - złożoność O(n).
Implementacja C++
A - tablica,
size - rozmiar tablicy,
max - maxymalna wartość elementu w tablicy,
założenie - w tablicy masz liczby >= 0
Po wywołaniu funkcji będziemy mieć posortowaną rosnąco tablicę A.

void counting_sort(int *A, int size, int max) {
int *B=new(int[size]); // temp
int *C=new(int[max+1]); // indexy
for(int i=0; i<=max; i++)// można też użyć memset()
C[i]=0;
for(int i=0; i<size; i++) // zliczanie
C[A[i]]++;
for(int i=1; i<=max; i++) // obliczanie indexow
C[i]+=C[i-1];
for(int i=size-1; i>=0; i--) {
B[C[A[i]]-1]=A[i];
C[A[i]]--;
}
for(int i=0; i<size; i++)
A[i]=B[i];
delete[] B;
delete[] C;
}
2010-01-16T15:34:49+01:00
Ten algorytm jest zapisany w Pascalu i wykorzystuje sortowanie bąbelkowe :

program p_3_1;
uses crt;
var i,j,k:byte;
t:array[1..99]of byte;

begin
randomize;
for i:=1 to 99 do t[i]:=random(200);
for i:=1 to 98 do
for j:=i+1 to 99 do
if t[i]>t[j] then
begin
k:=t[i];
t[i]:=t[j];
t[j]:=k;
end;
for i:=1 to 99 do write(t[i]:4);
readln;
end.

Jeśli chcesz zmienić wartość liczb to zmień w linijce
for i:=1 to 99 do t[i]:=random(200); na
for i:=1 to 99 do t[i]:=i;