Сортирање (уређивање) низова

Размотримо на почетку које све врсте једнодимензионалних низова постоје у односу на то у ком су односу елементи низа.

Низ се може састојати од чланова који су сви међусобно различити, али могу имати и више истих чланова.

Најчешће имамо неуређене низове облика:

  • a[0] <a [1] >a [2] >a [3] <a [4]…….. < a[n] или

  • a[0] <a [1] ≥a [2] >a [3] ≤a [4]…….. < a[n]

Код низова који су уређени разликујемо четири случаја:

  • a[0] <a [1] <a [2]…….. < a[n] растући

  • a[0] >a [1] >a [2]…….. > a[n] опадајући

  • a[0] ≤a [1] ≤a [2]…….. ≤ a[n] неопадајући

  • a[0] ≥a [1] ≥a [2]…….. ≥ a[n] нерастући

Сортирање низова представља сложенији процес од претраживања, јер је неопходно упоредити сваки елеменат са осталим елементима и поставити га у низу тако да низ на крају буде уређен.

Постоји велики број метода које се могу користити да се неуређени низ уреди.

Ми ћемо овде обратити пажњу на неколико основних.

Метода избора

Метода избора (selection sort) се заснива на томе да се пролази кроз низ од почетка до краја да би се нашао елемент који треба да дође на прво место (највећи или најмањи). Након проналаска они замене места.
Затим се на исти начин у делу низа од другог до последњег елемента проналази наредни по вредности елемент који треба да дође на друго место у уређеном низу, и тако редом све док низ на крају не буде уређен.

Напишимо циклусе који врше сортирање низа методом избора :

for (i = 0; i < n - 1; i++)                          // 1
    for (j = i + 1; j < n; j++)                      // 2
        if (a[j] > a[i])                             // 3
        {
            p = a[j];
            a[j] = a[i];
            a[i] = p;
        }

Имамо два циклуса за проласке кроз низ и један услов који врши замену вредности елемената уз помоћ променљиве p.

Иницијализујте један низ од пет целобројних елемената a[5] = {2, 4, 5, 1, 3}. На основу циклуса изнад написати програм за сортирање низа методом избора.

У нашем случају n = 5.

#include <stdio.h> 
int main(void)
{
    int j, i, p, a[5] = {2, 4, 5, 1, 3};
    for (i = 0; i < 4; i++)
        for (j = i + 1; j < 5; j++)
            if (a[j] > a[i])
            {
                p = a[j];
                a[j] = a[i];
                a[i] = p;
            }
    printf("Nakon sortiranja pocetni niz u opadajucem redosledu metodom izbora izgleda : \n");
    for (i = 0; i < 5; i++) 
        printf("a[%d] = %d\n", i, a[i]);
    return 0;
}

Излаз:

Sortirani niz u opadajucem redosledu metodom izbora izgleda ovako:
a[0] = 5
a[1] = 4
a[2] = 3
a[3] = 2
a[4] = 1

Значи, добија се низ сортиран у опадајућем поретку.

Посматрајмо корак по корак како се мењају вредности i и j

../_images/Picture7.svg

У циклусу означеним са 1 је i = 0, услов i < 4 је тачан - прелазимо у циклус 2.

У циклусу означеним са 2 је j = 1 услов ј < 5 тачан и проверава се услов означен са 3, којим ако је испуњен врши се замена елемената са индексом 0 и 1.

../_images/Picture8.svg

У циклусу означеним са 1 се ништа не мења, док је у циклусу означеним са 2, j = 2 - услов ј < 5 тачан и проверава се услов означен са 3, којим ако је испуњен врши се замена елемената са индексом 0 и 2.

../_images/Picture9.svg

У циклусу означеним са 1 се ништа не мења док је у циклусу означеним са 2, j = 3 - услов ј < 5 тачан и проверава се услов означен са 3.

../_images/Picture10.svg

У циклусу означеним са 1 се ништа не мења док је у циклусу означеним са 2, j = 4 - услов ј < 5 тачан и проверава се услов означен са 3.

../_images/Picture11.svg

У циклусу означеним са 1 се ништа не мења док је у циклусу означеним са 2, j = 5 - услов ј < 5 није тачан циклус означен са 2 се прекида и контрола се поново предаје циклусу означеним са 1.

На прво место у низу дошао је највећи елемент.

Идемо даље.

У циклусу 1 i = 1, услов i < 4 је тачан, контролу преузима циклус 2. У њему је j = 2 - услов ј < 5 тачан и проверава се услов 3, којим се врши замена елемената са индексом 1 и 2.

../_images/Picture12.svg

У циклусу 1 се ништа не мења док је у циклусу 2, j = 3 - услов ј < 5 тачан и проверава се услов 3.

../_images/Picture13.svg

У циклусу 1 се ништа не мења док је у циклусу 2, j = 4 - услов ј < 5 тачан и проверава се услов 3.

../_images/Picture14.svg

У циклусу 1 се ништа не мења док је у циклусу 2, j = 5 - услов ј < 5 није тачан, циклус 2 се прекида и контрола се поново предаје циклусу 1.

На друго место у низу дошао је следећи највећи елемент. Идемо даље.

У циклусу 1 i = 2, услов i < 4 је тачан, контролу преузима циклус 2. У њему је j = 3 - услов ј < 5 тачан и проверава се услов 3.

../_images/Picture15.svg

У циклусу 1 се ништа не мења док је у циклусу 2, j = 4 - услов ј < 5 тачан и проверава се услов 3, којим се врши замена елемената са индексом 2 и 4.

../_images/Picture16.svg

У циклусу 1 се ништа не мења док је у циклусу 2, j = 5 - услов ј < 5 није тачан циклус 2 се прекида и контрола се поново предаје циклусу 1.

На треће место у низу дошао је следећи највећи елемент.

Идемо даље.

У циклусу 1 i = 3, услов i < 4 је тачан, контролу преузима циклус 2. У њему је j = 4 - услов ј < 5 тачан и проверава се услов 3, којим се врши замена елемената са индексом 3 и 4.

../_images/Picture17.svg

Унутрашњи циклус по j се прекида пошто је достигао услов и враћамо се првом циклусу по i који такође достиже услов и оба циклуса се завршавају.

На четврто место у низу дошао је четврти највећи елемент. Пети је као најмањи дошао на крај. На крају је низ уређен у опадајућем редоследу.

Метода избора се може побољшати тако што се у унутрашњем циклусу не врши замена елемената, већ се проналази позиција највећег елемента у низу. По изласку из унутрашњег циклуса само једном заменом (уколико је уопште потребна) тај елемент неуређеног низа доводи се на одговарајућу позицију у уређеном низу.

Анализирајте следећи кôд:

    for (i = 0; i < n - 1; i++)
        for (m = i, j = i + 1; j < n; j++)
            if (a[j] > a[m])
                m = j;    
            if (m != i)
            { 
                p = a[i];
                a[i] = a[m];
                a[m] = p;
            }

Шта треба променити у коду да би се добио низ у растућем поретку?

Одговор: Треба променити услов 3 за проверу и услов а[j] > a[i] променити у а[j] < a[i].

Написати програм којим се уноси n елемената целобројног низа а, затим врши сортирање методом избора у нерастућем редоследу. Исписати сортирани низ.

Решење:

#include <stdio.h> 
int main(void)
{
    int j, i, p, a[50], n;
    printf("Koliko elemenata ima niz? ");
    scanf("%d", &n);
    printf("Unesi elemente niza:\n");
    for (i = 0; i < n; i++)
    {
        printf("a[%d] = ", i);
        scanf("%d", &a[i]);
    }
    for (i = 0; i < n - 1; i++)
        for (j = i + 1; j < n; j++)
            if (a[j] > a[i])
            {
                p = a[j];
                a[j] = a[i];
                a[i] = p;
            }
    printf("\nNakon sortiranja niz u nerastucem redosledu metodom izbora izgleda :\n");
    for (i = 0; i < n; i++)
        printf("a[%d] = %d\n", i, a[i]);
    return 0;
}

Излаз:

Koliko elemenata ima niz? 10
Unesi elemente niza:
a[0] = 5
a[1] = 7
a[2] = 11
a[3] = 25
a[4] = 2
a[5] = 3
a[6] = 8
a[7] = 36
a[8] = 1
a[9] = 2

Nakon sortiranja niz u nerastucem redosledu metodom izbora izgleda :
a[0] = 36
a[1] = 25
a[2] = 11
a[3] = 8
a[4] = 7
a[5] = 5
a[6] = 3
a[7] = 2
a[8] = 2
a[9] = 1

Написати програм којим се уноси n елемената целобројног низа а, затим врши сортирање побољшаном методом избора у неопадајућем редоследу. Исписати сортирани низ.

Решење:

#include <stdio.h> 
int main(void)
{
    int j, i, p, a[50], n, m;
    printf("Koliko elemenata ima niz? ");
    scanf("%d", &n);
    printf("Unesi elemente niza:\n");
    for (i = 0; i < n; i++)
    {
        printf("a[%d] = ", i);
        scanf("%d", &a[i]);
    }
    for (i = 0; i < n - 1; i++)
        for (m = i, j = i + 1; j < n; j++)
            if (a[j] > a[m])
                m = j;    
            if (m != i)
            { 
                p = a[i];
                a[i] = a[m];
                a[m] = p;
            }
    printf("\nNakon sortiranja niz u neopadajucem redosledu poboljsanom metodom izbora izgleda :\n");
    for (i = 0; i < n; i++)
        printf("a[%d] = %d\n", i, a[i]);
    return 0;
}

Излаз:

Koliko elemenata ima niz? 10
Unesi elemente niza:
a[0] = 5
a[1] = 7
a[2] = 11
a[3] = 25
a[4] = 2
a[5] = 3
a[6] = 8
a[7] = 36
a[8] = 1
a[9] = 2

Nakon sortiranja niz u neopadajucem redosledu poboljsanom metodom izbora izgleda :
a[0] = 1
a[1] = 2
a[2] = 2
a[3] = 3
a[4] = 5
a[5] = 7
a[6] = 8
a[7] = 11
a[8] = 25
a[9] = 36

Метода уметања

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

for (i = 1; i < n; i++)                                // 1
    for (j = i - 1; j >= 0 && a[j] > a[j+1]; j--)      // 2
    {     
        p = a[j];
        a[j] = a[ј+1];
        a[j+1] = p;
    }

Наведеним кодом упоређујемо два суседна елемента и замењујемо им места све док је a[j] > a[j+1] односно док се не врататимо до почетног индекса низа j >= 0. Ово значи да циклус може да се заврши и раније ако се утвди да је управо испитана вредност стигла на своје место у раније већ уређеном низу. Ова метода је ефикаснија од методе избора.

Иницијализујте један низ од пет целобројних елемената a[5] = {2, 4, 5, 1, 3}. Користећи наведене циклусе написати програм за сортирање низа методом уметања.

Решење:

#include <stdio.h> 
int main(void)
{
    int j, i, p, a[5] = {2, 4, 5, 1, 3};
    for (i = 1; i < 5; i++)
        for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
        {
            p = a[j];
            a[j] = a[j + 1];
            a[j + 1] = p;
        }
    printf("\nSortirani niz u rastucem redosledu metodom umetanja izgleda ovako:\n");
    for (i = 0; i < 5; i++)
        printf("a[%d] = %d\n", i, a[i]);
    return 0;
}

Излаз:

Sortirani niz u rastucem redosledu metodom umetanja izgleda ovako:
a[0] = 1
a[1] = 2
a[2] = 3
a[3] = 4
a[4] = 5

Дакле, добија се низ сортиран у растућем поретку.

Посматрајмо корак по корак како се мењају вредности i и j.

../_images/Picture7.svg

У циклусу означеним са 1, i = 1, услов i < 5 је тачан па прелазимо у циклус означен са 2. У њему је j = 0 услов j >= 0 && a[0] > a[1] није тачан и циклус означен са 2 се прекида и контрола се враћа циклусу 1. Редослед елемената остаје непромењен.

../_images/Picture7.svg

У циклусу 1 i = 2 услов i < 5 је тачан прелазимо у циклус 2. У њему је j = 1 услов j >= 0 && a[1] > a[2] није тачан и циклус 2 се прекида и контрола се враћа циклусу 1. Редослед елемената остаје непромењен.

../_images/Picture7.svg

У циклусу 1 i = 3 услов i < 5 је тачан прелазимо у циклус 2. У њему је j = 2 услов j >= 0 && a[2] > a[3] је тачан и врши се замена елемената са индексима 2 и 3.

../_images/Picture22.svg

У циклусу 1 се ништа не мења док у циклусу 2 j = 1 услов j >=0 && a[2] > a[3] је тачан и врши се замена елемената са индексима 1 и 2.

../_images/Picture23.svg

У циклусу 1 се ништа не мења док у циклусу 2 j = 0 услов j >= 0 && a[2] > a[3]је тачан и врши се замена елемената са индексима 0 и 1.

../_images/Picture24.svg

У циклусу 1 се ништа не мења док у циклусу 2 j = -1услов j >=0 && a[2] > a[3] није тачан и циклус 2 се прекида и контрола се враћа циклусу 1.

У циклусу 1 i = 4 услов i < 5 је тачан прелазимо у циклус 2. У њему је j = 3 услов j >= 0 && a[3] > a[4] је тачан и врши се замена елемената са индексима 3 и 4.

../_images/Picture25.svg

У циклусу 1 се ништа не мења док у циклусу 2 j = 2 услов j >= 0 && a[2] > a[3] је тачан и врши се замена елемената са индексима 2 и 3.

../_images/Picture26.svg

У циклусу 1 се ништа не мења док у циклусу 2 j = 1 услов j >= 0 && a[1] > a[2] није тачан циклус 2 се прекида и контрола се враћа циклусу 1. Редослед елемената остаје непромењен.

../_images/Picture27.svg

У циклусу 1 i = 5 услов i < 5 није тачан и он се прекида. Приметићемо да је низ уређен у растућем поретку.

../_images/Picture27.svg

Метода уметања се може побољшати тако што се елемент на позицији привремено сачува, и тек на крају када се утврди његова позиција ту и копира. На овај начин се смањује број операција доделе.

Анализирајте следећи кôд:

for (i = 1; i < n; i++)
    {
    p = a[i];                            
    for (j = i - 1; j >= 0 && a[j] > p ; j--)         
        a[j+1] = a[j];
        a[j+1] = p;
    }

Шта треба променити у коду да би се добио низ сортиран у опадајућем поретку?

Одговор: Треба променити услов за проверу и уместо a[j] > a[j+1]ставити a[j] < a[j+1].

Написати програм којим се уноси n елемената целобројног низа, затим врши сортирање методом уметања и на крају исписује сортирани низ.

Решење:

#include <stdio.h> 
int main(void)
{
    int j, i, p, a[50], n;
    printf("Koliko elemenata ima niz? ");
    scanf("%d", &n);
    printf("Unesi elemente niza:\n");
    for (i = 0; i < n; i++)
    {
        printf("a[%d] = ", i);
        scanf("%d", &a[i]);
    }
    for (i = 1; i < n; i++)
        for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
        {
            p = a[j];
            a[j] = a[j + 1];
            a[j + 1] = p;
        }
    printf("\nSortirani niz u rastucem redosledu dobijen metodom umetanja izgleda : \n");
    for (i = 0; i < n; i++)
        printf("a[%d] = %d\n", i, a[i]);
    return 0;
}

Излаз:

Koliko elemenata ima niz? 7
Unesi elemente niza:
a[0] = 1
a[1] = 6
a[2] = 3
a[3] = 4
a[4] = 77
a[5] = 22
a[6] = 11

Sortirani niz u rastucem redosledu dobijen metodom umetanja izgleda :
a[0] = 1
a[1] = 3
a[2] = 4
a[3] = 6
a[4] = 11
a[5] = 22
a[6] = 77

Написати програм којим се уноси n елемената целобројног низа, затим врши сортирање побољшаном методом уметања и на крају исписује сортирани низ.

Решење:

#include <stdio.h> 
int main(void)
{
    int j, i, p, a[50], n;
    printf("Koliko elemenata ima niz? ");
    scanf("%d", &n);
    printf("Unesi elemente niza:\n");
    for (i = 0; i < n; i++)
    {
        printf("a[%d] = ", i);
        scanf("%d", &a[i]);
    }
    for (i = 1; i < n; i++)
    {
        p = a[i];                            
        for (j = i - 1; j >= 0 && a[j] > p ; j--)         
            a[j+1] = a[j];
        a[j+1] = p;
    }
    printf("\nSortirani niz u rastucem redosledu dobijen poboljsanom metodom umetanja izgleda : \n");
    for (i = 0; i < n; i++)
        printf("a[%d] = %d\n", i, a[i]);
    return 0;
}

Излаз:

Koliko elemenata ima niz? 7
Unesi elemente niza:
a[0] = 1
a[1] = 6
a[2] = 3
a[3] = 4
a[4] = 77
a[5] = 22
a[6] = 11

Sortirani niz u rastucem redosledu dobijen metodom umetanja izgleda :
a[0] = 1
a[1] = 3
a[2] = 4
a[3] = 6
a[4] = 11
a[5] = 22
a[6] = 77

Метода замене суседа

Метода замене суседа (bubble sort) заснива се на идеји да се кроз низ пролази са једног на други крај низа упоређујући суседне елементе и замењујући их уколико нису у одговарајућем поретку.

Овај поступак се понавља све док не добијемо потпуно уређен низ

for(i = n-1; i >= 0; i--)                                
    for (j = 0; j < i; j++)
        if(a[j] > а[j+1])
        {
            p = a[j];
            a[j] = a[ј + 1];
            a[j + 1] = p;
        }
}

Иницијализујте један низ од пет целобројних елемената a[5] = {2, 4, 5, 1, 3}. На основу циклуса написати програм за сортирање низа методом замене суседа.

Решење:

#include <stdio.h> 
int main(void)
{
    int j, i, p, a[5] = {2, 4, 5, 1, 3};
    for (i = 4; i >= 0; i--)
        for (j = 0; j < i; j++)
            if (a[j] > a[j + 1])
            {
                p = a[j];
                a[j] = a[j + 1];
                a[j + 1] = p;
            }
    printf("Sortirani niz u opadajucem redosledu dobijen metodom zamene suseda izgleda ovako:\n");
    for (i = 0; i < 5; i++)
        printf("a[%d] = %d\n", i, a[i]);
    return 0;

Излаз:

Sortirani niz u opadajucem redosledu dobijen metodom zamene suseda izgleda ovako:
a[0] = 1
a[1] = 2
a[2] = 3
a[3] = 4
a[4] = 5

Посматрајмо корак по корак како се упоређују вредности. У циклусу 1 i = 5 с у циклусу 2 j = 0.

Корак 1: Поредимо да ли је a[0] > a[1]. Видимо да није и низ остаје непромењен.

../_images/Picture7.svg

Корак 2: Поредимо да ли је a[1] > a[2]. Видимо да није и низ остаје непромењен.

../_images/Picture7.svg

Корак 3: Поредимо да ли је a[2] > a[3]. Видимо да јесте и та два елемента замењују места

../_images/Picture32.svg

Корак 4: Поредимо да ли је a[3] > a[4]. Видимо да јесте и та два елемента замењују места

../_images/Picture33.svg

Значи, на последње место смо довели највећи елемент низа.

Крећемо поново од почетка.

Сада је у циклусу 1 i = 4 а у циклусу 2 j = 0.

Корак 1: Поредимо да ли је a[0] > a[1]. Видимо да није и низ остаје непромењен.

../_images/Picture34.svg

Корак 2: Поредимо да ли је a[1] > a[2]. Видимо да јесте и та два елемента замењују места.

../_images/Picture35.svg

Корак 3: Поредимо да ли је a[2] > a[3]. Видимо да јесте и та два елемента замењују места.

../_images/Picture36.svg

На друго место од позади довели смо следећи највећи елемент низа.

Крећемо поново од почетка.

Сада је у цикусу 1 i = 3, а у циклусу 2 j = 0.

Корак 1: Поредимо да ли је a[0] > a[1]. Видимо да јесте и та два елемента замењују места.

../_images/Picture37.svg

Корак 2: Поредимо да ли је a[1] > a[2]. Видимо да није и низ остаје непромењен.

../_images/Picture27.svg

На треће место од позади довели смо следећи највећи елемент низа.

Крећемо поново од почетка.

Сада је у цикусу 1 i = 4, а у циклусу 2 j = 0.

Корак 1: Поредимо да ли је a[0] > a[1]. Видимо да није и низ остаје непромењен. Ово значи да смо дошли до краја. Оба циклуса су се прекинула и сви су елементи на свом месту.

../_images/Picture27.svg

Шта треба променити у коду да би низ био уређен у опадајућем редоследу

Одговор: Треба променити и уместо услова a[j] > a[j+1] ставити a[j] < a[j+1].

Написати програм којим се уноси n елемената целобројног низа, затим врши сортирање методом замене суседа у растућем поретку. Исписати сортирани низ.

Решење:

#include <stdio.h> 
int main(void)
{
    int j, i, p, a[50], n;
    printf("Koliko elemenata ima niz? ");
    scanf("%d", &n);
    printf("Unesi elemente niza:\n");
    for (i = 0; i < n; i++)
    {
        printf("a[%d] = ", i);
        scanf("%d", &a[i]);
    }
    for (i = n - 1; i >= 0; i--)
        for (j = 0; j < i; j++)
            if (a[j] > a[j + 1])
            {
                p = a[j];
                a[j] = a[j + 1];
                a[j + 1] = p;
            }
    printf("\nSortirani niz u rastucem redosledu dobijen metodom zamene suseda izgleda ovako: \n");
    for (i = 0; i < n; i++)
        printf("a[%d]=%d\n", i, a[i]);
    return 0;
}

Излаз:

Koliko elemenata ima niz? 6

Unesi elemente niza:
a[0] = 12
a[1] = -5
a[2] = 0
a[3] = 4
a[4] = 11
a[5] = 2

Sortirani niz u rastucem redosledu dobijen metodom zamene suseda izgleda ovako:
a[0] = -5
a[1] = 0
a[2] = 2
a[3] = 4
a[4] = 11
a[5] = 12

Написати програм којим се уноси n елемената целобројног низа, затим врши сортирање методом замене суседа у опадајућем поретку. Исписати сортирани низ.

Решење:

#include <stdio.h> 
int main(void)
{
    int j, i, p, a[50], n;
    printf("\nKoliko elemenata ima niz: ");
    scanf("%d", &n);
    printf("\nUnesi elemente niza: \n");
    for (i = 0; i < n; i++)
    {
        printf("a[%d] = ", i);
        scanf("%d", &a[i]);
    }
    for (i = n - 1; i >= 0; i--)
        for (j = 0; j < i; j++)
            if (a[j] < a[j + 1])
            {
                p = a[j];
                a[j] = a[j + 1];
                a[j + 1] = p;
            }
    printf("Sortirani niz u rastucem redosledu metodom zamene suseda izgleda ovako: \n");
    for (i = 0; i < n; i++)
    printf("a[%d] = %d\n", i, a[i]);
    return 0;
}

Излаз:

Koliko elemenata ima niz? 6

Unesi elemente niza:
a[0] = 12
a[1] = -6
a[2] = 0
a[3] = 4
a[4] = 11
a[5] = 2

Sortirani niz u opadajucem redosledu metodom zamene suseda izgleda ovako:
a[0] = 12
a[1] = 11
a[2] = 4
a[3] = 2
a[4] = 0
a[5] = -6

Метода може да се побољша и скрати број поређења. Један од таквих програма следи у наставку. Пробај да разумеш зато је уведена промењива dalje.

#include <stdio.h> 
int main(void)
{
    int j, i, p, a[5] = {2, 4, 5, 1, 3}, dalje;
    for (dalje = 1, i = 0; i < 4 && dalje; i++)
        for (dalje = 0, j = 4; j > i; j--)
            if (a[j - 1] > a[j])
            {
                p = a[j - 1];
                a[j - 1] = a[j];
                a[j] = p;
                dalje = 1;
           }
    printf("Sortirani niz u opadajucem redosledu metodom zamene suseda izgleda ovako: \n");
    for (i = 0; i < 5; i++)
        printf("a[%d] = %d\n", i, a[i]);
    return 0;
}

Излаз:

Sortirani niz u opadajucem redosledu metodom zamene suseda izgleda ovako:
a[0] = 1
a[1] = 2
a[2] = 3
a[3] = 4
a[4] = 5