정렬 알고리즘

버블 정렬

버블 정렬은 1) 인접한 두 개의 요소를 비교하며 2) j 인덱스의 요소가 j+1 인덱스의 요소보다 클 경우 3) 두 요소의 위치를 바꿔주는 방식으로 진행된다.

바깥의 for 반복문이 한 번 동작하면 인덱스의 마지막에 배열의 가장 큰 요소가 도착했다는 의미이므로, 안쪽의 for 반복문은 매번 n-1-i 번만큼만 동작하게 된다.

function solution(arr) {
  const n = arr.length;

  for (i=0; i<n-1; i++) {
    for (j=0; j<n-1-i; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  
  return arr;
}

 

선택 정렬

선택 정렬은 각 인덱스를 훑으면서 '배열의 최솟값이 어떤 인덱스에 위치해있는가'를 찾는다. 그리고 찾은 요소를 배열의 i 인덱스에 위치한 요소와 갈아끼운다.

바깥의 for 반복문이 한 번 동작하면 0번 인덱스에 배열의 가장 작은 요소가 오게 된다. 따라서 안쪽 for 반복문은 매번 j=i+1으로 초기화된다.

function solution(arr) {
  const n = arr.length;

  for (i=0; i<n; i++) {
    let idx = i;

    for (j=i+1; j<n; j++) {
      if (arr[j] < arr[idx]) idx = j;
    }
    
    [arr[i], arr[idx]] = [arr[idx], arr[i]];
  }

  return arr;
}

 

삽입 정렬

삽입 정렬은 1) 특정 인덱스보다 낮은 인덱스에 위치한 요소가 2) 특정 인덱스에 존재하는 요소보다 클 경우 3) 낮은 인덱스에 위치한 요소를 높은 인덱스로 한 칸 끌어올리는 방식으로 정렬을 진행한다. 만약 4) 낮은 인덱스에 위치한 요소가 특정 인덱스에 존재하는 요소보다 작을 경우 5) 그 즉시 해당 반복 동작이 멈춰버린다는 특징이 있다.

앞서 살펴본 다른 정렬들의 바깥 for 반복문이 0부터 시작했던 것과 달리 삽입 정렬에서는 1부터 시작한다. 그리고 안쪽의 for 반복문은 하나씩 줄어들며 더 낮은 인덱스를 향해 나아간다.

function solution(arr) {
  const n = arr.length;

  for (i=1; i<n; i++) {
    let temp = arr[i];
    let j;

    for (j = i - 1; j >= 0; j--) {
      if (arr[j] > temp) arr[j + 1] = arr[j];
      else break;
    }

    arr[j + 1] = temp;
  }
  
  return arr;
}

 

한 줄 요약

• 버블 정렬 : 내부 반복문이 n-i-1번 인덱스를 향해 이동하며 해당 인덱스와 인접한 다음 인덱스의 요소를 비교하고, 해당 인덱스의 요소가 더 크면 인접한 인덱스의 요소와 교체한다. 큰 숫자를 마지막 인덱스에 가져다 놓는 방식
• 선택 정렬 : 내부 반복문이 마지막 인덱스를 향해 이동하며 가장 작은 숫자를 기록(idx)해놓고, 인덱스의 끝에 도달하면 기록한 숫자를 외부 반복문이 가리키는 인덱스와 교체한다.
• 삽입 정렬 : 내부 반복문이 0번 인덱스를 향해 이동하며 외부 반복문이 가리키는 요소(temp)보다 작은지를 확인하고, 작다면 즉시 내부 반복문을 중지하고 내부 반복문이 마지막으로 확인한 요소(j)의 뒤에 temp를 배치한다.