Sortowanie wg tego algorytmu powoduje pobieranie kolejnego elementu z analizowanego podciągu i wstawienie go w odpowiednie miejsce w podciągu posortowanym, który narasta od lewej strony analizowanego ciągu.
Przykład działania tego algorytmu przedstawiony jest poniżej:
Przykład sortowania przez wstawianie
|
||||||||||||||||||||
|
||||||||||||||||||||
|
||||||||||||||||||||
|
||||||||||||||||||||
|
||||||||||||||||||||
|
||||||||||||||||||||
|
||||||||||||||||||||
|
||||||||||||||||||||
|
||||||||||||||||||||
|
Algorytm:
void InsertSort(long* tab, long n)
{
long porownan=0,przestawien=0;
long i,j,x;
for(i=1;porownan++,i<n;i++)
{
x=tab[i];
for(j=i-1;porownan++,j>=0;j--)
{
porownan++;
if(tab[j]>x)
{
przestawien++;
tab[j+1]=tab[j];
}
else
break;
}
tab[j+1]=x;
}
cout<<"InsertSort.Por.="<<porownan<<"; Przest.="<<przestawien<<endl;
}
Metoda ta polega na wybieraniu z całego ciągu liczby najmniejszej oraz największej i wstawienie ich odpowiednio na lewy i prawy kraniec analizowanego podciągu. Po każdej takiej zmianie analizowany podciąg zostaje pomniejszony o 1 element z lewej i z prawej, które w danym momencie są już posortowane.
Przykład sortowania przez selekcję
|
||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||
|
Algorytm:
void SelectSort(long* tab, long n)
{
long porownan=0,przestawien=0;
long i,start,stop;
long min,max, mini, maxi;
long pom;
for(start=0,stop=n-1;porownan++,start<=stop;start++,stop--)
{
min=max=tab[start];
mini=maxi=start;
for(i=start+1;porownan++,i<=stop;i++)
{
if (porownan++,tab[i]>max) {max=tab[i]; maxi=i;}
if (porownan++,tab[i]<min) {min=tab[i]; mini=i;}
}
pom=tab[start];
tab[start]=min;
tab[mini]=pom;
przestawien++;
pom=tab[stop];
tab[stop]=max;
tab[maxi]=pom;
przestawien++;
}
cout<<"SelectSort.Por.="<<porownan<<"; Przest.="<<przestawien<<endl;
}
Metoda ta opiera się na porównywaniu dwóch sąsiadujących ze sobą wartości i ustawieniu ich w odpowiednim porządku. Porównywanie wykonywane jest tak długo, aż nie zostanie wykonane żadne przestawienie. W przypadku dojścia z porównywaniem do końca ciągu, rozpoczyna się ono od początku. Dodatkowo wiemy, że gdy ostatnia zamiana nastąpiła na danym polu, to wszystkie pola znajdujące się za nim są już uporządkowane.
Przykład sortowania przez wstawianie
|
|||||||||||||||||||
|
|||||||||||||||||||
|
|||||||||||||||||||
|
|||||||||||||||||||
|
|||||||||||||||||||
|
|||||||||||||||||||
|
|||||||||||||||||||
|
|||||||||||||||||||
|
Algorytm:
void BubbleSort(long* tab, long n)
{
long porownan=0,przestawien=0;
long i,stop;
long pom;
long ostzam;
for(stop=n-1;porownan++,stop>0;stop=ostzam)
{
ostzam=0;
for(i=0;porownan++,i<stop;i++)
{
if (porownan++,tab[i]>tab[i+1])
{
ostzam=i;
przestawien++;
pom=tab[i];
tab[i]=tab[i+1];
tab[i+1]=pom;
}
}
}
cout<<"BubbleSort.Por.="<<porownan<<"; Przest.="<<przestawien<<endl;
}
Algorytm ten pozwala sortować dowolne dane. Przy jego pomocy także możliwe jest bardzo szybkie stworzenie ciągu posortowanego wykorzystując do tego pomocniczą tablicę indeksów.
Tablica ta zawiera tylko i wyłącznie indeksy z tablicy nieposortowanej, a stworzenie posortowanego ciągu polega na wypisaniu elementów z tablicy pierwotnej zgodnie ze schematem stworzonym przez kolejne odczytywanie indeksów z tablicy indeksów. Kluczową rolą jest tutaj oczywiście prawidłowe umieszczenie właściwych numerów na właściwych miejscach w tablicy indeksu, co może być rozwiązane na wiele różnych sposobów. W zaproponowanym algorytmie określenie pozycji dla danego elementu polega na zliczeniu, ile występuje w ciągu elementów o wartości mniejszej od badanego.
Algorytm:
int *sort_index(int *tab, int n)
{
int *index; //tablica indeksów
int *posortowana;
int a,b;
int poz_w_index;
index=new int[n];
for(a=0;a<n;a++)
{
poz_w_index=0;
for(b=0;b<n;b++)
{
if (tab[b]<tab[a]) poz_w_index++;
else if ((b<a) && (tab[b]==tab[a])) poz_w_index++;
}
index[poz_w_index]=a;
}
posortowana=new int[n];
for(a=0;a<n;a++)
posortowana[a]=tab[index[a]];
delete []index;
return posortowana;
}