сортировка C++.

[Koshak]

дайте пожалуйста код C++, где приводиться пример Улучшеной сортировки обменом и шейкерной сортировки.

[Sheogorath]

template< typename Iterator >
void cocktail_sort( Iterator first, Iterator last )
{
for( --last; first < last; --last, ++first )
{
for( Iterator i = first; i < last; ++i )
if ( *(i + 1) < *i )
std::iter_swap( i, i + 1 );

for( Iterator i = last - 1; i > first; --i )
if ( *i < *(i - 1) )
std::iter_swap( i, i - 1 );
}
}

  #include 

{
if (L >= R)
return;
int m = (L + R) /2;//int m = (L + R) >>1; \\ сдвиг работает быстрее.
int mediana = arr[m];
int LL = L;
int RR = R;
while (LL < RR) {
while (arr[LL] < mediana)
LL++;
while (arr[RR] > mediana)
RR--;
if (LL <= RR) {
int swap = arr[LL];
arr[LL] = arr[RR];
arr[RR] = swap;
LL++;
RR--;
}
}
if (LL sort (arr , LL , R);
if (RR > L)
sort (arr , L , RR);
}
void main(void) {
int arr[] = { 1, 3, 2, 7, 5, 8, 0, 4, 6, 9 };
int ARR_LENGTH = sizeof (arr) / sizeof (int);
sort (arr , 0 , ARR_LENGTH - 1);
for (int i=0; i < ARR_LENGTH; i++)
printf ("%4d" , arr [i] );
}

void sort(int arr[], int L, int R)

[Koshak]

а можно попроще

[Sheogorath]

#include
void SheikerSort(int *a, const int n)
{
int l, r, i, k, buf;
k = l = 0;
r = n - 2;
while(l <= r)
{
for(i = l; i <= r; i++)
if (a[i] > a[i+1])
{
buf = a[i]; a[i] = a[i+1]; a[i+1] = buf;
k = i;
}
r = k - 1;
for(i = r; i >= l; i--)
if (a[i] > a[i+1])
{
buf = a[i];
a[i] = a[i+1];
a[i+1] = buf;
k = i;
}
l = k + 1;
}
}

int main()
{
int i, a[5] = {50, 40, 30, 20, 10};
SheikerSort(a, 5);
for(i = 0; i < 5; i++)
printf("%d ", a[i]);
getchar();
}

Квиксорт итак легкий.

[haha]

Koshak

«Вон из профессии»

[Koshak]

haha

умно

[Klonizz]

qsort есть в библиотеке stdlib.h пользоваться очень легко

Нам понадобиться такая вот функция

int compare (const void * a, const void * 
{
  return ( *(int*)a - *(int*)b );
}

Сам вызов

qsort (values, n, sizeof(int), compare);

где

values - имя массива

n- его размер

остальное думаю понятно...

P.S. Для каждого типа функция compare будет иметь свой вид

[Koshak]

а есть у кого реализация сортировки шелла,пирамидальной,слиянием?

[Lakers]

просторы кишат примерами реализаций

[Koshak]

может покажется старнным, но шелла и бинарные вставки не нашел на одной из 25 страниц яндексаточнее,ни,конечно, есть,но где-то не работают, где-то на других языках, где-то используются еще не понятные мне функции...

[Sheogorath]

#include 
#include 
using namespace std;

void shellsort(int a[],int n)
{
int j,i,k,m,mid;
	for(m = n/2;m>0;m/=2){
		for(j = m;j< n;j++){
			for(i=j-m;i>=0;i-=m){
				if(a[i+m]>=a[i])
				break;
			else{
			mid = a[i];
			a[i] = a[i+m];
			a[i+m] = mid;}
			}
		}
	}
}
int main(void)
{
int a[10],i,n;
system("cls");
printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++){
	printf("\nElement %d\t: ",i+1);
	scanf("%d",&a[i]);
}
printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
	printf("%5d",a[i]);
shellsort(a,n);
printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
	printf("%5d",a[i]);
getch();
return 0;
}

[Koshak]

а где вычисляется шаг?

[zaki]

shaker sort

#include

#include

#include

using namespace std;

const int len=4;

int a[len];

void shakersort()

{

int napr, tmp, p, j, k;

p=0; //Текущая позиция в массиве

napr = 1; //Направление движения: 1- слево на право, -1 справо на лево

for (k=len-1;k>=1;k--) //k - количество сравниваемых пар

{ //с уменьшением k отсекаем границы

//(при проходе вправо до конца границы максимальный элемент выталкивается на границу, таким обр. мы его не рассматриваем)

//при движении в обратном направлении на левую границу выталкивается минимальный элемент, таким обр. цикл перестановки его не рассматривает

//за счет сужения границ достигается оптимизация, стандартного алгоритма "пузырька"

for (j=1; j<=k; j++) //Производим перестановку в заданных границах

{

if ((a[p]-a[p+napr])*napr>0)

{

tmp = a[p]; //Перемещение числа

a[p] = a[p+napr];

a[p+napr] = tmp;

}

p=p+napr;

}

napr = -napr; //left => right

p = p+napr; //отсекаем граничный элемент

}

}

void main()

{

int i;

for ( i=0; i<=len; i++)

a=rand();

cout << "Ishodniy - " <

for (int i=0; i<=len; i++)

cout <

shakersort();

cout <

for (int i=0; i<=len; i++)

cout <

[Koshak]

мне шейкер сорт уже давно не нужен

[Koshak]

поделитесь сортировкой слиянием...

[Sheogorath]

#include "conio.h"
#include "stdio.h"
#include "locale.h"
void main ()
{
int ArrayA[20], ArrayB[20];
int length, i, j, temp, piece, s, amount, k, k1, k2, span;
setlocale (LC_ALL,"RUSSIAN");
printf ("Введите длину массива: ");
scanf ("%i",&length);
printf ("_________________________________\n");
printf ("Введите элементы массива \n");
for (i=0;iscanf ("%i", &ArrayA[i]);
piece=1;	/* начальная длина "подмассивов"*/
if (length % 2 == 0) amount=length/2;	/* узнаём количество частей.*/
else amount=(length-1)/2;
do
{
piece=piece*2;	/* длина "подмассива" увеличивается в два раза*/
if (amount % 2==0)	/* количество частей уменьшается в два раза*/
amount=amount/2;
else amount=(amount+1)/2;
if (piece>length)	/* условие, предохранающее от сравнивания чисел, лежащих за "сеткой" массива*/
piece=length;
span=0; /* проверка снова начинается с начала массива*/
for (k=0;k<=amount+1;k++)	/*цикл для упорядочивания*/
{
s=span+piece;	/* вспомогательная переменная, необходима ниже*/
if (span+piece<=length) /* пока не проверится последний "подмассив"*/
for (k2=0;k2for (i=span; i{
if (ArrayA[i]>ArrayA[i+1])
{
temp=ArrayA[i];
ArrayA[i]=ArrayA[i+1];
ArrayA[i+1]=temp;
}
}
span=span+piece; /* переход на следующий "подмассив" */
}
}
while (pieceprintf ("_________________________________\n");
printf ("Отсортированный массив:\n");
ArrayB[0]=ArrayA[0];
j=0;
printf ("%i ", ArrayB[0]);
for (i=1;i{
{// сравнивая каждый последующий элемент
j=j+1;
ArrayB[j]=ArrayA[i];
printf ("%i ", ArrayB[j]);
}
}
j=1;
int mj=ArrayB[0];
i=1;
while(iif(ArrayB[i]!=mj)
{
j++;
mj=ArrayB[i];
}
i++;}
printf ("\n_________________________________\n");
printf ("Количество различных элементов: ");
printf("\n%i",j);
getch();
}

Там прога еще ищет количество различных элементов, но это можно вырезать.

[Koshak]

*156 спасибки