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

Kit0boy

Дата 22.3.2011, 17:00 (ссылка)

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

Загрузка ...

Новичок

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

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

Нужно сделать сортировку двумерного массива методом Шелла. Чтобы элементы, стоящие на нечетных местах стояли по возрастанию. Не могу понять этот метод.

t_gran

Дата 23.3.2011, 10:44 (ссылка)

(голосов:1)

Загрузка ...

Опытный

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

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

Реализовал для одномерного массива, а там по аналогии сделаете для двумерного (ведь что-то Вы тоже должны сами сделать, не так ли? smile

)

Код


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//----------------------------------------------//
// Заполнение массива случайными значениями
void Random(int arr[], unsigned len)
{
   srand(time(0));
   unsigned i;
   for (i = 0; i < len; ++i)
   {
      arr[i] = rand() % (2*len);
   }
}
//----------------------------------------------//
// Вывод значений массива на экран
void Print(int arr[], unsigned len)
{
   unsigned i;
   for (i = 0; i < len; ++i)
   {
      printf("%3d", arr[i]);
   }
   printf("\n");
}
//----------------------------------------------//
// Сортировка вставками с учётом шага
void InsertSort(int arr[], unsigned len, unsigned step) 
{
   unsigned i, j;
   int key;
   for (i = step; i < len; i += step) 
   {
      key = arr[i];
      j = i;
      while ((j > 0) && (arr[j-step] > key))
      {
         arr[j] = arr[j-step];
         j -= step;
      }
      arr[j] = key;
   }
 }
//----------------------------------------------//
// Сортировка Шелла (для примера, но нигде не используется)
void ShellSort(int arr[], unsigned len)
{
   unsigned step = len / 2;
   while (step)
   {
      InsertSort(arr, len, step--);
   }
}
//----------------------------------------------//
// Сортировка Шелла только для чётных элементов
void ShellSortOnlyOdd(int arr[], unsigned len)
{
   unsigned step = len / 2;
   while (step)
   {
      InsertSort(arr, len, step);
      step -= 2;
   }
}
//----------------------------------------------//

int main(int argc, char **argv)
{
   int arr[20];
   
   unsigned len = sizeof(arr)/sizeof(*arr);
   
   Random(arr, len);

   printf("array:\t");
   Print(arr, len);

   ShellSortOnlyOdd(arr, len);

   printf("sorted:\t");
   Print(arr, len);
   
   return 0;
}

Результат выполнения

Бинарник с исходником ниже

Присоединённый файл ( Кол-во скачиваний: 12 )

sort_shell.zip 2,36 Kb

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

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

Kit0boy

Дата 23.3.2011, 12:19 (ссылка)

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

Загрузка ...

Новичок

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

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

Вы даже больше, чем нужно сделали, спасибо) Я не совсем уж ничего не делал, все по возрастанию я отсортировал, а вот через один косячил. Спасибо еще раз.

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