[정렬] 버블정렬

버블정렬은 배열의 한 요소와 그 다음요소의 대소를 비교한뒤 순서를 바꿔주는 정렬알고리즘이다.

 

	[1,3,2,4]	[4,3,2,1]
배열의 첫번째 요소를 두번째 요소와 비교한뒤 첫번째 요소가 크다면 서로 순서를 바꾼다.		첫번째 요소: 4 두번째 요소 :3 [3,4,2,1]
두번째 요소가 크다면 바꾸지 않는다.	첫번째 요소 : 1 두번째 요소 : 3 [1,3,2,4]
두번째 요소는 세번째 요소와 크기를 비교한다. 세번째 요소가 크다면 두번째 요소와 순서를 바꾼다.	두번째요소: 3 세번째요소: 2 [1,2,3,4]	두번째요소: 4 세번째요소: 2 [3,2,4,1]
세번째 요소가 크다면 바꾸지 않는다.
세번째 요소는 네번째 요소와 크기를 비교한다. 네번째 요소가 크다면 세번째 요소와 순서를 바꾼다.		세번째요소: 4 네번째요소: 1 [3,2,1,4]
네번째 요소가 크다면 바꾸지 않는다.	세번째요소: 3 두번째요소: 2 [1,2,3,4]

이렇게 배열의 길이인 4보다 한 번 적은 3번만 돌면 최대값을 구할 수 있다.

 

오른쪽 예시 배열 [3,2,1,4]에서 모든요소가 정렬되려면

마지막을 제외한 나머지 세 요소들을 표처럼 모두 반복해야한다.

즉 배열의 길이보다 하나 적게 반복하면된다.

 

만약 요소3이 버블정렬되어서 [2,1,3,4]이 되었다면

3,4가 고정되었으니

배열의 길이 -1 -1 번

요소 2가 버블정렬되어서 [1,2,3,4]

배열이 길이-1 -1-1 번 반복하면 된다.

 

요소 1은 모두 정렬되고 난 다음 최솟값이 된다.

 

다음은 버블정렬을 사용한 알고리즘 문제를 풀어보자.

const bubbleSort = function (arr) {
  for (let i = 0; i < arr.length-1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[ j + 1]] = [arr[ j + 1], arr[j]];
      }
    }
  }

  return arr;
};

위에서 설명한 바와 같이

각요소를 배열의 길이보다 하나 작은만큼 돌되

현재 요소보다 다음요소보다 크면 위치를 서로 바꿔주면된다.

 

해당 인덱스의 값을 저장하고 바꿔도 되지만

나는 구조분해할당 방법을 사용했다.

 

프로그래머스에서도 다른 사람들의 풀이에서 종종 보였는데

배열의 위치를 서로 바꿀때 유용하게 쓰이는듯 하다.

원래 자리변경만 해줘도 버블정렬인데

코플릿에서 수행시간단축을 요구하는 Advanced 조건이 있었다.

const bubbleSort = function (arr) {
  for (let i = 0; i < arr.length-1; i++) {
    let swap = 0;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap++;
        [arr[j], arr[ j + 1]] = [arr[ j + 1], arr[j]];
      }
    }

    if (swap === 0) {
      break;
    }
  }

  return arr;
};

동기님의 힌트로 교환이 일어났을때

어떤 조건을 일어나게해서

한번도 교환이 안되었을때 바로 배열을 리턴하도록 했다.

 

사실 이부분이 이해가 안가서 chatGPT에게 물어보았다.

뭔가 경우의 수를 계속 생각하니 어차피 요소를 다 돌아야 할 것 같았는데

두번째 반복문에서 아무런 교환이 없었다면

당연하게도 이미 정렬된 배열일 것이다.