---
id: 5a23c84252665b21eecc8010
title: Алгоритми сортування/Сортува́ння Ше́лла
challengeType: 1
forumTopicId: 302317
dashedName: sorting-algorithmsshell-sort
---

# --description--

Write a function to sort an array of elements using the Shell sort algorithm, a diminishing increment sort. Функція має повернути впорядкований масив.

Сортування Шелла( також відомий як Шеллове сортування або метод Шелла) названо на честь винахідника Дональда Шелла, який опублікував алгоритм у 1959.

Сортування Шелла — це послідовність впорядкованих вставних сортувань на основі послідовності приросту. Розмір приросту зменшується після кожного проходу, поки розмір приросту не дорівнюватиме 1.

З розміром приросту 1 сортування є базовим сортуванням вставкою, але до цього часу дані гарантовано будуть майже відсортовані, що є «найкращим випадком» сортування вставкою.

Будь-яка послідовність сортує дані до тих пір, поки вони закінчується на 1, але деякі працюють краще, ніж інші.

Емпіричні дослідження показали, що геометрична послідовність приросту з коефіцієнтом приблизно 2,2 добре працює на практиці.

# --hints--

`shellSort` має бути функцією.

```js
assert(typeof shellSort == 'function');
```

`shellSort([25, 32, 12, 7, 20])` має повернути масив.

```js
assert(Array.isArray(shellSort([25, 32, 12, 7, 20])));
```

`shellSort([25, 32, 12, 7, 20])` має повернути `[7, 12, 20, 25, 32]`.

```js
assert.deepEqual(shellSort([25, 32, 12, 7, 20]), [7, 12, 20, 25, 32]);
```

`shellSort([38, 45, 35, 8, 13])` має повернути `[8, 13, 35, 38, 45]`.

```js
assert.deepEqual(shellSort([38, 45, 35, 8, 13]), [8, 13, 35, 38, 45]);
```

`shellSort([43, 36, 20, 34, 24])` має повернути `[20, 24, 34, 36, 43]`.

```js
assert.deepEqual(shellSort([43, 36, 20, 34, 24]), [20, 24, 34, 36, 43]);
```

`shellSort([12, 33, 26, 18, 1, 16, 38])` має повернути `[1, 12, 16, 18, 26, 33, 38]`.

```js
assert.deepEqual(shellSort([12, 33, 26, 18, 1, 16, 38]), [
  1,
  12,
  16,
  18,
  26,
  33,
  38
]);
```

`shellSort([3, 39, 48, 16, 1, 4, 29])` має повернути `[1, 3, 4, 16, 29, 39, 48]`.

```js
assert.deepEqual(shellSort([3, 39, 48, 16, 1, 4, 29]), [
  1,
  3,
  4,
  16,
  29,
  39,
  48
]);
```

# --seed--

## --seed-contents--

```js
function shellSort(a) {

}
```

# --solutions--

```js
function shellSort(a) {
  for (var h = a.length; h > 0; h = parseInt(h / 2)) {
    for (var i = h; i < a.length; i++) {
      var k = a[i];
      for (var j = i; j >= h && k < a[j - h]; j -= h) a[j] = a[j - h];
      a[j] = k;
    }
  }
  return a;
}
```
