버블정렬과 삽입정렬

boyeonJ·2023년 5월 22일

알고리즘

목록 보기

5/17

버블정렬

버블정렬이란?

버블 정렬은 인접한 두 개의 요소를 비교하고 필요에 따라 서로 위치를 교환하는 방식으로 동작합니다.

주어진 배열의 길이를 구합니다.
배열의 첫 번째 요소부터 시작하여 인접한 두 요소를 비교합니다.
현재 요소(arr[i])가 다음 요소(arr[i+1])보다 크다면, 두 요소의 위치를 교환합니다.
이 과정을 배열의 끝까지 반복합니다. 이 단계를 마치면 배열의 마지막 요소는 가장 큰 요소가 됩니다. (1회전)
2부터 4단계까지를 (배열의 길이 - 1)번 반복합니다. 이를 통해 가장 큰 값이 배열의 끝으로 계속해서 이동합니다.
정렬이 완료될 때까지 2부터 5단계를 반복합니다.

버블정렬의 장단점(시간 복잡도)

버블 정렬은 간단하고 구현하기 쉽지만, 최악의 경우(평균의 경우에도) 에는 시간 복잡도가 O(n^2)이 되어 효율적이지 않습니다. O(n^2)이기 때문에 배열의 크기가 커질수록 성능이 저하됩니다.

예시

데이터: [5, 3, 8, 4, 2]

정렬 과정:
1회전: [3, 5, 4, 2, 8]
2회전: [3, 4, 2, 5, 8]
3회전: [3, 2, 4, 5, 8]
4회전: [2, 3, 4, 5, 8]
//1회전 할떄마다 큰 값들부터 정렬이 된다.

최종 정렬된 배열: [2, 3, 4, 5, 8]

코드(javascript)

function bubbleSort(arr) {
  const length = arr.length;

  for (let i = 0; i < length - 1; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 두 요소의 위치 교환
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

삽입정렬

삽입정렬이란?

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 요소를 정렬된 부분에 삽입하는 방식으로 동작합니다.

주어진 배열의 길이를 구합니다.
배열의 두 번째 요소부터 시작합니다. 현재 요소를 '삽입할 요소'로 선택합니다.
'삽입할 요소'를 이전의 정렬된 부분 배열과 비교하여 올바른 위치에 삽입합니다.

이전의 정렬된 부분 배열은 '삽입할 요소'보다 큰 값들로 구성됩니다.
'삽입할 요소'보다 큰 값이 발견되면, 그 값들을 오른쪽으로 한 칸씩 이동시킵니다.
작은 값이나 배열의 시작에 도달하면, '삽입할 요소'를 해당 위치에 삽입합니다.

2부터 3단계까지를 (배열의 길이 - 1)번 반복합니다. 이를 통해 모든 요소가 올바른 위치에 삽입됩니다.

삽입정렬의 장단점(시간 복잡도)

버블정렬과 동일하다.

예시

데이터: [5, 3, 8, 4, 2]

정렬 과정:
1회전: [3, 5, 8, 4, 2]
2회전: [3, 5, 8, 4, 2]
3회전: [3, 4, 5, 8, 2]
4회전: [2, 3, 4, 5, 8]

최종 정렬된 배열: [2, 3, 4, 5, 8]

코드(javascript)

function insertionSort(arr) {
  const length = arr.length;

  //두번째 요소 부터 시작!
  for (let i = 1; i < length; i++) {
    const key = arr[i];
    let j = i - 1;

    //만약  시작에 도달했거나 더 작은 값을 만나면 stop
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = key;
  }

  return arr;
}