선택정렬(Selection Sort)

• 선택정렬은 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법이다.
• O(N^2)로 비효율적인 정렬 알고리즘이지만, 데이터의 갯수가 적고, 빠르게 작성할 수 있기 때문에 알고 있으면 좋다.

동작 원리

• 각 단계에서 가장 작은 원소를 선택한다.
• 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치를 교체한다.

동작 예시

[2, 4, 3, 1, 9, 6, 8, 7, 5] 배열이 있다고 가정해보자

[1단계] 가장 작은 원소인 1을 선택해 아래와 같은 배열을 만든다.

[1, 4, 3, 2, 9, 6, 8, 7, 5]

[2단계] 그 다음 작은 원소인 2를 선택해 아래와 같은 배열을 만든다.

[1, 2, 3, 4, 9, 6, 8, 7, 5]

[3단계] 

[1, 2, 3, 4, 9, 6, 8, 7, 5]

[4단계]

[1, 2, 3, 4, 9, 6, 8, 7, 5]


[5단계]

[1, 2, 3, 4, 5, 6, 8, 7, 9]

[6단계]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

[7단계]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

[8단계]

[1, 2, 3, 4, 5, 6, 7, 8, 9]

코드 예시

function selectionSort(arr) {
	for (let i = 0; i < arr.length; i++) {
      let minIndex = i;
      for (let j = i+1; j < arr.length; j++) {
        if(arr[minIndex] > arr[j]) {
          minIndex = j;
        }
      }
      // swap
      let temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
}

버블정렬 (Bubble Sort)

• 인접한 두개의 원소를 확인해서, 정렬이 되어 있지 않다면 위치를 서로 바꿔준다.
• O(N^2)으로 비효율적인 알고리즘이다.

동작 원리

• 서로 인접한 두 개의 원소를 비교해서, 필요하다면 위치를 서로 바꾸어준다.
• 한번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동한다.
• 하나의 단계를 거칠 때마다 가장 큰 값을 확실하게 결정한다.

동작 예시

[9, 8, 2, 4, 3] // 정렬할 배열

[1단계]
[8, 9, 2, 4, 3] -> [8, 2, 9, 4, 3] -> [8, 2, 4, 9, 3] -> [8, 2, 4, 3, 9]

[2단계]
[2, 8, 4, 3, 9] -> [2, 4, 8, 3, 9] -> [2, 4, 3, 8, 9]

[3단계] 
[2, 3, 4, 8, 9]

[4단계]
[2, 3, 4, 8, 9]

[5단계]
[2, 3, 4, 8, 9]

코드 예시

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

삽입 정렬(Insertion Sort)

• 삽입 정렬이란, 말 그대로 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다.
• 이미 정렬이 완료되어 있는 경우 동작이 매우 빠르다.

동작 원리

• 각 단계마다 원소가 삽입될 적절한 위치를 찾는다.
• 적절한 위치에 도달할 때까지 반복적으로 왼쪽으로 이동한다.
• 최악의 경우 O(N^2)의 복잡도를 갖는다.

동작 예시

[2, 4, 3, 1, 9, 6, 8, 7, 5] // 정렬할 배열, 첫번째 원소는 정렬이 되어 있다고 가정한다.

[1단계]
[2, 4, 3, 1, 9, 6, 8, 7, 5]

[2단계]
[2, 3, 4, 1, 9, 6, 8, 7, 5]

[3단계]
[1, 2, 3, 4, 9, 6, 8, 7, 5]

[4단계]
[1, 2, 3, 4, 9, 6, 8, 7, 5]

[5단계]
[1, 2, 3, 4, 6, 9, 8, 7, 5]

[6단계]
[1, 2, 3, 4, 6, 8, 9, 7, 5]

[7단계]
[1, 2, 3, 4, 6, 7, 8, 9, 5]

[8단계]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

코드 예시

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