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

  • Автор темы slay09
  • Дата начала
S

slay09

Гость
#1
Здравствуйте! Написал программу по сортировке массива методом Шелла. И вот с проблемой одной разобраться не могу. Все отлично сортируется кроме первого элемента! Как не ломал целый день голову не могу понять в чем дело. Независимо от количества элементов и от вида массива первый элемент не сортируется и все тут! Знаю что возможно это слишком легко чтобы задавать вопрос на форум, но к сожалению мне больше не куда обратиться, а сам я не вижу ошибки. Если кто разбирается в сортировках прошу вашей помощи.
Сама сортировка происходит в функции "sort".

Код:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define N 100 //кол-во эл-в массива
void sort (long *x, long n); // прототип функции сортировки методом Шелла

main ()
{
clrscr();
long x[N]; // обьявление массива x[N]
int i;
randomize ();
printf ("\n Vyvod massiva: \n");
for (i=0;i<N;i++)
{x[i]=random(99); //массив заполняется случ. Числами (до 99)
printf("%5d",x[i]);}
sort (x,N);
getch();}

void sort(long* x,long n )
{
int i,k,tmp,c,m;
c=0; m=0;	// Переменные для подсчета кол-ва сравнений и обменов между Эл-ми
int incr=n/2;	
while (incr>0)
{
for (i=incr; i<n; i++)
{
k=i-incr;
while (k>0)
{
c++;
if (x[k]>x[k+incr])
{
tmp=x[k]; x[k]=x[k+incr]; x[k+incr]=tmp;
m++; k=k-incr;
}
else k=0;
}
}
incr=incr/2;
}

printf ("\n\n Sortirovka metodom Shella: \n");
for (i=0; i<n; i++)
printf("%5ld", x[i]);
printf ("\n\n Kolichestvo sravneniy = %d", c);
printf ("\n kolichestvo peresylok = %d", m);
}
P.S. Знаю есть другая версия сортировки Шелла, но там я не смог реализовать подсчет количества сравнений и обменов между элементами и поэтому прошу помощи именно с этим кодом.
 
C

Charley2

Гость
#2
Проблема была с условием while: k должно быть больше либо равно 0. Весь исходный код я не проверял, но по-крайней мере сортирует прога все элементы правильно. На всякий случай привожу весь исходный код:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define N 100 //кол-во эл-в массива
void sort (long *x, long n); // прототип функции сортировки методом Шелла

main ()
{
clrscr();
long x[N]; // обьявление массива x[N]
int i;
randomize ();
printf ("\n Vyvod massiva: \n");
for (i=0; i<N; i++)
{
x=random(99); //массив заполняется случ. Числами (до 99)
printf("%5d",x);}
sort (x,N);
getch();
}

void sort(long* x,long n )
{
int i,k,tmp,c,m;
c=0; m=0; // Переменные для подсчета кол-ва сравнений и обменов между Эл-ми
int incr=n/2;
while (incr>0)
{
for (i=incr; i<n; i++)
{
k=i-incr;
while (k>=0)
{
c++;
if (x[k]>x[k+incr])
{
tmp=x[k]; x[k]=x[k+incr]; x[k+incr]=tmp;
m++; k=k-incr;
}
else k=-1;
}
}
incr=incr/2;
}

printf ("\n\n Sortirovka metodom Shella: \n");
for (i=0; i<n; i++)
printf("%5ld", x);
printf ("\n\n Kolichestvo sravneniy = %d", c);
printf ("\n kolichestvo peresylok = %d", m);
}