[JS알고리즘] 선택 정렬, 버블 정렬, 삽입 정렬

선택 정렬, 버블 정렬, 삽입 정렬은 시간 복잡도 O(n^2)로 비효율적인 정렬 알고리즘입니다.

선택 정렬

- 선택 정렬은 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법입니다.

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

- 매 단계에서 가장 작은 것을 선택하는 데에 약 N번의 연산이 필요하다.

 

5

4

3

2

1

 

1단계: 첫 단계에서 제일 작은 수는 1입니다. 

1

5

4

3

2

 

2단계: 그 다음 제일 작은 수는 2입니다.

1

2

5

4

3

 

3단계: 그 다음 제일 작은 수는 3입니다.

1

2

3

5

4

 

4단계: 마지막으로 제일 작은 수는 4입니다.

1

2

3

4

5

 

const selectSolution = (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;
    }
    let temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
};

 

버블 정렬

- 단순히 인접한 두 원소를 확인하여, 정렬이 안 되어 있다면 위치를 서로 변경한다. 

- 각 단계에서는 인접한 두 개의 원소를 비교하여, 필요시 위치를 변경한다.

- 비교해서 나온 마지막 정렬을 고정하고, 다시 비교하여 정렬한다.

 

[단계 별]

 0의 자리와 1의 자리를 비교한다.0의자리가 작아서 고정한다.

5

8

2

4

 

 1과 2의 자리를 비교한다. 2의 자리가 작아서 자리를 변경해준다.

5

2

8

4

 

2과 3의 자리를 비교한다. 3의 자리가 더 작아서 자리를 변경해준다.

5

2

4

8

 

이 방법을 반복하여 변경해준다.

 

const bubbleSolution = (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;
      }
    }
  }
  return arr;
};
let list = [8, 2, 3, 4];

console.log(bubbleSolution(list));

 

삽입 정렬

- 각 단계에서 현재 원소가 삽입될 위치를 찾는다.

- 적절한 위치에 도달 할 때까지 반복적으로 왼쪽으로 이동한다.

2

3

1

5

6

 

[1단계] 첫번째는 정렬되었다고 판단하고, 3이 2보다 크기 때문에 그대로 정렬된다.

2

3

1

5

6

 

[2단계] 1이 2,3보다 작기 때문에 맨 앞으로 정렬된다.

1

2

3

5

6

 

[3단계] 5가 3보다 크기 때문에 그대로 고정한다.

1

2

3

5

6

 

[4단계] 6이 5보다 크기 때문에 그대로 고정한다.

1

2

3

5

6

 

const insertionSort = (arr) => {
  for (let i = 1; 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;
      }
    }
  }

  return arr;
};
let list = [8, 2, 3, 4];

console.log(insertionSort(list));