Algorithm #05 - "Bubble Sort"

filoscoderยท2019๋…„ 12์›” 1์ผ
0

Toy Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
5/7
post-thumbnail

๐Ÿ‡บ๐Ÿ‡ธ 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;
};
profile
Never gets bored of making mistakes and wonder why is that

0๊ฐœ์˜ ๋Œ“๊ธ€