Сортирање низа

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




Растући поредак


a[0] < a[1] < a[2] < a[3] < a[4] < ......... < a[n-1]

Опадајући поредак

a[0] > a[1] > a[2] > a[3] > a[4] > ......... > a[n-1]




Размотримо сада једну помоћну фор петљу која ће нам помоћи да боље разумемо поступак сортирања низова! i-ти елемент у низу а заменићемо сваким елементом десно од њега, који пронађемо да је мањи. Променљива ј ће у итерацији ,која следи, узимати све вредности индекса почев од i+1 па до n-1, што значи да се у једном пролазу кроз подниз почев од (i+1)-ог елемента тражи најмањи. 


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

namespace ConsoleApplication1
{
    class  Program
    {
        static void Main(string[] args)
        {	  
            //Navodimo direktno elemente niza a
            int a[] = {2,5,6,8,4,9,3,7,11,10};
            int i,j,pom;
            //Uzimamo duzinu niza
            int n = a.Length;
            //Na primer postavicemo promenljivu i da bude na trecoj poziciji u nizu
            i = 2;
  
            //Promenljivu j postavljamo od sledece pozicije u nizu
            for(j = i+1;j < n;j++)
			
                //Trazimo elemente a[j] koji su manji od fiksiranog elementa na trecoj poziciji
                if(a[j] < a[i])
                {
                    //Svaki pronadjeni manji element zamenjujemo elementom na i-toj(trecoj) poziciji
                    pom = a[i];
                    a[i] = a[j];
                    a[j] = pom;
                }
            }
	 }
     }
}

Понављањем претходног поступка за i=0,1,2,.....n-1 елементи низа ће се поређати у растући поредак.
На сличан начин можемо добити и низ сортиран у опадајућем редоследу, с тим што тада вршимо размену сваког i-тог елемента са сваким следећим елементом који је већи.

Постоје различите врсте алгоритма за сортирање, који се битно разликују по принципу рада и брзини извршавања. Ми ћемо се на овом курсу упознати са најједноставнијим selection sort алгоритмом.
Баш као и у помоћном примеру, низ се сортира растуће тако што се најпре тражи најмањи елемент, који се доводи на прво место. Затим се налази најмањи од преосталих n-1 елемената и он се доводи на друго место, па најмањи у поднизу од n-2 елемента доводимо на треће место и тако закључно са налажењем мањег од последња два елемента и његовим довођењем на претпоследње место. На последњем месту ће остати елемент који није мањи ни од једног у низу (највећи елемент).

У наставку је приказан алгоритам сортирања у растућем поретку, у оквиру функције selection_sort која нема повратну вредност. Јасно је да та функција врши само пермутације и упоређивања елемената низа, па самим тим не враћа конкретан резултат добијен неким операцијама. 
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class  Program
    {
        static void selection_sort (int []a ,int n)
        {
            int i,j,pom;
            //Cuva indeks tekuceg minimalnog elementa
            int min;
   
            /*Spoljasnja for petlja koja se izvrsava prolaskom kroz niz po promenljivoj i, 
			tek kada se zavrsi unutrasnja for petlja*/
            for(i = 0;i < n-1;i++)
            { 
                //Promenljivoj min dodelimo indeks elementa na i-toj poziciji
                min = i;
                /*Unutrasnja for petlja krece od narednog elementa, (i+1)-og. Kako se j povecava
                sve se vise smanjuje podniz elemenata koje uporedjujemo sa i-tim elementom*/ 
                for(j = i+1; j < n ;j++)
                    //Uporedjujemo tekuci element a[j] sa fiksiranim elementom na poziciji min
                    if(a[j] < a[min])
                        /*Kada pronadjemo novi manji element a[j], njegov indeks j dodeljujemo 
                        promenljivoj min koja uvek cuva indeks tekuceg najmanjeg elementa*/
                        min = j;
  
                /*Vrsimo zamenu mesta novog minimalnog elementa na poziciji min i elementa na 
                prethodnoj min poziciji, ako min vise nije i*/
                if(min != i)
                {
                    pom = a[i];
		    a[i] = a[min];
                    a[min] = pom;
                }
            }
        }

        static void Main(string []args)
        {
	    //Rezervisemo proizvoljno 50 elemenata u memoriji
            int []a = new int[50];
            int i,n;

            Console.WriteLine("Unosimo broj elemenata niza:");
            n = int.Parse(Console.ReadLine());

            Console.WriteLine("Unosimo elemente niza:");

            for(i = 0;i < n;i++)

            a[i] = int.Parse(Console.ReadLine());

            //Pozivamo funkciju selection_sort koja ce nam sortirati uneti niz
            selection_sort(a , n);

            //Ispisujemo elemente u novom rastucem poretku

            for(i = 0;i < n;i++)
                Console.WriteLine(a[i]+ ",");
        }
    }
}


Овде се налази и видео фајл који ближе објашњава претходни алгоритам. select_sort

Слично се врши и сортирање низа у опадајући поредак,са једном битном разликом. Којом?

Када низ сортирамо у опадајући поредак тражи се највећи елемент у сваком поднизу до последњег елемента, тако да ми уствари вршимо избор узастопних максимума, док смо при уређењу чланова низа растуће бирали узастопне минимуме.
Покушајте сада сами да направите selection_sort алгоритам који сортира низ опадајуће.
Само пратите претходни поступак. Smiley face
Увек можете да преконтролишете свој код, ако ваш програм не ради након покретања и не можете да нађете грешку.


Постоји још један алгоритам за сортирање низова, insertion sort, који се користи код низова које треба "мало" сортирати и низова малих димензија. Insertion sort алгоритам за сортирање у растућем поретку ради тако што пролази редом кроз елементe у низу и за сваки проверава да ли је елемент пре њега (лево од њега) већи, и ако је већи врши се замена елемената и тако све док постоји елемент на левој страни који је већи. 

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

namespace insert_sort
{
    class  Program
    {
        static void insertion_sort(int[] a, int n)
        {
            int i, pom, t;
            for (i = 0; i < n; i++)
            {   
	        /*t postavimo na tekuci indeks i zatim pod uslovom da je t>0 uporedjujemo element
			sa prethodno poredjanim elementima*/
                t = i;
                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*/
            }
        }
		
	static void Main(string[] args)
        {
            int []a = new int[50];
            int i, n;
 

            Console.WriteLine("Unosimo broj elemenata niza:");
            n = int.Parse(Console.ReadLine());

            Console.WriteLine("Unosimo elemente niza:");

            for(i = 0;i < n;i++) 
            {
                a[i] = int.Parse(Console.ReadLine());
            }
            insertion_sort(a, n);

            //Ispisujemo elemente u rastucem poretku

            for(i = 0;i < n;i++)
            Console.Write(a[i]+ " ");
        }

    }
}


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

Пример 1. Написати програм који сортира унети низ произвољне дужине и рачуна медијан,тј. средњи члан тог низа. Ако је број чланова низа непаран, медијан је средњи члан, а ако је број чланова паран, медијан је средња вредност елемената низа са индексима n/2-1 и n/2, где је n број чланова низа.


Решење: 

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

namespace medijan
{
    class  Program
    {
        //Funkcija koja sortira elemente niza u rastucem poretku
        static void selection_sort(int[] a, int n)              
        {
            int i, j, pom;
            int min;
            for (i = 0; i < n - 1; i++)
            {
                min = i;

                for (j = i + 1; j < n; j++)
                    if (a[j] < a[min])
                        min = j;

                if (min != i)
                {
                    pom = a[i];
                    a[i] = a[min];
                    a[min] = pom;
                }
            }                       
        }
        
        static void Main(string[] args)
        {
            int[] a=new int[100];
            int i, j, dim;
			
            //Sa ulaza unosimo broj clanova niza a[] i tu vrednost dodeljujemo promenljivoj dim
            Console.WriteLine("Unesite broj clanova niza");
            dim = int.Parse(Console.ReadLine());

            //Sa ulaza unosimo clanove niza a[]
            Console.WriteLine("Unesite clanove niza");
            for (i = 0; i < dim; i++) 
            {
                a[i] = int.Parse(Console.ReadLine());
            }

            //Pozivamo funkciju selection_sort 
            selection_sort(a,dim); 
            for (i = 0; i < dim; i++)
            {
                //Ispisujemo sortirani niz
                Console.WriteLine(" " +a[i]);              
            }
			
            //Postavimo medijan na pocetnu vrednost
            int med = 0;
			
            //Racunamo medijan niza a prema gore navedenom pravilu 
			
            //Ako je broj clanova niza neparan, tj. dim nije deljiv sa 2
            if (dim % 2 != 0)
            {
                //Medijan je srednji clan, ciji je indeks (dim-1)/2
                med = a[(dim - 1) / 2];
            }
            //Ako je broj clanova niza paran, tj. ako je dim deljivo sa 2
            else if (dim % 2 == 0)
            {
                //Medijan racunamo kao aritmeticku sredinu dva elementa na pomenutim pozicijama
                med = (a[(dim / 2)-1]+a[(dim/2)])/2;
            }
            //Ispisujemo rezultat
            Console.WriteLine("Medijan je:", med);
        
	}
    }
}