Тут на неделе пришлось стокнуться с некоторыми методами сортировки (их намного больше) - решил показать.
Сортировка Шелла
Выбирается интервал 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;
}