VPF::[c++]Сортировки - Форум программистов

maxnsk82

Дата 20.1.2010, 20:07 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 74
Регистрация: 27.6.2009

Репутация: нет
Всего: нет

Задание:Сортировка Шелла. Частичную сортировку с заданным шагом, начиная с заданного элемента оформить в виде функции. Алгоритм частичной сортировки - вставка погружением.

Кое что есть, функция сортировки погружением работает, но нужно что бы она была в сортировке Шелла...я так думаю что с переменной step не как надо обращаюсь:

Код


# include <stdio.h>
# include <conio.h>

const int sz=10;//размер массива

void sort(int B[],int step);
void sortShell(int A[]);

void main()
{
    
    printf ("Input %d numbers: ",sz);
    int A[sz];
    for (int i=0;i<sz;i++)
    {
        scanf_s ("%d",&A[i]);//ввод массива пользователем
    }
    sortShell(A);                         //если вызвать sort(A), то выдаёт упорядоченный массив
    printf ("\n\nUporjadochennyj massiw: ");
    for (int j=0;j<sz;j++)
    printf ("%d ",A[j]);//вывод упорядоченного массива
    _getch();
}

void sortShell(int A[])
{
    int sh=8;//первоначальный шаг сортировки Шелла
    int step=0;
    int B[20];//массив используемый для сортировки
    while (sh>=1)
    {    
        for (int i=0;i<sh;i++)
        {
            for (int j=0,k=i;k<sz;j++,k+=sh)
            {
                B[j]=A[k];//занисим в В эелементы из А с заданным шагом
                step++;
            }
            sort(B,step);//сортируем погружением
            for (int j=0,k=i;k<sz;j++,k+=sh)
            {
                A[k]=B[j];//возвращаем из В упорядоченные элементы в А
            }
            step=0;        
        }if (sh=1) break;
        sh/=2;
    }
}

void sort(int B[],int step)//функция сортировки погружением
{
    int i,j,tmp; 
    for (i=1;i<step;i++)
        {tmp = B[i];
        for (j=i;j>0;j--)
            if(B[j-1]>tmp)
            {
                B[j]=B[j-1];
                B[j-1]=tmp;
            }
            else break;
        }
    
}

t_gran

Дата 21.1.2010, 04:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Ну сам (рабочий) алгоритм Шелла выглядит так:

Код


void SortShell (int arr[], int size)
{
   int step= size/2;
   while (step > 0)
   {
      for (int i= step; i < size; i++)
      {
         int j;
         int buff= arr[i];
         for (j= i - step; (j >= 0) && (arr[j] > buff); j-= step)
            arr[j+step]= arr[j];
         arr[j+step]= buff;
      }
      step/= 2;
   }
}

Но учитывая, что вам алгоритм частичной сортировки нужно выполнить отдельно, то я не могу взять в толк, почему у функции sort передаётся всего 2 параметра а не 3? Ведь кроме самого массива и шага, нужно знать правую стартовую границу. + Ко всему вы должны били реализовать частичную, а не полную сортировку, т.е. переместить правый элемент ниже, на своё место, и всё.

В общем результат должен быть примерно таким:

Код


//----------------------------------------------//
void Sort (int arr[], int pos, int step)
{
   int j;
   int buff= arr[pos];
   for (j= pos - step; (j >= 0) && (arr[j] > buff); j-= step)
      arr[j+step]= arr[j];
   arr[j+step]= buff;
}
//----------------------------------------------//
void SortShell (int arr[], int size)
{
   for (int step= size/2; step > 0; step/= 2)
      for (int pos= step; pos < size; pos++)
         Sort(arr, pos, step);
}
//----------------------------------------------//

Это сообщение отредактировал(а) t_gran - 21.1.2010, 05:16

--------------------

Я знаю, что ничего не знаю© Сократ
user posted image

maxnsk82

Дата 21.1.2010, 09:16 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 74
Регистрация: 27.6.2009

Репутация: нет
Всего: нет

Спасибо за помощь. Работает и похоже так как требуется)

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »