Центрированная вставка
Видел несколько схожих описаний алгоритма. По сути: работа с массивом как с бинарным древом поиска, но при этом гибкость, получаемая при реализации связанным списком, отсутствует - так что код громоздкий и медленный (по сравнению с возможным: скорость падает на сдвигах эл-тов и завершающем копировании, но экономится время при поиске места). Вероятно, рассчитан на специфические входные данные.
#include<iostream.h>
#include<conio.h>
void sort(int m[],int n){
cout<<"start function!"<<endl;
int *b=new int[n];//
int c=n*0.5;//
int left_ptr=0;//
int right_ptr=c+1;//
b[c]=m[0];//
cout<<"Value of a median "<<b[c]<<";On a position="<<c<<endl;
cout<<"--"<<endl;
for(int i=1;i<n;i++){//
*cout<<endl<<"analysis of value "<<m[i]<<";On a position="<<i<<endl;
*if(m[i]<b[c]){
* cout<<"Choice of the left branch"<<endl;
* //++++
* if(left_ptr==c){
* *cout<<"left branch is loaded - displacement elements"<<endl;
* *for(int j=right_ptr;j>left_ptr;j--){//+1
* * b[j]=b[j-1];
* *}
* *c++;
* *left_ptr++;
* }
* for(int j=0;j<=left_ptr;j++){
* *//@
* *if(m[i]<b[j]){
* * cout<<"The place of an analyzed element is not empty - displacement of elements"<<endl;
* * for(int j2=left_ptr;j2>j;j2--){//+1
* * *b[j2]=b[j2-1];
* * }
* * left_ptr++;
* * b[j]=m[i];
* * break;
* *}
* *//@
* *if(j==left_ptr){
* * cout<<"Are analyzed an element has taken a place at the end of a branch"<<endl;
* * left_ptr++;
* * b[j]=m[i];
* * break;
* *}
* }
* //++++
*}
*////////////////////
*else{
* cout<<"Choice of the right branch"<<endl;
* //++++
* if(right_ptr==n){
* *cout<<"right branch is loaded - displacement elements"<<endl;
* *for(int j=left_ptr;j<right_ptr;j++){//-1
* * b[j]=b[j+1];
* *}
* *c--;
* *right_ptr--;
* }
* for(int j=0;j<=right_ptr;j++){
* *//@
* *if(m[i]<b[j]){
* * cout<<"The place of an analyzed element is not empty - displacement of elements"<<endl;
* * for(int j2=right_ptr;j2>j;j2--){//+1
* * *b[j2]=b[j2-1];
* * }
* * right_ptr++;
* * b[j]=m[i];
* * break;
* *}
* *//@
* *if(j==right_ptr){
* * cout<<"Are analyzed an element has taken a place at the end of a branch"<<endl;
* * right_ptr++;
* * b[j]=m[i];
* * break;
* *}
* }
* //+++++
*}
*////////////////////////
*cout<<"array: ";
*for(int ii=0;ii<n;ii++)
* cout<<b[ii]<<";";
*cout<<endl;
}
cout<<"copy..."<<endl;
for(int j=0;j<n;j++){
m[j]=b[j];
}
cout<<"end function!"<<endl;
}
void main(){
int n;
cin>>n;
int *m=new int[n];
int i;
for( i=0;i<n;i++){
*cin>>m[i];
}
sort(m,n);
cout<<"**"<<endl;
for(i=0;i<n;i++){
*cout<<m[i]<<endl;
}
getch();
}