Javascript # 알고리즘

📝오늘 배운 내용

오늘은 여러 정렬 알고리즘중 가장 기본적인 알고리즘인 버블 정렬 문제를 풀어보았다.
버블정렬은 아래와 같은 방법으로 배열을 오름차순으로 정렬하는 방법이다.
이러한 모습이 마치 거품이 밀려 올라가는 것과 같은 모습이라 bubble sort라고 부른다.

1. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
2. 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
3. 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
4. 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
5. 1~3의 과정을 첫 요소부터 다시 반복합니다.
6. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
7. 1~3의 과정을 총 n번(배열의 크기) 반복합니다.

• 입출력 예시

let output = bubbleSort([2, 1, 3]);
console.log(output); // --> [1, 2, 3]

arr가 [2, 1, 3] number타입의 요소를 가지는 배열이라면 [1, 2, 3]과 같은 결과 값을 출력하는 함수를 구해야 한다.
먼저 arr의 요소들을 반복적으로 비교해서 더 작은 숫자가 맨 앞에 위치하도록 바꿔줘야한다. 이중 for문을 만들어줘서 우선 첫 번째 요소와 그 다음 요소를 비교해 첫 번째 요소가 더 크다면 첫 번째 요소를 임시 변수에 넣어놓고 그 자리에 두 번째 요소를 넣어준다. 그리고 다시 첫 번째 요소를 두 번째 요소 자리에 넣어준다. 이런식으로 arr의 길이만큼 반복해서 넣어준다.

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

위와 같은 코드도 정답이 될 수 있지만 만약 수행 시간을 단축 시켜야 한다면 어떻게 코드를 작성 할 수 있을까.
예를 들어, 첫 번째 요소부터 다음 요소들을 비교하는데 위치를 바꿀 필요가 없다면 이미 정렬이 되어있는 숫자이기 때문이다. 그렇다면 이미 정렬이 되어있는 숫자는 비교하지 않고 넘어가게 코드를 작성 할 수 있을까?

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

여기서 temp에 값이 있다는 의미는 arr[j] > arr[j + 1]이라는 조건이 성립했기 때문이다. 그렇다면 우리는 temp에 값이 없을 때 반복문을 빠져나오게 만들어주면 더 이상 정렬하지 않아도 된다는 의미가 된다.