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).