[Algorithm] Bubble Sort 시간 비교

Bubble Sort 는 배열의 가장 왼쪽 혹은 오른쪽에서 시작하여 다음숫자와 크기를 비교하여 큰 것을 가장 끝으로 보내는 정렬 방법이다.

두가지 방법으로 풀어봤는데, 첫번째 풀이는 while 문에서 숫자 교환이 일어났을 때 바뀌는 changed라는 변수를 사용하여, 숫자 교환이 일어나지 않을 때 까지(정렬이 완료 됐을 때 까지) 배열의 처음부터 끝까지 계속 비교하는 방식이다. 두번째 풀이는 for문을 두개를 사용하였다. 한번 배열의 처음부터 끝까지 비교를 하면, 맨 끝의 숫자는 정렬이 완료된 것으로 보고 계속해서 비교하는 횟수를 줄여나가는 방식이다.

정렬되지 않은 10000~1까지의 배열을 정렬하는 데 걸리는 시간을 비교했을 때, 두번째 풀이가 2초 가량 빨랐다. (각각 4.7s, 2.6s)

첫번째 풀이

var bubbleSort = function(array) {
  // Your code here.
  
  let changed = true;
  let temp;
   while(changed){
     changed = false
     for(let i=0 ; i<array.length-1 ; i++){
       if(array[i] > array[i+1]){
         temp = array[i+1];
         array[i+1] = array[i];
         array[i] = temp;
         changed = true;
       }
     }
   } 
  return array;
};

두번째 풀이

var bubbleSort = function(array) {
  // Your code here.
  let changed = true;
  let temp;
  for(let i=0 ; i<array.length-1 ; i++){
    for(let j=0 ; j<array.length-1-i ; j++){
      if(array[j]>array[j+1]){
        temp = array[j+1];
        array[j+1] = array[j];
        array[j] = temp;
      }
    }
  }
  return array;
};