Сортировка Шелла (реализация на C++)

C++   23 Февраль 2012  Автор статьи:  

Приведем пример реализации сортировки Шелла. Данная сортировка является улучшением сортировки вставками.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;

int main()
{
    // Считываем размер массива,
    // который необходимо отсортировать
    int size;
    cin >> size;

    // Динамически выделяем память под
    // хранение массива размера size
    int *a = new int[size];
   
    // Считываем массив
    for (int i = 0; i < size; i++)
    {
        cin >> a[i];
    }
    int step = size / 2;//инициализируем шаг.
    while (step > 0)//пока шаг не 0
    {
      for (int i = 0; i < (size - step); i++)
                {
                    int j = i;
                    //будем идти начиная с i-го элемента
                    while (j >= 0 && a[j] > a[j + step])
                    //пока не пришли к началу массива
                    //и пока рассматриваемый элемент больше
                    //чем элемент находящийся на расстоянии шага
                    {
                        //меняем их местами
                        int temp = a[j];
                        a[j] = a[j + step];
                        a[j + step] = temp;
                        j--;
                    }
                }
                step = step / 2;//уменьшаем шаг
            }    
    // Выводим отсортированный массив
    for (int i = 0; i < size; i++)
    {
        cout << a[i] << ' ';
    }

    return 0;
}

  • Михаил

    Работает не правильно =(

  • Михаил

    Мои извинения, кривые руки голове покоя не дают =)
    Всё правильно

  • Василмй

    если размер массива будет нечетным, то алгоритм будет работать криво

  • Кирилл

    Работает неправильно. Подсписки массива (элементы, выбранные через шаг) сортируются не полностью — например, если минимальный элемент будет стоять на последнем месте, в первое он не попадет (при шаге большем, чем 1).

    • Кирилл

      Возьмите пример входных данных из википедии, поставьте вывод после каждого шага — увидите

Научиться программировать

  • на Delphi

  • на Java

  • на C++