Помощ за задача на С++

[mirka]

Моля за помощ за следната задача!

 

Да се извърши сравнително тестване на методите за сортировка, чрез пряка селекция и пряко вмъкване!

 

Предварително благодаря!

[crio]

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. Заключение

Като цяло двата метода си приличат. И при двата, след n обхождания на масива, първите n са вече подредени. За пряката селекция, това са n-те най-малки елементи, докато при прякото вмъкване това са първите n които масива е обходил. Предимството на прякото вмъкване е че то обхожда само толкова елементи колкото са му нужни за да добави докато, метода на пряката селекция трябва да обходи всички елементи за да намери най-малките n елемента. Ако си разбрала обяснението ми върху тези методи, предполагам че ще ти е лесно да решиш задачата.

[mirka]

Сърдечно благодаря!

[dj_parimo]

Някой да знае от къде мога да си намеря компилатора C++?

 

Много ви благодаря предварително!!!

[blood]

Тук.