Algorytmy sortowania w języku C(C++)












Strona Piotra Różnickiego v3.0









Strona główna
Wstęp
Nauka
Programy
Rozrywka
Pomoc
Księga gości
Kontakt



Algorytmy sortowania w języku C(C++)


Inne strony o tej tematyce:
Algorytmy przeszukiwania w języku C(C++)
Język C++ - ściąga z programowania obiektowego (autor : Piotra Różnicki)
Język C ,opis języka - struktury dynamiczne (autor : Robert Chwastek)
Kurs języka C - opracowany przez mojego kolegę.
Przykładowe programy w C i C++



Sortowanie bąbelkowe O(N2)
Dwustronne sortowanie bąbelkowe O(N2)
Sortowanie szybkie O(Nlog2N)
Powrót na początek strony
Objaśnienia:
Typ_elementu typ elementu zdefiniowany np. przez typedef int Typ_elementu;
tablica[max_rozmiar] - tablica o rozmiarze max_rozmiar przechowująca dane typu Typ_elementu przeznaczone do sortowania
lewy - lewa granica tablicy przeznaczonej do sortowania(początek)
prawy - prawa granica tablicy przeznaczonej do sortowania(koniec).
Sortowanie bąbelkowe
Algorytm ten polega na porównywaniu i ewentualnej zamianie miejscami par sąsiadujących ze sobą elementów. 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)

void SortowanieBabelkowe(Typ_elementu *tablica)
{
int dalej=1;
while (dalej)//sortuj az wszystko posortowane
{
dalej=0;
for (int i=0;i<max_rozmiar-1 ;i++ )
{
if (*(tablica+i)>*(tablica+i+1) )
{
Typ_elementu tmp;
tmp=*(tablica+i);
*(tablica+i)=*(tablica+i+1);
*(tablica+i+1)=tmp;
dalej=1;
}
}

}
}

Powrót na początek strony
Sortowanie ShakerSort (przetasowanie)Algorytm zwany też dwukierunkowe
sortowanie bąbelkowe - różni się od bąbelkowego jedynie tym, że odbywa się w dwóch kierunkach.

void ShakerSort(Typ_elementu *tablica)
{
int lewy=1,prawy=max_rozmiar-1,k=max_rozmiar-1;
do
{
for(int j=prawy; j>=lewy; j--)
if(tablica[j-1]>tablica[j])
{
przestaw(tablica[j-1],tablica[j]);//funcja zamienia argumenty miejscami
k=j;
}
lewy=k+1;
for(int j=lewy; j<=prawy; j++)
if(tablica[j-1]>tablica[j])
{
przestaw(tablica[j-1],tablica[j]);//funcja zamienia argumenty miejscami
k=j;
}
prawy=k-1;
}
while (lewy<=prawy);
}

Powrót na początek strony
Sortowanie szybkie(QSort)Jest to dość szybki algorytm klasy  O(Nlog2N).
Algorytm przebiega następująco : dzielimy calą tablicę na dwie części wg. pewnej liczby dzaiłowej(pierwsza z tej tablicy). Wszystkie
mniejsze od niej są przerzucane przed nią, a większe za nią.
Procedura wywołuje samą siebie dla liczb mniejszych od liczby działowej, a później dla liczb większych od liczby działowej.
Tablica ta jest dzielona na coraz to mniejsze części przez kolejne rekurencyjne wywołania procedury do czasu, gdy w danym fragmencie tablicy
zostanie tylko jedna liczba.

void qsort(Typ_elementu *tablica,int lewy, int prawy)
{
if (lewy < prawy)
{
int m=lewy;
for(int i=lewy+1;i<=prawy;i++)
if (tablica[i]<tablica[lewy])
przestaw(tablica[++m],tablica[i]);
przestaw(tablica[lewy],tablica[m]);//Powrót na początek strony












Strona główna

|

Wstęp

|

Nauka

|

Programy
|

Rozrywka
|

Pomoc





© 2000 Piotr Różnicki.