Question

Napisz przynajmniej 5. algorytmów.

Answer 1

Http://algorytmy.blox.pl/2008/04/5-algorytmow-sortowania.html

Masz tam wszystko ;p

Answer 2

Czy ten algorytm nie jest prosty (keep it simple)? Jeśli kiedyś zdarzy Ci się, że komputer dozna awarii, dziewczyna Cię dawno olała, a doręczyciel pizzy się spóźnia - możecie spróbować posortować w ten sposób talię zawierającą 55 kart. Implementacja (tak jak sam algorytm) jest bardzo prosty:

void Shuffle(int* A, int N)
{
for (int i = 0; i < N; i++)
{
int r = i + rand() % (N-i);
int temp = A[i];
A[i] = A[r];
A[r] = temp;
}
}

void BogoSort(int* A, int N)
{
while (!IsSort(A, N)) Shuffle(A, N);
}

Implementację funkcji IsSort podaję poniżej. Algorytm sortuje w miejscu, nie jest niestety stabilny [ogłaszam konkurs na napisanie poprawki do algorytmu, by stał się stabilny]. Algorytm ten zaimplementowany na komputerze kwantowym działa w czasie liniowym ;)

BozoSort (aka MonkeySort)

Kolejny ciekawy algorytm

1. Jeśli talia jest posortowana - zakończ algorytm
2. Zmień miejscami dwa wybrane losowo elementy
3. Przejdź do 1.

void Swap(int* A, int N)
{
int r1 = rand() % N;
int r2 = rand() % N;

int temp = A[r1];
A[r1] = A[r2];
A[r2] = temp;
}

void BozoSort(int* A, int N)
{
while(!IsSort(A, N)) Swap(A, N);
}

Podobnie jak BogoSort algorytm działa w miejscu, ale nie jest stabilny. Bardzo chętnie w komentarzach przeczytam jak zmienić ten algorytm aby był stabilny (nie dbaj o złożoność).

IsSort()

Funkcję IsSort można zaimplementować na kilka sposobów. Pierwszym z nich jest prosta pętla:

bool IsSort(int* A, int N)
{
for (int i = 1; i < N; i++)
if (A[i-1] > A[i]) return false;
return true;
}

Ale skoro dzisiaj szalejemy :)

bool IsSort(int* A, int N)
{
int* B = new int[N];

for (int i = 0; i < N; i++)
B[i] = A[i];

Sort(B, N);

for (int i = 0; i < N; i++)
if (A[i] != B[i]) return false;
return true;
}