Методи за сортиране

[crio]

Методи за сортиране

Съдържание:

1. Пряка селекция
   
2. Пряко вмъкване
   
3. Методът на "Мехурчето"
   
4. Сортиране чрез клатене
   

1. Пряка селекция

1. Намираме най-малката стойност в масива
   
2. Разменяме позицията и с първата несортирана стойност
   
3. Това се повтаря върху масив без сортираните стойности
   

http://img523.imageshack.us/img523/7269/sorting1ai8.png

 

Примерен код:

#include <iostream.h>
int main()
{
const int len = 10;
int a[len]={30,40,20,80,70,60,50,90,100,10};
		int b,c,d;
		for(int i=0;i<=len;i++){
		  d = a[i];
		  b = i;
		  for(int j=i+1;j<len;j++){
			 if(a[j]<d){
					 d=a[j];
					 b=j;
			 }
			 c=a[b];
			 a[b]=a[i];
			 a[i]=c;
		  }		   
		}
for(b=0;b<len;b++) cout<<a[b]<<endl;
cin.get();
return 0;
}

 

2. Пряко вмъкване

1. Всеки път се премахва един елемент от входния масив, и се вмъква на правилното
    
   място в масива който ще ни даде резултата.
   
2. Няма значение в какъв ред взимаме елементите от входния масив.
   
3. Повтаря се докато не останат елементи никакви в входния масив
   

http://upload.wikimedia.org/wikipedia/en/2/25/Insertion_sort_animation.gif

 

Ето примерен код:

#include <iostream.h>
int main()
{
const int len = 10;
int a[len]={30,40,20,80,70,60,50,90,100,10};
	for (int i=2; i<=len-1; i++)
		 {
		 	int x = a[i]; 
	   		int j = i - 1; 
		 	a[0] = x;
		  
			while (x < a[j]) {
		 		a[j + 1] = a[j];
	 			j--;
		   		}
	
			 a[j + 1] = x;
		  }
for(int b=0;b<len;b++) cout<<a[b]<<endl;
cin.get();
return 0;
}

 

3. Методът на "Мехурчето"

1. Обхожда се целия масив
   
2. Сравняват се 2 елемента, ако първия е по-голям от втория те разменят местата си.
   
3. Обходът на масива се повтаря до правилната подредба на масива.
   

http://upload.wikimedia.org/wikipedia/en/3/37/Bubble_sort_animation.gif

 

Примерен код:

#include <iostream.h>
int main()
{
int a,b,c;
const int RAZMER = 10;
int chisla[RAZMER] = {123,10,13,55,33,54,32,76,16,101};
for(a=0;a<RAZMER-1;a++)
{
	for(b=1;b<RAZMER;b++)
	{
		if(chisla[b]<chisla[b-1])
		{
			 c = chisla[b];
			 chisla[b]= chisla[b-1];
			 chisla[b-1]=c;						
		}
	}											
}
for(a=0;a<RAZMER;a++)
{
	cout<<a<<"::"<<chisla[a]<<"\n";
}
cin.get();
return 0;
}

 

4. Сортиране чрез клатене

1. Обхожда се целия масив в двете посоки.
   
2. Сравняват се две стойности, ако не са на правилното си място се разменят.
   
3. Повтаря се до правилната подредба.
   

Както забелязвате този метод е много близък до методът на "мехурчето".

 

Примерен код:

#include <iostream.h>
int main()
{
const int r = 10;
int a,b=0,c=r-1,i,n[r] = {30,40,20,80,70,60,50,90,100,10};
bool ok = true;
while(ok==true)
{
	 ok = false;
	 for(i=b;i<c;i++)
	 {
			 if(n[i]>n[i+1])
			 {
					 a = n[i];
					 n[i] = n[i+1];
					 n[i+1]=a;
					 ok = true;
			 }
	 }
	 c--;
	 for(i=c;i>b;i--)
	 {
		   if(n[i] < n[i - 1])
		   {
				a = n[i];
				n[i] = n[i-1];
				n[i-1]=a;
				ok = true;   
		   }
	 }
	 b++;			 
}
for(i=0;i<r-1;i++) cout<<i<<"::"<<n[i]<<"\n";
cin.get();
return 0;
}

 

to be continued...

В статията са използвани анимации от Wikipedia, кодът е пренаписан на C++ от псевдокода който използват в Wiki. от мен (Crio)

 

В духа на Wikipedia и свободния софтуер тази статия, или части от нея могат да бъдат разпространявани свободно, при едно условие:

Авторът на статията (Crio), както и оригиналния източник (Wiki) да бъдат споменати!

 

Автор:

Милен Иванов a.k.a. Crio

[dakan]

Можеш ли да ми разясниш наименуванията на тези алгоритми на български, аз ги познавам само на английски и ми е интересно какви точно наименувания се ползват за тях. Ето това което вече съм разбрал:

• Пряка селекция / Selection Sort
• Пряко вмъкване - този не се ли нарича просто "вмъкване" ?/ Insertion Sort
• Методът на "Мехурчето" / Bubblesort

  4.Сортиране чрез клатене / Quicksort ?? не този алгоритъм също не мога да се сетя кой е. Можеш ли да ми кажеш английското му наименуване?

[as9993]

Наименованието на Quicksort на български е "Бързо сортиране", тоест това е по-често срещаното име, но мисля, че и двете са правилни, а най-точно е да се използва английското му наименование, за да няма разминавания.

 

За Insertion sort нямам представа какъв е точният български превод, заради това нека колегата Crio да отговори.

Поне според мен, най-правилно е да се използват английските наименования, защото са се наложили по света и по този начин се избягват грешките.