알고리즘 문제풀이 6

버블정렬에 관련된 알고리즘 문제이다.
버블정렬은 삽입정렬 알고리즘을 풀 때 등장했던 개념으로,
나는 삽입정렬 문제를 풀 때, 버블정렬과 개념에 혼동이 와서 제대로 풀지 못했던 기억이 난다.
삽입정렬 알고리즘 문제

버블 정렬이란?

버블 즉 거품의 모양처럼, 요소들의 크기 비교 후 볼록볼록하게 이동한다고 해서 버블정렬이라고 부르는 듯하다.
버블정렬에 대한 설명(참고 블로그)
위의 블로그를 참고하면, 결국 버블 정렬은 크게 순회할 때마다,
크기 비교하면서 가장 큰 수를 뒤로 보내는 작업을 하는 정렬 작업 인 것이다.

내가 삽입정렬 때, 삽입정렬이라 착각했던 풀이로직+두번째 순회(실제로 크기 비교할 때) 순회 종료 조건을 좀 더 효율적으로 바꾼다면 버블 정렬이라고 볼 수 있다.

const bubbleSort = function(array) {
  for(let i=0; i<array.length-1; i++){
    //여기서 변수 i는 실행 횟수를 의미한다. 
    //횟수는 배열 마지막 요소-1 만큼, 왜냐면 끝에서 두번째까지 크기 비교를 다하고 나면 
    //sort가 완료된 상황이므로 마지막 요소 횟수까지 점검 안해줘도 된다.
    for(let j=0; j<array.length-1-i; j++){ 
      //실제로 배열내의 요소를 도는 반복문은 여기다.
      //반복문을 도는 횟수를 의미하는 j에 대해, 반복을 진행하는 횟수가 늘어날수록 요소 반복은 적게 해도 된다.
      //한 번 실행 할수록 뒤에 있는 요소들은 이미 정렬이 완료되었기 때문이다. 
      if(array[j]>array[j+1]){ //뒤의 요소가 앞의 요소보다 작으면
        let small = array[j+1]; // 작은 요소를 임의의 변수를 정의하여 할당해주고(따로 빼주기)
        let big = array[j]; // 큰요소도 임의의 변수를 정의하여 할당해준다
        array[j+1] = big; // 그리고 큰요소와 작은요소의 자리를 바꿔준다.
        array[j] = small;
      }
    }
  }
  return array
};

버블정렬의 시간 복잡도와 효율성

버블정렬은 코드상으로는 매우 단순하고 이해하기 쉽다.
하지만 효율적인 측면에서 보자면, 반복문이 두 번이나 반복되므로 n^2의 효율성을 가지고 있고 ,
run-time도 실제로 정렬들 중에서 가장 오래 걸린다.