[impersonalis]

Тут на неделе пришлось стокнуться с некоторыми методами сортировки (их намного больше) - решил показать.



Сортировка Шелла

Выбирается интервал D между сравниваемыми элементами и выполняется сортировка методом "пузырька", но с шагом D. После выполнения интервал уменьшается по ф-ле
D(k)=[D(k+1)-1]/2

#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>

void SHELL_sort(int a[],long N);
void input(int a[],long N);
void output(int a[],long N);

void main(){
	long N;
	cout<<"N?\n";
	cin>>N;
	int *x=new int[N];
	input(x,N);
	output(x,N);
	SHELL_sort(x,N);
	output(x,N);
	cout<<"Press any key\a";
	cout<<endl;
	getch();
}

void SHELL_sort(int a[],long N){
	cout<<"SHELL_sort RUN\n";
	long D=N-1;
	while(D>0){
 *for(int j=1;j<N;j+=D){
 *	for(int i=0;i<N-j;i++){
 * *if(a[i]>a[i+1]){
 * *	//a=a+b
 * *	//b=a-b
 * *	//a=a-b
 * *	a[i]=a[i]+a[i+1];
 * *	a[i+1]=a[i]-a[i+1];
 * *	a[i]=a[i]-a[i+1];
 * *}
 *	}
 *}
 *D=(D-1)*0.5;
	}
}

void input( int a[],long N){
	cout<<"Select type:"<<endl;
	cout<<"1) Random"<<endl;
	cout<<"2) Manually"<<endl;
	char p=getch();
	if(p=='1'){
 *for(int i=0;i<N;i++)
 *	a[i]=rand()%50;
	}
	else{
 *for(int i=0;i<N;i++){
 *	cout<<"a["<<i<<"]=";
 *	cin>>a[i];
 *}
	}
}

void output(int a[],long N){
	cout<<"output ===\n";
	for(int i=0;i<N;i++)
 *cout<<"a["<<i<<"]="<<a[i]<<endl;
}