forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)
-   C++ (http://forum.boolean.name/forumdisplay.php?f=22)
-   -   Алгоритмы сортировки (http://forum.boolean.name/showthread.php?t=89)

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



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

Выбирается интервал 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;
}

impersonalis 16.09.2005 17:07
Челночная сортировка
описание нарыл где-то в сети
Челночная сортировка представляет собой стандартный обмен, выполняемый в двух направлениях:
1. При движении «вниз» попарно сравниваются соседние элементы и при необходимости переставляются местами. Сравнения данного вида называются ПЕРВИЧНЫМИ (НИСХОДЯЩИМИ).
2. Как только производится перестановка элементов, выполняется попарное сравнение элементов и при необходимости их перестановка при движении «вверх». Сравнения данного вида называются ВТОРИЧНЫМИ. Вторичные сравнения прекращаются при невозможности поднять более «легкий» элемент вверх. После прекращения вторичных сравнений возобновляются первичные сравнения.
Код:
#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>

void CHELN_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);
        CHELN_sort(x,N);
        output(x,N);
        cout<<"Press any key\a";
        cout<<endl;
        getch();
}

void CHELN_sort(int a[],long N){
        cout<<"CHELN_sort RUN\n";
        for(int j=0;j<N-1;j++){
 if(a[j]>a[j+1]){
        a[j]=a[j]+a[j+1];
        a[j+1]=a[j]-a[j+1];
        a[j]=a[j]-a[j+1];
        for(int i=j;i>0;i--){
  if(a[i]<a[i-1]){
          a[i]=a[i]+a[i-1];
          a[i-1]=a[i]-a[i-1];
          a[i]=a[i]-a[i-1];
  }
  else break;
        }
 }
        }
}

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;
}

alcosholik 17.09.2005 04:05
Если вы собираетесь тестить приведенный выше код в VS .NET, то нужно заменить это:
Код:
#include<iostream.h>
на это
Код:
#include<iostream>
using namespace std;

impersonalis 17.09.2005 04:10
Код:
#include<math.h>
#include<stdlib.h>
Для MSVC++ достаточно только #include<stdlib.h>
для Borland Builder - только #include<math.h>

Guest 06.10.2005 00:57
Привет народ!
подскажите плиз как переделать код челночной сортировки под шаблоны...
заранее сенкс =)

impersonalis 06.10.2005 01:00
вносим коррективы типа
Код:
template<class abstr>
перед прототипами функций и их телами. Собсно, заменяем конкретный тип данных - например целочисленный int на шаблон
Код:
abstr a[]
Далее я изменил код ф-ции main() для наглядности:
она последовательно обррабатывает массив типа Int,float and char.
Код:
#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>

template<class abstr>
void CHELN_sort(abstr a[],long N);
template<class abstr>
void input(abstr a[],long N);
template<class abstr>
void output(abstr a[],long N);

void main(){
        long N;
        cout<<"N?\n";
        cin>>N;
        cout<<"for int"<<endl;
        int *xint=new int[N];
        input(xint,N);
        output(xint,N);
        CHELN_sort(xint,N);
        output(xint,N);
        cout<<"Press any key\a";
        cout<<endl;
        delete xint;
        float *xfloat=new        float[N];
        cout<<"for float"<<endl;
        input(xfloat,N);
        output(xfloat,N);
        CHELN_sort(xfloat,N);
        output(xfloat,N);
        cout<<"Press any key\a";
        cout<<endl;
        delete xfloat;
        char *xchar=new        char[N];
        cout<<"for char"<<endl;
        input(xchar,N);
        output(xchar,N);
        CHELN_sort(xchar,N);
        output(xchar,N);
        cout<<"Press any key\a";
        cout<<endl;
        getch();
}
template<class abstr>
void CHELN_sort(abstr a[],long N){
        cout<<"CHELN_sort RUN\n";
        for(int j=0;j<N-1;j++){
 if(a[j]>a[j+1]){
        a[j]=a[j]+a[j+1];
        a[j+1]=a[j]-a[j+1];
        a[j]=a[j]-a[j+1];
        for(int i=j;i>0;i--){
  if(a[i]<a[i-1]){
          a[i]=a[i]+a[i-1];
          a[i-1]=a[i]-a[i-1];
          a[i]=a[i]-a[i-1];
  }
  else break;
        }
 }
        }
}
template<class abstr>
void input( abstr 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()%255)*0.1;
        }
        else{
 for(int i=0;i<N;i++){
        cout<<"a["<<i<<"]=";
        cin>>a[i];
 }
        }
}
template<class abstr>
void output(abstr a[],long N){
        cout<<"output ===\n";
        for(int i=0;i<N;i++)
 cout<<"a["<<i<<"]="<<a[i]<<" ("<<float(a[i])<<")"<<endl;
}

impersonalis 23.10.2005 17:38
Центрированная вставка
Видел несколько схожих описаний алгоритма. По сути: работа с массивом как с бинарным древом поиска, но при этом гибкость, получаемая при реализации связанным списком, отсутствует - так что код громоздкий и медленный (по сравнению с возможным: скорость падает на сдвигах эл-тов и завершающем копировании, но экономится время при поиске места). Вероятно, рассчитан на специфические входные данные.
Код:
#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();
}

impersonalis 25.10.2005 22:38
Кто придумает: почему, и без того не увжаемый мной, Builder не сортирует по данному коду массив, а Visual Studio делает это "на ура" - получит от меня + к рейтингу ;)

это я про центрированную вставку

jimon 26.10.2005 14:03
мне влом искать там всякие ***** :)
говорю одно : для билдера надо еще сверху include "vcd.h" или как его там... мне в лом смотреть

:lol:

impersonalis 26.10.2005 22:44
Цитата:
Originally posted by jimon@Oct 26 2005, 12:03 PM
мне влом искать там всякие ***** :)
говорю одно : для билдера надо еще сверху include "vcd.h" или как его там... мне в лом смотреть

:lol:
Блин - без этого бы вообще не скомпилилось - разумеется код пишется в подготовленный мастером файл - все инкулды и проч на месте. Код комплится и не сортирует массив.

impersonalis 07.11.2005 22:50
Комбинированный метод

Для больших массивов ( или, при рекурсивном вызове, частей массивов) используем буыструю сортировку, для частей с длиной меньше параметра (M) - сортировку пузырьком.

Примерно так:
Код:
#include<iostream.h>
#include<conio.h>

void B_Sort(int a[],long N){
        int temp;
        for(int j=1;j<N;j++){
 for(int i=0;i<N-j;i++){
        if(a[i]>a[i+1]){
  temp=a[i];
  a[i]=a[i+1];
  a[i+1]=temp;
        }
 }
        }
}

void Quick_Sort(int a[], long N,int M) {
        long left=0, right=N-1;
        int temp;
        int c=a[ N>>1 ];
        do {
 while ( a[left] < c ) left++;
 while ( a[right] > c ) right--;

 if (left <= right) {
        temp = a[left];
        a[left] = a[right];
        a[right] = temp;
        left++;
        right--;
 }
        } while ( left<=right );

        if ( right > 0 ){
 if (right>=M)
        Quick_Sort(a, right,M);
 else
        B_Sort(a,right);
        }
        if ( N > left ){
 if (N-left>=M)
        Quick_Sort(a+left, N-left,M);
 else
        B_Sort(a+left, N-left);
        }
}



void main(){
        int N;
        cin>>N;
        int *m=new int[N];
        int i=0;
        for( i=0;i<N;i++)
 cin>>m[i];
        Quick_Sort(m,N,4);
        cout<<"-----"<<endl;
        for( i=0;i<N;i++)
 cout<<m[i]<<endl;
        getch();
}


Часовой пояс GMT +4, время: 23:24.

vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot