Уроки C++

Сортировка Шелла C++

Этот вид сортировки на порядок серьёзней в реализации по сравнению сортировкой “Пузырьком”. Но и время, затраченное на сортировку массива значительно меньше, правда заметно это будет при весьма большом количестве элементов. Данный алгоритм базируется на примере из книги Герберта Шилдта, он рассматривается как пример на языке “C”, есть написанный алгоритм и на “C++”, но он весьма больше этого и новичка может изрядно испугать. Но если вам нужна реализация именно на “C++”, то вот ресурс, где она находится - здесь. Ну а здесь же вы можете увидеть рабочий пример сортировки “Шелла”, вот он:

---

#include "stdafx.h"
#include "iostream"
#include "time.h"
#include "iomanip"
#include "algorithm"

using namespace std;

void shell(int *, int);   // объявление функции сортировки

int main()
{
setlocale(LC_ALL, "Russian");
int n; // Количество элементов массива
cout << "Введите размер массива: ";
cin >> n;
cout << endl;
cout << "Массив: " << endl;
int *mas = new int [n];
srand(time(NULL));
for (int i = 0; i < n; i++)
{
mas[i] = rand() % 200 - 100;   // заполняем массив случайными числами
cout << setw(2) << mas[i] << " ";   // выводим массив на экран
}
cout << "\n\n";

shell(mas, n);   // вызываем функцию Быстрой сортировки
cout << "Отсортированный массив: " << endl;
for (int i = 0; i < n; i++)
{
cout << mas[i] << " ";   // Вывод на экран отсортированного массива
}
cout << "\n\n";
system("PAUSE");
return 0;
}

void shell(int *sort_el, int c)
{
register int i, j, temp, k;
int x, m[5];
m[0]=9; m[1]=5; m[2]=3; m[3]=2; m[4]=1;
for(k=0; k < 5; k++) {
temp = m[k];
for(i=temp; i < k; ++i) {
x = sort_el[i];
for(j=i-temp; (x < sort_el[j]) && (j >= 0); j=j-temp)
sort_el[j+temp] = sort_el[j];
sort_el[j+temp] = x;
    }
  }
}

---

Результат:



<< К списку сортировок

---