|
16.09.2005, 16:46
|
#1
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Тут на неделе пришлось стокнуться с некоторыми методами сортировки (их намного больше) - решил показать.
Сортировка Шелла
Выбирается интервал 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;
}
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
16.09.2005, 17:07
|
#2
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Челночная сортировка
описание нарыл где-то в сети
Челночная сортировка представляет собой стандартный обмен, выполняемый в двух направлениях:
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;
}
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
17.09.2005, 04:05
|
#3
|
|
Если вы собираетесь тестить приведенный выше код в VS .NET, то нужно заменить это:
на это
#include<iostream>
using namespace std;
|
|
|
17.09.2005, 04:10
|
#4
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
#include<math.h>
#include<stdlib.h>
Для MSVC++ достаточно только #include<stdlib.h>
для Borland Builder - только #include<math.h>
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
06.10.2005, 00:57
|
#5
|
|
Привет народ!
подскажите плиз как переделать код челночной сортировки под шаблоны...
заранее сенкс =)
|
|
|
06.10.2005, 01:00
|
#6
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
вносим коррективы типа
перед прототипами функций и их телами. Собсно, заменяем конкретный тип данных - например целочисленный int на шаблон
Далее я изменил код ф-ции 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;
}
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
23.10.2005, 17:38
|
#7
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Центрированная вставка
Видел несколько схожих описаний алгоритма. По сути: работа с массивом как с бинарным древом поиска, но при этом гибкость, получаемая при реализации связанным списком, отсутствует - так что код громоздкий и медленный (по сравнению с возможным: скорость падает на сдвигах эл-тов и завершающем копировании, но экономится время при поиске места). Вероятно, рассчитан на специфические входные данные.
#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();
}
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
25.10.2005, 22:38
|
#8
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Кто придумает: почему, и без того не увжаемый мной, Builder не сортирует по данному коду массив, а Visual Studio делает это "на ура" - получит от меня + к рейтингу
это я про центрированную вставку
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
26.10.2005, 22:44
|
#10
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Originally posted by jimon@Oct 26 2005, 12:03 PM
мне влом искать там всякие *****
говорю одно : для билдера надо еще сверху include "vcd.h" или как его там... мне в лом смотреть
|
Блин - без этого бы вообще не скомпилилось - разумеется код пишется в подготовленный мастером файл - все инкулды и проч на месте. Код комплится и не сортирует массив.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
07.11.2005, 22:50
|
#11
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Комбинированный метод
Для больших массивов ( или, при рекурсивном вызове, частей массивов) используем буыструю сортировку, для частей с длиной меньше параметра (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();
}
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 12:42.
|