Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

Sortowanie przez wstawianie

powrót

Ten rodzaj sortowania możemy porównać do układania kart pokerzysty. Pierwszą kartę wstawiamy w odpowiednie miejsce przesuwając pozostałe, następną także wstawiamy między odpowiednie karty i tak układamy zestaw kart.

Prześledźmy przykład na następującym ciągu liczb:

{tex}2,\ 5,\ 3,\ 0,\ 7,\ 1{/tex}

Strategia algorytmu:

  • Rozpoczynamy od drugiego elementu, czyli {tex}5{/tex} i porównujemy go z elementami poprzedzającymi - w tym przykładzie poprzedza tylko liczba {tex}2{/tex}.
  • Jeśli napotkamy liczbę większą, to musimy przesunąć ją o jeden w prawo.
  • Czynność tą powtarzamy do momentu napotkania liczby niemniejszej lub gdy skończą nam się liczby (nie będzie spełniony warunek {tex}j>=0{/tex}).
  • W następnym kroku wstawiamy naszą liczbę w odpowiednie miejsce i otrzymujemy podzbiór uporządkowany.
  • Powyższe czynności powtarzamy dla reszty wyrazów.

Dla przykładowego ciągu wygląda to następująco:

  • 2 5 3 0 7 1 - liczba {tex}5{/tex} pozostaje na swoim miejscu (dwa pierwsze elementy są posortowane)
  • 2 3 5 0 7 1 - liczba  {tex}3{/tex} zostaje wstawiona między liczby  {tex}2{/tex} i  {tex}5{/tex} (trzy pierwsze elementy są posortowane)
  • 0 2 3 5 7 1 - liczba  {tex}0{/tex} zostaje wstawiona na początek (cztery pierwsze elementy są posortowane)
  • 2 3 5 7 1 - liczba  {tex}7{/tex} pozostaje na swoim miejscu (pięć pierwszych elementów jest posortowanych)
  • 0 1 2 3 5 7 - liczba  {tex}1{/tex} zostaje wstawiona między liczby {tex}0{/tex} i {tex}2{/tex}. (otrzymujemy zbiór uporządkowany)

 

Sortowanie przez wstawianie można zaliczyć do atrakcyjniejszych algorytmów. Chociaż jego złożoność jest rzędu {tex}O(n^2){/tex}, a więc nie należy do najszybszych, to algorytm ma swoje zalety:

  • jest stabilny
  • bardzo dobrze zachowuje się w przypadku zbioru posortowanego lub częściowo posortowanego
  • prosty w implementacji
  • dobrze radzi sobie z niedużymi zbiorami

Algorytm najwięcej porównań elementów musi wykonać w przypadku pesymistycznej wersji zbioru danych (elementy posortowane są malejąco):

{tex}0+1+2+3+...+n-1=\frac{n\cdot (n-1)}{2}{/tex}.

Rozwiązanie w C++:

#include<iostream>
using namespace std;
 
void sortowanie_przez_wstawianie(int n, int *tab)
{
     int pom, j;
     for(int i=1; i<n; i++)
     {
             //wstawienie elementu w odpowiednie miejsce
             pom = tab[i]; //ten element będzie wstawiony w odpowiednie miejsce
             j = i-1;
 
             //przesuwanie elementów większych od pom
             while(j>=0 && tab[j]>pom) 
             {
                        tab[j+1] = tab[j]; //przesuwanie elementów
                        --j;
             }
             tab[j+1] = pom; //wstawienie pom w odpowiednie miejsce
     }     
}
 
int main()
{
    int n, *tab;
    cout<<"Podaj wielkość zbioru: ";
    cin>>n;
 
    tab = new int [n];
 
    for(int i=0; i<n; i++)
    {
            cout<<"Podaj "<<i+1<<" element: ";
            cin>>tab[i];
    }
 
    cout<<"Elementy przed sortowaniem:\n";
    for(int i=0; i<n; i++)
            cout<<tab[i]<<" ";
 
    sortowanie_przez_wstawianie(n, tab);
 
    cout<<"\nElementy posortowaniem:\n";
    for(int i=0; i<n; i++)
            cout<<tab[i]<<" ";
 
    cin.ignore();
    cin.get();
    return 0;    
}