23/24 Sekcija iz Programiranja

Za numerički nz se kaže da je sortiran ili uređen kao:

1) rastući, ako je  a[0] < a[1] < a[2] < ... < a[n-1]

2) neopadajući, ako je  a[0] <= a[1] <= a[2] <= ... <= a[n-1]

3) opadajući, ako je  a[0] > a[1] > a[2] > ... . a[n-1]

4) nerastući, ako je  a[0] >= a[1] >= a[2] >= ... >= a[n-1]

Jedan od problema koji se vrlo često javlja u obradama podataka je svakako sortiranje elemenata niza.

Sortiranje je postupak uređivanja datog niza vrednosti (elemenata koji se mogu porediti) tako da čine uređen niz (neopadajući ili nerastući).

---

Najčešće su vrednosti koje se uređuju – celi ili realni brojevi, mada mogu da budu i neki drugi objekti nad kojima je definisano neko uređenje. Celi brojevi imaju određene prednosti, pa su zbog njih razvijeni i neki efikasniji algoritmi sortiranja. Najpopularniji algoritmi za sortiranje elemenata su:

• sortiranje slekcijom,
• quck sort – brzo sortiranje,
• sortiranje deljenjem niza,
• sortiranje izborom uzastopnih minimuma

SORTIRANJE SELEKCIJOM

Ovo je jedna od najjednostavnijih metoda, na primer, sortiranje niza u rastućem redosledu. Postupak je sledeći:

1. najmanji element niza postavlja se na prvu poziciju, zamenjujući mesto sa elementom koji se tamo nalazio;
2. drugi najmanji element se premešta na drugu poziciju, zamenjujući trenutnu vrednost do tada drugog elementa niza;
3. postupak se ponavlja sve dok se i na poslednju poziciju ne postavi odgovarajuća vrednost.

Sortiranje niza u opadajućem redosledu je analogno.

**************************************

Implementacija Selection sort algoritma u C-u

1. #include <stdio.h>
2.  
3. int main()
4. {
5.   int array[100], n, c, d, position, swap;
6.  
7.   printf("Enter number of elements\n");
8.   scanf("%d", &n);
9.  
10.   printf("Enter %d integers\n", n);
11.  
12.   for (c = 0; c < n; c++)
13.     scanf("%d", &array[c]);
14.  
15.   for (c = 0; c < (n - 1); c++)
16.   {
17.     position = c;
18.    
19.     for (d = c + 1; d < n; d++)
20.     {
21.       if (array[position] > array[d])
22.         position = d;
23.     }
24.     if (position != c)
25.     {
26.       swap = array[c];
27.       array[c] = array[position];
28.       array[position] = swap;
29.     }
30.   }
31.  
32.   printf("Sorted list in ascending order:\n");
33.  
34.   for (c = 0; c < n; c++)
35.     printf("%d\n", array[c]);
36.  
37.   return 0;
38. }

    **************************************
    

    
    

    Postoje različite vrste algoritma za sortiranje, koji se bitno razlikuju po principu rada i brzini izvršavanja. Mi ćemo se ovde upoznati sa najjednostavnijim selection sort algoritmom.
    Niz se sortira rastuće tako što se najpre traži najmanji element, koji se dovodi na prvo mesto. Zatim se nalazi najmanji od preostalih n-1 elemenata i on se dovodi na drugo mesto, pa najmanji u podnizu od n-2 elementa dovodimo na treće mesto i tako zaključno sa nalaženjem manjeg od poslednja dva elementa i njegovim dovođenjem na pretposlednje mesto. Na poslednjem mestu će ostati element koji nije manji ni od jednog u nizu (najveći element).
    
    

    Slično se vrši i sortiranje niza u opadajući poredak,sa jednom bitnom razlikom. Kojom?
    
    Kada niz sortiramo u opadajući poredak traži se najveći element u svakom podnizu do poslednjeg elementa, tako da mi ustvari vršimo izbor uzastopnih maksimuma, dok smo pri uređenju članova niza rastuće birali uzastopne minimume.

Ako neko želi da nauči nešto više:

1. Ovde ćemo se osvrnuti na još jedan algoritam za sortiranje nizova, insertion sort. Ovaj algoritam se koristi kod nizova koje treba "malo" sortirati i nizova malih dimenzija.

   Insertion sort algoritam za sortiranje u rastućem poretku radi tako što prolazi redom kroz svaki element u nizu i proverava da li je element pre njega (levo od njega) veći, i ako je veći vrši se zamena elemenata i tako sve dok postoji element na levoj strani koji je veći od njega.

   http://www.edusoft.math.rs/csharp/Verzija2005/niz_slike/insertion_sort.jpg