Sortowanie

[admin]

Sortowanie bąbelkowe.

Algorytm ten polega na porównywaniu i ewentualnej zamianie miejscami par sąsiadujących ze sobą elementów. Sortowanie rozpoczyna się od końca lub początku tablicy. Jeżeli sortujemy rosnąco, to ostatni element tablicy porównywany jest z tym stojącym przed nim. Jeżeli ostatni jest mniejszy od przedostatniego następuje zamiana miejscami. Jeżeli przedostatni jest mniejszy od ostatniego, to on staje się bąbelkiem i jest porównywany z kolejnymi.
Poszczególne elementy zmieniają miejsce w tablicy o jedną pozycje i powoli wędrują na swoje miejsce.
Algorytm jest dobry dla małych tablic częściowo już posortowanych. Jest to algorytm klasy O(N2)


#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int i,j,x,tmp;
int tablica[5];

/* wczytywanie liczb z klawiatury */

cout << "Podaj 5 liczb : \n";

for (i=0; i<=4; i++)
cin >>tablica[  i ];
/*wyświetlenie liczb w podanej kolejności*/
for (i=0; i<=4; i++)
{cout.width(3);cout << tablica[ i ];
}
cout << "\n\n";

/* sortowanie bąbelkowe */

for (i=0;i<=3; i++)
for (j=0;j<=3; j++)
if (tablica[j]>tablica[j+1])
{tmp = tablica[j];
tablica[j] = tablica[j+1];
tablica[j+1] = tmp;
}
cout << "\n";
/* wyświetlanie posortowanych liczb */
for (i=0; i<=4; i++)
{cout.width(3);cout << tablica[ i ];
}
cout<<endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

[admin]

Sortowanie szybkie

Algorytm sortowania szybkiego jest uważany za najszybszy algorytm dla danych losowych.
Zasada jego działania opiera się o metodę dziel i zwyciężaj.

Na początku wybiera się tzw. element osiowy (pewien element tablicy np. jej środek nazywany pivot), po czym na początek tablicy przenoszone są wszystkie elementy mniejsze od niego, na koniec większe, a w powstałe między tymi obszarami puste miejsca trafia wybrany element. Następnie sortuje się osobno początkową i końcową część tablicy.

Zbiór danych zostaje podzielony na dwa podzbiory i każdy z nich jest sortowany niezależnie od drugiego.
Dla zadanej tablicy A[1..p] wybieramy element p=A[l] i przeszukujemy resztę tablicy (tzn. A[l+1..p]) tak długo, aż nie znajdziemy elementu większego niż A[l]. Następnie przeszukujemy tą tablicę od strony prawej póki nie znajdziemy elementu nie większego niż A[l]. Gdy to osiągniemy, zamieniamy miejscami te dwa elementy i zaczynamy cały proces od początku. Algorytm działa tak długo, aż wskaźnik poruszający się w lewo i wskaźnik poruszający się w prawo spotkają się. Należy wówczas zamienić element p=A[l] z ostatnim elementem lewej części tablicy.

[admin]

Sortowanie przez kopcowanie ( kubełkowe).