Algorytmy sortujące w czasie O(n2)

Sortowanie przez wstawianie (insertion sort)

Przykład

Jest to najczęściej używana procedura sortująca, szczególnie dobrze działająca dla małych n.
W k-tym kroku pętki for elemety o numerach od 0 do k-1 są już posortowane. Te z nich, które są większe od t[k] są "podsuwane" o jedno miejsce w górę, a element t[k] jest wstawiany w powstalą po ich podsunięciu "dziurę".

insertion_sort1.cc 
#include <iostream>

using namespace std;
////////////////////////////////////////////////////////////////////////////
/// procedura wstawia x na właściwe miejsce w posortowanej tablicy n liczb
/// zakładamy, że faktyczny rozmiar tablicy wynosi co najmniej n+1 tzn.
/// jest co najmniej jedno miejsce wolne za końcem tablicy
////////////////////////////////////////////////////////////////////////////
inline void wstaw(double t[],int n,double x)
{while(n && t[n-1]>x)
   {t[n]=t[n-1];
    n--;
   }
 // tutaj n==0 lub t[n-1] <= x
 t[n]=x;
}

/////////////////////////////////////////////////////////////////////////////
/// sortowanie przez wstawianie 
/// w i-tym kroku algorytmu elemety t[0] ... t[i-1] są już posortowane
/////////////////////////////////////////////////////////////////////////////
void sortuj(double t[],int n)
{for(int i=1;i<n;i++)
   wstaw(t,i,t[i]);
}


//////////////////////////////////////////////////////////////////////////////
void pokaz(double t[],int n)
{for(int i=0;i<n;i++)
   cout<<t[i]<<' ';
 cout<<endl;
}


int main()
{double t[]={2,3,3,21,5,4,3,6,5,7,6,5,8,7,6,5,4,5,9,3,1,0};

 sortuj(t,22);
 pokaz(t,22);
 system("pause");
 return 0;
}

Wersja z wartownikiem jest od 10% do 30% szybsza

insertion_sort_sentinel.cc 
#include <iostream>

void sort2(double &a, double &b)
{if(a>b) {double c=a;a=b;b=c;}
}

using namespace std;
////////////////////////////////////////////////////////////////////////////
///  Procedura wstawia x na właściwe miejsce w częściowo posortowanej tablicy.
///  Zakładamy, że elementy na lewo od x są posortowane oraz pierwszy z nich
//   jest mniejszy od x.
///  Dzięki temu możemy zrezygnować ze sprawdzania, czy nie wyszliśmy poza tablicę.
///  t - wskazuje na miejsce, w którym stoi x (x==t[0])
//   (nie wiemy gdzie jest początek tablicy i nie obchodzi nas to)
////////////////////////////////////////////////////////////////////////////
inline void wstaw_z_wartownikiem(double *t, double x)
{while(t[-1]>x)
   {t[0]=t[-1];
    t--;
   }
 // tutaj t[-1] <= x
 t[0]=x;
}

/////////////////////////////////////////////////////////////////////////////
///  sortowanie przez wstawianie 
///  w i-tym kroku algorytmu elemety t[0] ... t[i-1] są już posortowane
/////////////////////////////////////////////////////////////////////////////
void sortuj_z_wartownikiem(double t[],int n)
{// umieść element najmniejszy na początku tablicy 
 for(int j=n-1;j>0;j--)
   sort2(t[j-1],t[j]); 
 // posortuj pozostałe elementy traktując t[0] jako wartownika
 for(int i=2;i<n;i++)
   wstaw_z_wartownikiem(t+i,t[i]);
}


//////////////////////////////////////////////////////////////////////////////
void pokaz(double t[],int n)
{for(int i=0;i<n;i++)
   cout<<t[i]<<' ';
 cout<<endl;
}


int main()
{double t[]={2,3,3,21,5,4,3,6,5,7,6,5,8,7,6,5,4,5,9,3,1,0};

 sortuj_z_wartownikiem(t,22);
 pokaz(t,22);
 return 0;
}