Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование игр для компьютеров > C++

Ответ
 
Опции темы
Старый 16.09.2005, 16:46   #1
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 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)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Mr_F_ (18.06.2009)
Старый 16.09.2005, 17:07   #2
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 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
alcosholik
 
Сообщений: n/a
Если вы собираетесь тестить приведенный выше код в VS .NET, то нужно заменить это:
#include<iostream.h>
на это
#include<iostream>
using namespace std;
 
Ответить с цитированием
Старый 17.09.2005, 04:10   #4
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 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
Guest
 
Сообщений: n/a
Привет народ!
подскажите плиз как переделать код челночной сортировки под шаблоны...
заранее сенкс =)
 
Ответить с цитированием
Старый 06.10.2005, 01:00   #6
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Смущение

вносим коррективы типа
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;
}
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Старый 23.10.2005, 17:38   #7
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 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
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Смущение

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

это я про центрированную вставку
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Старый 26.10.2005, 14:03   #9
jimon
 
Сообщений: n/a
мне влом искать там всякие *****
говорю одно : для билдера надо еще сверху include "vcd.h" или как его там... мне в лом смотреть

 
Ответить с цитированием
Старый 26.10.2005, 22:44   #10
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 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
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 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)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Некоторые алгоритмы написанные на чистом pascal-е _Nox_ MidletPascal 7 08.07.2010 20:10
программы-поэты, алгоритмы/идеи abcdef Основной форум 10 25.05.2010 22:42
алгоритмы j2me для рисованного интерфейса abcdef Проекты на MidletPascal 7 24.11.2009 16:17
Алгоритмы поведения противника WaReZ_MEN 2D-программирование 4 25.07.2007 01:50
Алгоритмы поиска impersonalis C++ 0 18.09.2005 18:51


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


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com