[TIL] 면접 카타 9일차

🧐 정렬을 설명하고 본인이 가장 편한 언어를 사용하여 로직을 구현해 주세요.

선택 정렬(Selection Sort)

선택 정렬은 데이터가 무작위로 있을때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번쨰 데이터와 바꾸는 과정을 반복한다. 이것은 원시적인 방법으로, 늘 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라고 부른다.

function selectionSort(arr) {
  const len = arr.length;
  
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      // Swap elements
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage:
const array = [64, 25, 12, 22, 11];
console.log("Original array:", array); //'Original array:' [ 64, 25, 12, 22, 11 ]
const sortedArray = selectionSort(array);
console.log("Sorted array:", sortedArray); //'Sorted array:' [ 11, 12, 22, 25, 64 ]

 

 

버블 정렬(Bubble Sort)

버블 정렬은 가장 간단하고 기본적인 알고리즘 중 하나로, 두 원소를 비교해가며 오름 차순이나 내림 차순으로 정렬을 진행한다.

오름 차순으로 정렬하는 상황에서 더 큰 숫자가 한 번에 하나씩 뒤로 이동하는 방법이다.

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

    // Outer loop for each pass
    for (let i = 0; i < len - 1; i++) {
        // Inner loop for comparisons and swaps
        for (let j = 0; j < len - 1 - i; j++) {
            // Compare adjacent elements and swap if necessary
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }

    return arr;
}

const array = [64, 25, 12, 22, 11];
console.log("Original array:", array); //'Original array:' [ 64, 25, 12, 22, 11 ]
const sortedArray = bubbleSort(array);
console.log("Sorted array:", sortedArray); //'Sorted array:' [ 11, 12, 22, 25, 64 ]