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

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

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

Сортирање низа значи поређати његове чланове у неком поретку. Бројеви се сортирају у односу на релацију < и >, односно <= и >=, а знаци и речи у односу на енглески алфабет, захваљујући чињеници да су већ представљени помоћу ASCII кода у облику бројева.

Растући редослед:

a0<a1<a2<…<an-2<an-1

Опадаjући редослед:

a0>a1>a2>…>an-2>an-1

Неопадаjући редослед (међу елементима уређеним у растућем редоследу има и jеднаких):

a0<=a1<=a2<=…<=an-2<=an-1

Нерастући редослед (међу елементима уређеним у опадаjућем редоследу има и jеднаких):

a0>=a1>=a2>=…>=an-2>=an-1

Да бисмо сортирали низ, потребна нам је помоћна функција razmeni, која мења места две променљиве:

void razmeni(int *x,int *y)
{
	int p; 
	p=*x;
	*x=*y;
	*y=p;
}

Размотримо како бисмо могли обавити сортирање неког низа од n елемената у рецимо растући поредак. Решење које се прво намеће је да прво пронађемо најмањи елемент па да га доведемо на прво место у низу (при томе, елемент који се већ налазио на првом месту треба пребацити на место на којем се претходно налазио најмањи елемент, односно треба извршити размену првог и најмањег елемента – позивамо функцију razmeni). У другом кораку, проналазимо најмањи елемент почев од другог елемента низа надаље, а затим га доведемо на друго место у низу. Уопштено, у неком k-том кораку проналазимо најмањи елемент почев од k-тог елемента низа надаље, а затим га доведемо на k-то место у низу (на његово место доводимо елемент који се до тада налазио на k-том месту). Очигледно, након n-1 корака, низ је сортиран. Ово је најједноставнији алгоритам и назива се сортирање методом избора. За реализацију овог начина сортирања неопходно је користити два for циклуса:

  • спољашњи има границе од 0 до n-1

  • унутрашњи има границе од i+1 до n како би се обезбедило да након првог проласка кроз спољашњи циклус (и све проласке кроз унутрашњи циклус) на прво место дође најмањи елеменат. Након тога, у следећем проласку кроз спољашњи циклус, одређујемо други најмањи елеменат и смештамо га на друго место…

Постоје две варијанте овог начина сортирања:

1. у првој варијанти се приликом проласка кроз унутрашњи циклус константно врши размена СВИХ елемената који су мањи од елемента на првом месту са елементом на првом месту, тако да може да се деси да се изврши већи број размена:

for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if (a[j]<a[i]) razmeni (&a[i],&a[j]);

2. у другој варијанти одређујемо индекс најмањег елемента у преосталом делу низа; ако је индекс најмањег елемента различит од i то значи да у преосталом делу низа постоји мањи елеменат и потребно је извршити замену:

for(i=0;i<n-1;i++)
	{
		m=i;
		for(j=i+1;j<n;j++) if(a[j]<a[m]) m=j;
		if (m!=i) razmeni(&a[i],&a[m]);
		for(k=0;k<n;k++)printf("%.2f\t ",a[k]);printf("\n"); /*predvidjeno je da nakon svakog prolaska kroz ciklus odstampamo trenutni poredak elemenata niza, kako bi se videlo kako se postepeno sortira niz */
	}

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

Bubble sort (Сортирање заменом суседних елемената)

Код методе замене суседа кроз низ се пролази са jедног на други краj, упоређуjући по два суседна елемента и замењуjући их међусобно кад нису у одговараjућем поретку. На таj начин ће се елементи низа померити ка своjим краjњим положаjима. Оваj поступак се понавља, све док у jедном пролазу кроз низ не треба више замењивати ни jедан пар суседа. И овај алгоритам има две варијанте:

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

dalje=1;
for(i=0;i<n-1&&dalje;i++)
{
	dalje=0;
	for(j=n-1;j>i;j--)if(a[j-1]>a[j]){ razmeni(&a[j-1],&a[j]);	dalje=1;}
	for(k=0;k<n;k++)printf("%.2f\t ",a[k]);printf("\n");
}

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

dalje=1;
while(dalje)
{
	i++;
	dalje=0;
	for(j=0;j<n-1-i;j++) if(a[j]>a[j+1]){	razmeni(&a[j],&a[j+1]);	dalje=1;}
	for(k=0;k<n;k++)printf("%.2f\t ",a[k]);printf("\n");
}

Сортирање са уметањем (Insertion sort)

Метода уметања заснива се на идеjи да се елементи низа умећу jедан по jедан тако да оформљени део низа сваког момента буде уређен. Упоређуjу се редом два суседна елемента (од тачке до коjе смо уредили низ) и та два елемента међусобно замењуjемо све док jе аj+1j. Унутрашњи циклус не траjе увек до краjњих граница, може се завршити и пре времена, ако се утврди да jе управо испитана вредност стигла на своjе место у већ уређеном делу низа.

1. мењамо места суседним елементима, док се не уреде

for(i=1;i<n;i++)
for(j=i-1;j>=0&&a[j]>a[j+1];j--)
razmeni (&a[j],&a[j+1]);

2. померамо елеменат за по једно место улево, док не дође до места на коме треба да се налази

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

Метода поделе (Quick sort)

Основна идеја ове методе је да низ поделимо произвољно одабраним елементом на два дела тако да су у левом елементи мањи од њега, у десном већи од њега. Исто важи и за њихове индексе. Добијени делови се даље рекурзивно деле све док не добијемо сортиран низ.

Крећемо од почетка према крају све док су елементи мањи од последњег (a[i]). – I do while циклус

Крећемо од краја према почетку, све док су елементи већи од последњег (a[j]). – II do while циклус

Мењамо a[i] и a[j].

Овај метод је рекурзиван, и то му је највећи недостатак.

if(n>1)
{
i=-1;j=n-1;
while(1)
{
do i++; while (a[i]<a[n-1]);
do j--;while (j>=0&&a[j]>a[n-1]);
if(i>=j) break;
else razmeni(&a[i],&a[j]);
}
razmeni(&a[i],&a[n-1]);
podela(a,i); /* pozivanje funkcije za sortiranje i primena na levi deo niza */
podela(a+i+1,n-i-1); /* pozivanje funkcije za sortiranje i primena na desni deo niza */
}

1. Дефинисати функције за сортирање реалних низова по неопадајућем редоследу: метод селекције и метод селекције – побољшана верзија. Предвидети приказивање делимично сортираног низа после сваког проласка кроз циклус.

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

Решење:

#include<stdio.h>

void razmeni(float *x,float *y)
{
	float p;
	p=*x;*x=*y;*y=p;
}

void izbor1(float a[],int n)
{
	int i,j,k;
	float p;
	for(i=0;i<n-1;i++)
	{
		for(j=i+1;j<n;j++) if(a[j]<a[i]) razmeni(&a[i],&a[j]);
		for(k=0;k<n;printf("%.2f ",a[k++]));printf("\n");
	}

}

void izbor2(float a[],int n)
{
	int i,j,m,k;
	float p;
	for(i=0;i<n-1;i++)
	{
		m=i;
		for(j=i+1;j<n;j++) if(a[j]<a[m]) m=j;
		if (m!=i) razmeni(&a[i],&a[m]);
		for(k=0;k<n;printf("%.2f ",a[k++]));printf("\n");

	}
}

main()
{
	float a[20];
	int n, i, m;
	while(1)
	{
		printf("unesi broj elemenata niza: ");scanf("%d",&n);
		if (n<=0)break;
		printf("\nunesi elemente niza:\n");
		for(i=0;i<n;i++){printf("%d.",i+1);scanf("%f",&a[i]);}
		printf("\nUnesite nacin sortiranja\n");
		printf("\n1 - metoda selekcije");
		printf("\n2 - metoda selekcije - poboljsana\n");
		scanf("%d",&m);
		printf("\n");
		switch(m)
		{
			case 1:izbor1(a,n);break;
			case 2:izbor2(a,n);break;
			default:printf("greska\n");
		}
		printf("sortiran niz:\n");
		for(i=0;i<n;printf("%.2f ",a[i++]));printf("\n");
	}
}
Advertisements

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се / Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се / Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се / Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се / Промени )

Повезивање са %s