Algorytmy sortujące

Witam!
Postaram się omówić najważniejsze algorytmy sortujące.
W kodzie zostały przedstawione następujące algorytmy sortujące w języku C++:
– sortowanie bąbelkowe;
– sortowanie bąbelkowe ze znacznikiem;
– sortowanie przez wstawianie;
– sortowanie przez wybieranie;
– Quick Sort;
– sortowanie stogowe.

Sortowanie bąbelkowe

Najczęstszy i najprostszy w implementacji sposób sortowania elementów. Jednak pod względem algorytmicznym jest to metoda absorbująca dużą część zasobów systemowych. Najmniej zalecana.

Sortowanie bąbelkowe ze znacznikiem

Metoda bardzo dobra, gdy część naszych elementów jest już posortowana. Wówczas działa sprawnie.
Porównanie algorytmów

#include
#include
#include
#include
#include
#define N 40000

using namespace std;

void bable(int *tab);
void bableZeZnacznikiem(int *tab);
void wstawianie(int *tab);
void wybieranie(int *tab);
void quicksort(int *tab, int left, int right);
void stogowe(int *tab);
void przywracanie(int *tab, int k, int NN);
string nazwa(int ktory);

int NN;

int main(int argc, char **argv)
{
int wybor = 0;
bool autotest = true;
srand((unsigned) time(0));
int tab[N];
clock_t end, begin;
do {

if(autotest) {
cout << "*** Witaj wybierz proszę metodę sortowania z listy ***" << endl;
cout << "0 - AUTOTEST" << endl;
for(int i = 1; i < 7; i++)
cout << i << " - " << nazwa(i) << endl;
cout << "7 - KONIEC" << endl; cin >> wybor;
} else
wybor++;

for(int i = 0 ; i < N; i++) {
tab[i] = rand();
// cout << "[" << i << "]" << " " << tab[i] << "\t";
// if ( i%3 == 2 )
// cout << endl;
}
cout << "Losowanie ukończone! Przystępuje do sotowania. Czas start" << endl;
begin = clock();

switch(wybor) {
case 0:

autotest = false;
// break;
wybor++;
case 1:
bable(tab);
break;
case 2:
bableZeZnacznikiem(tab);
break;
case 3:
wstawianie(tab);
break;
case 4:
wybieranie(tab);
break;
case 5:
quicksort(tab, 0, N);
break;
case 6:
stogowe(tab);
break;
case 7:
return 0;
default:
cout << "Niepoprawny wybór, więc kończę!" << endl;
}

end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;

if(autotest) {
cout << endl << "Po posortowaniu:" << endl;

for(int i = 0 ; i < N; i++) {
cout << "[" << i << "]" << " " << tab[i] << "\t";
if(i % 3 == 2)
cout << endl;
}
cout << endl;
}
cout << "Czas potrzebny na posortowanie poprzez " << nazwa(wybor)
<< " wynosił: " << elapsed_secs << endl;
if(wybor == 6 && !autotest)
autotest = !autotest;
if(autotest) {
cout << "Naciśnij przycisk, aby kontynuować..." << endl;
cin.ignore();
cin.get();
}

} while(wybor != 7);
pause();
return 0;
}

void bable(int *tab)
{
int i, temp;
for(int nr = 0; nr < N - 1 ; nr++)
for(int i = 0; i < N - nr - 1; i++) if(tab[i] > tab[i + 1]) {
temp = tab[i];
tab[i] = tab[i + 1];
tab[i + 1] = temp;
}
}
void BableZeZnacznikiem(int *tab)
{
bool znacznik;
int i, temp;
int nr = 0;
do {
znacznik = 0;
int i, temp;
nr++;
for(i = 0; i < N - nr; i++) if(tab[i] > tab[i + 1]) {
temp = tab[i];
tab[i] = tab[i + 1];
tab[i + 1] = temp;
znacznik = 1;
}
} while(znacznik);
}

void Wstawianie(int *tab)
{
int nr, j, temp;

for(nr = 1; nr < N; nr++)
{
j = nr;
temp = tab[j];
while((j > 0) && (tab[j - 1] > temp))
tab[j] = tab[--j];
tab[j] = temp;
}
}
void Wybieranie(int *tab)
{
int j, x;
for(int i = 0; i <= N; i++) {
int k = i;
x = tab[i];
for(j = i + 1; j < N; j++)
if(tab[j] < x) {
k = j;
x = tab[j];
}
tab[k] = tab[i];
tab[i] = x;
}
}
void Quicksort(int *tab, int left, int right)
{
if(left < right) {
int m = left;
for(int i = left + 1; i <= right; i++)
if(tab[i] < tab[left])
swap(tab[++m], tab[i]);
swap(tab[left], tab[m]);
quicksort(tab, left, m - 1);
quicksort(tab, m + 1, right);
}
}

void stogowe(int *tab)
{ int k, temp;
int NN = N;
for(k = NN / 2; k > 0; k--)
przywracanie(tab, k, N);
do {
temp = tab[0];
tab[0] = tab[NN - 1];
tab[NN - 1] = temp;
NN--;
przywracanie(tab, 1, NN);
} while(NN > 1);
}

void przywracanie(int *tab, int k, int NN)
{
int i, j;
i = tab[k - 1];
while(k <= NN / 2)
{
j = 2 * k;
if((j < NN) && (tab[j - 1] < tab[j]))
j++;
if(i >= tab[j - 1])
break;
else {
tab[k - 1] = tab[j - 1];
k = j;
}
}
tab[k - 1] = i;
}

string nazwa(int ktory)
{
if(ktory == 1)
return ""Sortowanie bąbelkowe"" ;
else if(ktory == 2)
return ""Sortowanie bąbelkowe ze znacznikiem"" ;
else if(ktory == 3)
return ""Sortowanie przez wstawianie"" ;
else if(ktory == 4)
return ""Sortowanie przez wybieranie"" ;
else if(ktory == 5)
return ""Sortowanie - Quick Sort"" ;
else if(ktory == 6)
return ""Sortowanie Stogowe"" ;
}

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *