Insertion sort

Сортирање методом уметања је једноставан алгоритам за сортирање, који гради завршни сортирани низ једну по једну ставку. Има јако једноставну примену и веома је ефикасан на малим скуповима података.
Када људи у свакодневном животу сортирају нешто (шпил карата за игру), већина користи метод сличан сортирању уметањем.
Како ради овај алгоритам?
Елементи низа се међусобно упоређују и мањи члан се увек ставља испред већег. На пример, ако је дат низ

  8   3   1   6   9 

који треба да се сортира у растућем поретку методом уметања. Почиње се са другим елементом (број 3), који се упоређује са првим елементом (број 8), и како је мањи од њега они замењују места.

  3   8   1   6   9 

Сада се изабере трећи елемент (број 1), и прво се упоређује са другим елементом (број 8) и пошто је мањи од њега они замењују места. Затим се понавља поређење са првим елементом, и како је мањи и од првог елемента, они такође замењују места.

  1   3   8   6   9

На идентичан начин, у следећем кораку се бира четврти елемент (број 6) и упоређује се са елементима лево од њега. Како је мањи од броја 8, тада они замењују места. Тада се пореди са следећим елементом, бројем 3, и како није мањи од њега неће се вршити замена.

  1   3   6   8   9

Остао је последњи елемент, број 9, и он се пореди са претходним елементом, бројем 8, и како није мањи од њега они не замењују места. Број 9 остаје на својој позицији. Тако смо добили сортиран низ.

  1   3   6   8   9




Слика 3. Insertion sort алгоритам


Пример 1. Програм који сортира у растућем поретку низ који корисник уноси преко конзоле методом insertion sort.

using System;
using System.Collections.Generic;
using System.Text;

namespace insertion_sort
{
    class Program
    {

        static void Main(string[] args)
        {
            int i, n;
            Console.Write("Unesite broj elemenata niza: ");
            n = Convert.ToInt32(Console.ReadLine());
            
            int[] a = new int[n];
            // Unos clanova niza
            for (i = 0; i < n; i++)
            {
                Console.Write("\n Unesite [" + (i + 1).ToString() + "] element: ");
                a[i] = Convert.ToInt32(Console.ReadLine());
            }
            Console.Write("\n");
            // Ispis unetog niza
            Console.Write("Uneli ste niz brojeva: ");
            for (int j = 0; j < n; j++)
                Console.Write(a[j] + " ");

            Console.WriteLine("\n \n Da li zelite da vidite sortiranje niza korak po korak? Unesite DA/NE");

            string odgovor = Console.ReadLine();

            if (odgovor == "DA")
            {   
	    	// Sortiranje niza metodom inserion sort
                Console.Write("\n");
                int k, pom, t;
                for (k = 0; k < n; k++)
                {
                    /* t postavimo na tekuci indeks i zatim pod uslovom da je t>0 uporedjujemo element
                    sa prethodno poredjanim elementima */
                    t = k;
                    while (t > 0 && a[t] < a[t - 1])
		    {
                    	// Zamenjujemo vrednosti elemenata na prethodnoj poziciji sa manjim na poziciji t
                        pom = a[t];
                        a[t] = a[t - 1];
                        a[t - 1] = pom;
                        /* Posto smo izvrsili zamenu elemenata t se smanjuje, pomera se na poziciju ulevo
                        i tako se while petljom  uporedjuju svaka dva prethodna elementa u podnizu */
                        t--;
                    }
                    /* Kada uslovi while petlje vise nisu zadovoljeni, izvrsava se spoljasnja for petlja 
                    i t dobija novu vrednost */

                    // Ispis trenutnog stanja niza
                    Console.Write("\n Niz nakon " + k.ToString() +". prolaska: ");
                    for (int j = 0; j < n; j++)
                    { 
                        Console.Write(a[j] + " ");
                    }
                }
                Console.WriteLine("\n");
                Console.Write("Niz nakon sortiranja: ");
                for (int j = 0; j < n; j++)
                    Console.Write(a[j] + " ");
                Console.Write("\n");
            }

            else if (odgovor == "NE")
            {                 
                int k, pom, t;
                for (k = 0; k < n; k++)
                {
                    /* t postavimo na tekuci indeks i zatim pod uslovom da je t>0 uporedjujemo element
                    sa prethodno poredjanim elementima */
                    t = k;
                    while (t > 0 && a[t] < a[t - 1])
                    {
                        // Zamenjujemo vrednosti elemenata na prethodnoj poziciji sa manjim na poziciji t
                        pom = a[t];
                        a[t] = a[t - 1];
                        a[t - 1] = pom;
                        /* Posto smo izvrsili zamenu elemenata t se smanjuje, pomera se na poziciju ulevo
                        i tako se while petljom  uporedjuju svaka dva prethodna elementa u podnizu */
                        t--;
                    }
                    /* Kada uslovi while petlje vise nisu zadovoljeni, izvrsava se spoljasnja for petlja 
                    i t dobija novu vrednost*/
                }
                // Ispis trenutnog stanja niza
                Console.Write("\n Niz nakon sortiranja: ");
                for (int j = 0; j < n; j++)
                    Console.Write(a[j] + " ");
                Console.Write("\n");
            }
            else
            {
                Console.Write("\n Greska! Morate uneti DA/NE! \n");
            }
            // Beskonacna petlja, da bi se video rezultat programa na kraju
            for (; ; );

     
        }    

    }

}




Напомена: За сортирање у опадајућем поретку у услову while петље
a[t] < a[t - 1]
променити знак < у знак >.


Слика 4. Резултат претходног примера