Strona główna » Algorytmy » Sortowanie » Sortowanie Przez Wstawianie
 

Sortowanie Przez Wstawianie

https://mattomatti.com/fs02

O sortowaniu

Sortowanie przez wstawianie (ang. insertion sort) jest bardzo podobna do porządkowania talii kart. Wybieramy kartę względem której będziemy porządkową i odpowiednio dokładamy kolejno. W przypadku ogólniejszego przypadku algorytm dla każdego elementu na liście do posortowania sprawdza gdzie jest jego miejsce na liście posortowanej. Robi to poprzez porównywanie pobranego elementu z kolejnymi elementami na liście wynikowej. Element jest wstawiany kiedy spełni warunek porządkowania lub kiedy nie ma już więcej elementów w celu porównania (wtedy wstawiamy na koniec).

Weźmy przykładowo listę L:={5, 3, 4, 1, 2} i prześledźmy działanie algorytmu (pogrubione zostały elementy aktualnie wstawione):

KrokPobrany elementLista posortowana
#15{5}
#23{3, 5}
#34{3, 4, 5}
#41{1, 3, 4, 5}
#52{1, 2, 3, 4, 5}

Przejdźmy teraz do analizy złożoności. Dla każdego elementu w i-tym kroku możemy wykonać maksymalnie i porównań. Sumując wszystkie porównanie dla n elementów to otrzymujemy porównań, dlatego złożoność czasowa algorytmu jest rzędu .

W najlepszym przypadku algorytm może wykonywać w każdym kroku jedno porównanie. Wtedy algorytm może działać ze złożonością liniową .

Implementacja

Będziemy sortować listę liczb rzeczywistych wpisanych przez użytkownika. Zastosujemy metodę sortowania przez wstawianie.

  1. void sort(int* lista, int zakres_od, int zakres_do, const int n){
  2.   int dl = zakres_do - zakres_od + 1;
  3.   int* zlicz = new int [dl];
  4.   for(int i = 0; i < dl; i++)
  5.     zlicz[i] = 0;
  6.   for(int i = 0; i < n; i++)
  7.     zlicz[lista[i] - zakres_od]++;
  8.   int x = 0;
  9.   for(int i = 0; i < dl; i++)
  10.     for(int j = 0; j < zlicz[i]; j++)
  11.       lista[x++] = i + zakres_od;
  12. }

(1.) Nasza funkcja będzie zwracać nową listę liczb rzeczywistych, która będzie posortowana. Jako argumenty przyjmuje listę liczb rzeczwistych do posortowania lista oraz długość listy n. (2.) Alokujemy pamięć pod listę wynikową. (3.) Dla każdej liczby na liście: (4.) i-ty element porównujemy z każdym elementem na liście wynikowej. (5.) Jeśli nie znajdziemy już elementów do porównania, czyli i = j to (6.) dopisujemy na koniec listy wynikowej aktualnie pobrany element i (7.) przerywamy pętle for. Jednak, gdy j!=i to (9.) wykonujemy porównanie pobranego elementu z j-tym element listy wynikowej. Jeśli element spełni określone kryterium (w zależności od sortowania rosnąco lub malejąco) to (10.) wszystkie elementy od pozycji j do końca przesuwamy o jeden w prawo i na j-te miejsce wstawiamy i-ty element listy do posortowania. Na koniec (18.) zwracamy listę wynikową.

Testowanie funkcji

Po uruchomieniu programu należy wpisać liczbę n jak długa jest lista, a potem n elementów. Przykładowo dla:

  1. int main () {
  2.   int n, zakres_od, zakres_do;
  3.   cin >> n >> zakres_od >> zakres_do;
  4.   int* L = new int[n];
  5.   for(int i = 0; i < n; i++)
  6.     cin >> L[i];
  7.   sort(L, zakres_od, zakres_do, n);
  8.   for(int i = 0; i < n; i++)
  9.     cout << L[i] << " ";
  10.   delete[] L;
  11.   system("pause");
  12.   return 0;
  13. }

Przykładowo dla listy [5 3 4 1 2] otrzymamy:

  1. 1 2 3 4 5

Zadania

Zadanie 1

Dodaj do funkcji sort() argument sortType. Domyślnie argument ma mieć wartość true dla której funkcja sort() będzie porządkować elementy rosnąco. Dla sortType=false lista ma zostać posortowana malejąco.

Wprowadź od użytkownika listę liczb rzeczywistych i wypisz na ekran listę posortowaną rosnąco i malejąco. Przykładowo dla listy [5 3 4 2 1] otrzymamy:

  1. 1 2 3 4 5
  2. 5 4 3 2 1