[TIL] 2024/04/09

💜 Key Point

선택정렬, 버블정렬

💜 Today I Learned

[기술면접]

• 선택 정렬
  선택정렬은 처음부터 마지막 데이터까지 차례대로 비교한다.
  1회전을 수행하고 나면 가장 작은 데이터가 맨 앞에 오게 된다.
  • 시간복잡도
    O(n²)

function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
    // i번째 인덱스가 최소값
    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[minIndex] > array[j]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      let swap = array[minIndex];

      array[minIndex] = array[i];

      array[i] = swap;
    }
    console.log(`${i}회전: ${array}`);
  }
  return array;
}

console.log(selectionSort([5, 4, 3, 1, 2]));

• 버블 정렬
  버블 정렬은 서로 인접한 두 원소를 비교하여 교환하는 것이다.
  1회전을 수행하고 나면 가장 큰 데이터가 맨 뒤로 이동하게 된다.
  이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회한다.
  정렬이 안되어있는 경우에 O(n²)이 소요된다.
  • 시간복잡도
    1) Best - O(n)
    2) Worst - O(n²)

function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    let swap;
    for (let j = 0; j < array.length - 1; j++) {
      if (array[j] > array[j + 1]) {
        swap = array[j];
        array[j] = array[j + 1];
        array[j + 1] = swap;
      }
    }
    if (!swap) {
      break;
    }
    console.log(`${i}회전: ${array}`);
  }
  return array;
}

console.log(bubbleSort([5, 4, 3, 2, 1]));