Algorithm #05 - "Bubble Sort"

🇺🇸 Bubble sort is the most basic sorting algorithm. It works by starting at the first element of an array and comparing it to the second element; if the first element is greater than the second element, it swaps the two. It then compares the second to the third, and the third to the fourth, and so on; in this way, the largest values "bubble" to the end of the array. Once it gets to the end of the array, it starts over and repeats the process until the array is sorted numerically.

Implement a function that takes an array and sorts it using this technique. Don't use JavaScript's built-in sorting function (Array.prototype.sort).

• Advance: Optimization time! During any given pass, if no elements are swapped we can assume the list is sorted and can exit the function early. After this optimization, what is the time complexity of your algorithm? (Big-O)

🇦🇷El Ordenamiento de Burbuja es el algoritmo de alineación más básico de todos. Empieza desde el primer elemento de la lista y comparando el segundo elemento, y si el primer elemento es mayor que el segundo elemento, intercambia los dos elementos. A continuación, se compara el segundo elemento con el tercer elemento, el tercero con el cuarto, asi continuamente el mayor elemento queda al final de la lista. Una vez que se haya completado la lista, se repita el proceso hasta que la lista se ordene numericamente.

Implementa una función que reciba una lista (array) y la ordene utilizando esta tecnica. No utilices la funcion ordenadora de Javascript (Array.prototype.sort).

• Avanzado: Tiempo de optimización! En cualquier paso dado, si no se intercambian elementos, podemos asumir que la lista está ordenada y la función puede terminar antes. ¿Cuál es la complejidad de tiempo del algoritmo después de esta optimización? (Big-O)

🇰🇷 버블 정렬은 가장 기본적인 정렬 알고리즘이다. 배열의 첫 번째 요소에서 시작하여 두 번째 요소와 비교하는 방식으로 작동하며, 첫 번째 요소가 두 번째 요소보다 크면 두 요소를 교환한다. 그런 다음 두 번째 값을 세 번째 값과 비교하고, 세 번째 값과 네 번째 값 등을 배열 끝에 "버블"하는 방식으로 비교한다. 일단 배열이 끝나면, 배열이 오름차순으로 정렬될 때까지 과정을 반복한다.

배열(Array)를 인수로 받고 이 기법을 사용하여 정렬하는 함수를 구현하십시오. JavaScript의 내장된 정렬 함수를 사용하지 마십시오 (Array.prototype.sort).

• Advance: 최적화 시간! 정렬 과정 동안, 만약 어떤 요소도 교환되지 않는다면, 우리는 배열이 정렬되어 있다고 가정할 수 있고, 그 기능을 일찍 종료할 수 있다. 이 최적화 후 알고리즘의 시간 복잡도는 어떤가요? (Big-O)

Example:

// Test
bubbleSort([2, 1, 3]); // output> [1, 2, 3]
bubbleSort([2, 72, 11, 10, 4]); // output> [2, 4, 10, 11, 72]
bubbleSort([21, 22, 23.5, 23.3, -25]); // output> [-25, 22, 23.3, 23.5, 25]
// etc...

• Click here to understand Bubble sort.
• Click here to understand the basics of Big-o notation.

# START [ here ] 🏁

let bubbleSort = function(array) {
  // Your CODE
};

// Test
bubbleSort([2, 1, 3]); // output> [1, 2, 3]
bubbleSort([2, 72, 11, 10, 4]); // output> [2, 4, 10, 11, 72]
bubbleSort([21, 22, 23.5, 23.3, -25]); // output> [-25, 22, 23.3, 23.5, 25]

# Javascript solution 🏆

• Run it on your browser console window (F12) 🖥
• Please feel free to add your preference language solution 👩‍👩‍👧‍👦
• Do your best to complete the problem 🎭
• if you can't beat this the solution is below 😱

Solution 👇

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

SOLUTION #1

let bubbleSort = function(array) {
  // Your CODE
  let count = 0;
  while (count !== array.length) {
    for (let i = 0; i < array.length - 1 - count; i++) {
      let item1 = array[i];
      let item2 = array[i + 1];
      if (item1 > item2) {
        array[i] = item2;
        array[i + 1] = item1;
      }
    }
    count++;
  }
  return array;
};

SOLUTION #2 (using ES6 forEach())

let bubbleSort = function(array) {
  // Your CODE
  let count = 0;
  while (count !== array.length) {
    array.forEach(function(currentValue, index) {
      let nextValue = array[index + 1];
      if (currentValue > array[index + 1]) {
        array[index + 1] = currentValue;
        array[index] = nextValue;
      }
    });
    count++;
  }

  return array;
};