[JS]_daily coding #24

seul·2022년 6월 27일

Algorithm

목록 보기

23/31

코플릿 데일리 코딩 03_bubbleSort

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다.

버블 정렬 알고리즘은 아래와 같습니다.

첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
1~3의 과정을 첫 요소부터 다시 반복합니다.
5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
1~3의 과정을 총 n번(배열의 크기) 반복합니다.
이 모습이 마치 '거품이 밀려 올라가는 것과 같은 모습'과 같아서 bubble sort라고 부릅니다.

첫번째 수도코드

변수 i를 통해 배열의 크기만큼 반복하는 반복문 선언
반복문 내부에서 변수 j를 통해서 배열 크기만큼 반복하는 반복문을 선언한다.
중첩된 반복문 안에서 arr[j와 arr[j+1]를 비교하고 arr[j]가 더 큰 경우에는 두 요소의 위치를 swap 한다.
정렬된 배열을 반환한다.

첫번째 코드

일단, advanced 힌트는 무시하고 문제에서 주어진 설명에 충실해서 코드를 작성했다. 테스트를 돌려보니, 실행시간을 초과했다는 결과가 나왔다. 불필요한 반복이 있는지 콘솔창에 확인해봤다.

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

일단, 내부 반복문 마지막에서 이미 정렬된 배열의 마지막 요소(가장 큰 요소임)와 undefined를 비교하고 있었다.
그리고 i를 기준으로 반복하는 큰 반복문은 한번 반복을 모두 마치면 마지막 요소가 정렬을 마친 상태이기 때문에 다음번 반복에서는 반복횟수를 줄여도 된다. (이미 정렬된 상태인데 비교를 할 필요가 없기 때문에)
[5,4,3,2,1] 배열(배열의 길이 5)은 처음 반복에서는 4번의 반복(비교)을 하면 가장 큰 요소가 맨 마지막에 위치하게 되고, 두번째 반복에서는 3번의 비교, 세번째 반복에서는 2번, 4번째 반복에서는 1번의 비교만 하면 원하는 결과를 얻을 수 있다.

두번째 수도코드

내부의 반복문은 반복문 길이에서 1을 뺀만큼 반복하면 되기때문에 i를 반복문의 길이로 초기화하고 1씩 감소하면서 반복하도록 바꿔줬다.
j는 0으로 초기화하고 i -1번씩 반복하도록 해줬다.

두번째 코드

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

불필요한 반복은 줄였지만, 여전히 테스트를 통과하지 못했다. 제시된 Advanced 힌트는 다음과 같았다.

아래의 힌트를 바탕으로 (최선의 경우) 수행 시간을 단축할 수 있도록 코드를 수정해보세요.

위에서 설명된 알고리즘 1~3의 과정 중 어떤 요소도 위치가 바뀌지 않은 경우, 배열이 정렬된 상태라는 것을 알 수 있습니다.

배열이 정렬된 (최선의)경우라면 swap 과정을 거칠 필요가 없다.

지금은 배열길이 5짜리 예시지만 테스트처럼 최대길이 1000, 80000인 배열이 들어올 경우에는 엄청난 비효율인 것이다. 반복문 내부에서 swap이 한번도 안이루어진 경우라면 이미 입력된 배열은 정렬을 끝마친 상태라는 의미이므로, 다음번 i 반복은 불필요하다.

세번째 수도코드

swap이 이루어졌을때를 boolean값으로 기록할 수 있는 변수 noSwaps를 선언해준다.
내부 반복문에서 swap이 이루어지지 않은 경우에는 큰 반복문을 빠져나오도록 한다. break
noSwaps에 true를 할당하고 내부 반복문에서 swap이 이루어진 경우에는 이 값을 false로 재할당한다.

세번째 코드

const bubbleSort = function (arr) {
  let noSwaps;
  for (let i = arr.length ; i >0 ; i--) {
    noSwaps = true;
    for(let j = 0; j < i-1; j++) {
      //console.log(i, noSwaps, arr, arr[j], arr[j+1])
      if(arr[j] > arr[j + 1]) {
        let temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
        noSwaps = false
      }
    }
    if(noSwaps) break;
  }
  return arr
};