---
id: 8d5123c8c441eddfaeb5bdef
title: Реалізуйте сортування бульбашкою
challengeType: 1
forumTopicId: 301612
dashedName: implement-bubble-sort
---

# --description--

Це перше із декількох завдань, які стосуються алгоритмів сортування. Нам надано масив несортованих елементів, і нам потрібно повернути впорядкований масив. Ми побачимо кілька різних методів для цього і вивчимо певні компроміси між цими різними підходами. Хоча більшість сучасних мов мають вбудовані методи сортування для таких операцій, все ж важливо зрозуміти деякі загальні підходи та дізнатися, як їх можна реалізувати.

Зараз ми розглянемо сортування бульбашкою. Метод сортування бульбашкою починається на початку несортованого масиву та перекидає несортовані значення в кінець, повторюючи масив, доки він не буде повністю відсортований. Це робиться шляхом порівняння суміжних елементів і їх заміни місцями, якщо вони не відповідають критеріям. Метод продовжує цикл, поки не відбудеться заміна місць та масив буде відсортовано.

Цей метод вимагає декількох ітерацій через масив, а в типових та найгірших ситуаціях має квадратичну часову складність. Простими словами, цей метод непрактичний у більшості випадків.

**Інструкція:** напишіть функцію `bubbleSort`, яка приймає масив цілих чисел як ввід та повертає масив цих цілих чисел у відсортованому порядку (від найменшого до найбільшого).

# --hints--

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

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

`bubbleSort` має повернути впорядкований масив (від найменшого до найбільшого).

```js
assert(
  isSorted(
    bubbleSort([
      1,
      4,
      2,
      8,
      345,
      123,
      43,
      32,
      5643,
      63,
      123,
      43,
      2,
      55,
      1,
      234,
      92
    ])
  )
);
```

`bubbleSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92])` має повернути масив без змін, окрім послідовності.

```js
assert.sameMembers(
  bubbleSort([
    1,
    4,
    2,
    8,
    345,
    123,
    43,
    32,
    5643,
    63,
    123,
    43,
    2,
    55,
    1,
    234,
    92
  ]),
  [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]
);
```

`bubbleSort` не має використовувати вбудований метод `.sort()`.

```js
assert(isBuiltInSortUsed());
```

# --seed--

## --after-user-code--

```js
function isSorted(a){
  for(let i = 0; i < a.length - 1; i++)
    if(a[i] > a[i + 1])
      return false;
  return true;
}

function isBuiltInSortUsed(){
  let sortUsed = false;
  Array.prototype.sort = () => sortUsed = true;
  bubbleSort([0, 1]);
  return !sortUsed;
}
```

## --seed-contents--

```js
function bubbleSort(array) {
  // Only change code below this line
  return array;
  // Only change code above this line
}
```

# --solutions--

```js
function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    let swapped = false;
    for (let j = 1; j < array.length; j++) {
      if (array[j - 1] > array[j]) {
        let temp = array[j-1];
        array[j-1] =  array[j];
        array[j] = temp;
        swapped = true;
      }
    }
    if (swapped === false) {
      break;
    }
  }
  return array;
}
```
