Źródła najważniejszych sortowań w C++

Do napisania tego artykułu skłoniły mnie problemy ze znalezieniem w sieci przejrzystych i łatwych w interpretacji źródeł sortowań. W źródłach z sieci często zupełnie niepotrzebnie stosowane są zaawansowane techniki, czy struktury programistyczne, które utrudniają początkującym wychwycenie istoty danej metody sortowania. Ten artykuł powstał, aby dostarczyć Wam źródła tych sortowań w możliwie najprostszej i najkrótszej formie. Nie chcę się bawić w wyjaśnianie zasad działania konkretnych sortowań - są już dobre strony zajmujące się tą tematyką (w linkach podaję dwa dobre adresy). Najtrudniejsze zastosowane w tych źródłach elementy to dynamiczne przydzielanie pamięci (obyło by się bez niego), losowanie liczb do tablicy (tylko do prezentacji działania), oraz w dwóch przypadkach rekurencja. Wszystkie podane źródła można przetestować - zaraz po uruchomieniu zostaniemy poproszeni o podanie dwóch liczb. Pierwsza to długość tablicy do posortowania, druga określa od zera do ilu mają być losowane liczby w tablicy. Ok, przejdźmy wreszcie do rzeczy.

sortowanie bąbelkowe (bubblesort)

#include <iostream>

using namespace std;

int main()
{
    long i, j, n, m, *tablica;
    cin >> n >> m;
    tablica = new long [n];
    srand(time(NULL));
    for(i=0; i<n; i++)
        tablica[i]=rand() % (m+1);

    for(i=0; i<n-1; i++)
        for(j=0; j<n-1; j++)
            if(tablica[j]>tablica[j+1])
                swap(tablica[j], tablica[j+1]);

    for(i=0; i<n; i++)
        cout << tablica[i] << " ";
    cout << "\n";
    delete tablica;
    tablica=0;
    return 0;
}

sortowanie przez wybór (selectionsort)

#include <iostream>

using namespace std;

int main()
{
    long i, j, n, m, min, min_index, *tablica;
    cin >> n >> m;
    tablica = new long [n];
    srand(time(NULL));
    for(i=0; i<n; i++)
        tablica[i]=rand() % (m+1);

    for(i=0; i<=n-1; i++)
    {
        min_index=i;
        min=tablica[i];
        for(j=i+1; j<n; j++)
            if(tablica[j]<min)
            {
                min_index=j;
                min=tablica[j];
            }
        tablica[min_index]=tablica[i];
        tablica[i]=min;
    }

    for(i=0; i<n; i++)
        cout << tablica[i] << " ";
    cout << "\n";
    delete tablica;
    tablica=0;
    return 0;
}

sortowanie przez wstawianie (insertionsort)

#include <iostream>

using namespace std;

int main()
{
    long i, j, k, n, m, *tablica;
    cin >> n >> m;
    tablica = new long [n];
    srand(time(NULL));
    for(i=0; i<n; i++)
        tablica[i]=rand() % (m+1);

    for (i=1; i<n; i++)
    {
        j=i;
        k=tablica[i];
        while(tablica[j-1]>k && j>0)
        {
            tablica[j]=tablica[j-1];
            j--;
        }
        tablica[j]=k;
    }

    for(i=0; i<n; i++)
        cout << tablica[i] << " ";
    cout << "\n";
    return 0;
}

sortowanie przez scalanie (mergesort)

#include <iostream>

using namespace std;
void mergesort(long tab[], long pocz, long kon);
long n;

int main()
{
    long i, j, m, *tablica;
    cin >> n >> m;
    tablica = new long [n];
    srand(time(NULL));
    for(i=0; i<n; i++)
        tablica[i]=rand() % (m+1);
    
    mergesort(tablica, 0, n-1);

    for(i=0; i<n; i++)
        cout << tablica[i] << " ";
    cout << "\n";
    delete tablica;
    tablica=0;
    return 0;
}

void mergesort(long tab[], long pocz, long kon)
{
    long i, j, k, srodek, *temp = new long [n];
    srodek=(pocz+kon+1)/2;
    if(srodek-pocz > 1)
        mergesort(tab, pocz, srodek-1);
    if(kon-srodek > 0)
        mergesort(tab, srodek, kon);
    j=pocz;
    k=srodek;
    for(i=pocz; i<=kon; i++)
        temp[i]=(j==srodek || (k<=kon && tab[j]>tab[k])) ? tab[k++] : tab[j++];
    for(i=pocz; i<=kon; i++)
        tab[i]=temp[i];
    delete temp;
    temp=0;
}

sortowanie "szybkie" (quicksort)

#include <iostream>

void quicksort(long tab[], long x, long y);
using namespace std;

int main()
{
    long i, j, n, m, *tablica;
    cin >> n >> m;
    tablica = new long [n];
    srand(time(NULL));
    for(i=0; i<n; i++)
        tablica[i]=rand() % (m+1);

    quicksort(tablica, 0, n);

    for(i=0; i<n; i++)
        cout << tablica[i] << " ";
    cout << "\n";
    delete tablica;
    tablica=0;
    return 0;
}

void quicksort(long tab[], long x, long y)
{
    int i,j,v,temp;
    i=x;
    j=y;
    v=tab[(x+y)/2];
    do
    {
        while(tab[i]<v)
            i++;
        while(v<tab[j])
            j--;
        if(i<=j)
        {
            swap(tab[i], tab[j]);
            i++;
            j--;
        }
    }
    while(i<=j);
    if(x<j) quicksort(tab, x, j);
    if(i<y) quicksort(tab, i, y);
}

sortowanie kopcowe/stogowe (heapsort)

#include <iostream>

using namespace std;

int main()
{
    long i, j, k, n, m, x, *tablica;
    cin >> n >> m;
    tablica = new long [n+1];
    srand(time(NULL));
    for(i=1; i<=n; i++)
        tablica[i]=rand() % (m+1);
    
    for(i=2; i<=n; i++)
    {
        j=i;
        k=j/2;
        x=tablica[i];
        while(k>0 && tablica[k]<x)
        {
            tablica[j]=tablica[k];
            j=k;
            k=j/2;
        }
        tablica[j]=x;
    }
    for(i=n; i>1; i--)
    {
        swap(tablica[1], tablica[i]);
        j=1;
        k=2;
        while(k<i)
        {
            if(k+1<i && tablica[k+1]>tablica[k]) m=k+1;
            else m=k;
            if(tablica[m]<=tablica[j]) break;
            swap(tablica[j], tablica[m]);
            j=m;
            k=2*j;
        }
    }

    for(i=1; i<=n; i++)
        cout << tablica[i] << " ";
    cout << "\n";
    delete tablica;
    tablica=0;
    return 0;
}

W przypadku tego sortowania należy uważać przy modyfikowaniu go - przykładowo jeśli chcemy podać tablicę wpisaną na sztywno np. {5, 3, 4}, to pierwszy element zostanie pominięty. Wystarczy zmienić taką tablicę np. tak: {0, 5, 3, 4}, wtedy wynikiem będzie 3, 4, 5.

Polecane linki:
http://www.i-lo.tarnow.pl/edu/inf/alg/algsort/index.html - świetny opis zasad działania poszczególnych sortowań
http://ww.uni.torun.pl/~abak/wdimat/s/Index.html - krótkie opisy sortowań - dające ogólne pojęcie o działaniu

Niniejszy artykuł jest dostępny na licencji Creative Commons Uznanie autorstwa - Użycie niekomercyjne - Na tych samych warunkach 2.5 Polska. Zrzekam się przy tym wszelkich praw do zamieszczonych tutaj źródeł programów.

<< Powrót

Komentarze:

hardtmuth | 18:33 | 05.09.2006
Widze, ze coraz wiecej sie dzieje na stronce. Ucz sie do sesji, a nie bawisz sie programowaniem :D

sadi | 21:11 | 07.09.2006
Trochę rozrywki trzeba mieć ;)

Yugo | 15:17 | 27.12.2006
Fajne ;P

Wojdanek | 21:22 | 16.03.2009
Wymagają tego od nas w I klasie LO ;D

Wszystkie przedstawione tutaj opinie należą do ich autorów i twórca strony nie ponosi żadnej odpowiedzialności za ich treść.

W polu "Strona WWW" wpisywanie członu "http://" nie jest konieczne. Tagi (X)HTML wpisane w treści nie będą działać jako element strony, zamiast tego pojawią się w samym komentarzu. Komentarze obraźliwe, nie na temat lub niezgodne z prawem będą w miarę możliwości usuwane.