[코딩 테스트] 9일차: 정렬 알고리즘

정렬 알고리즘

정렬 알고리즘은 데이터를 일정한 순서로 정렬하는 알고리즘입니다. 정렬된 데이터는 검색, 분석 등의 작업에서 효율성을 높여줍니다. 여기서는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬에 대해 알아보겠습니다.

버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 정렬하는 가장 간단한 정렬 알고리즘 중 하나입니다. 시간 복잡도는 O(n^2)입니다.

JavaScript에서의 버블 정렬 구현

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

let arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

Python에서의 버블 정렬 구현

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr)) # [11, 12, 22, 25, 34, 64, 90]

선택 정렬 (Selection Sort)

선택 정렬은 리스트에서 가장 작은 요소를 찾아 맨 앞의 요소와 교환하는 방식으로 정렬합니다. 시간 복잡도는 O(n^2)입니다.

JavaScript에서의 선택 정렬 구현

function selectionSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      // Swap
      let temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

let arr = [64, 25, 12, 22, 11];
console.log(selectionSort(arr)); // [11, 12, 22, 25, 64]

Python에서의 선택 정렬 구현

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

arr = [64, 25, 12, 22, 11]
print(selection_sort(arr)) # [11, 12, 22, 25, 64]

삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 부분의 요소를 하나씩 꺼내어 정렬된 부분에 삽입하는 방식으로 동작합니다. 시간 복잡도는 O(n^2)입니다.

JavaScript에서의 삽입 정렬 구현

function insertionSort(arr) {
  let n = arr.length;
  for (let i = 1; i < n; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
  return arr;
}

let arr = [12, 11, 13, 5, 6];
console.log(insertionSort(arr)); // [5, 6, 11, 12, 13]

Python에서의 삽입 정렬 구현

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

arr = [12, 11, 13, 5, 6]
print(insertion_sort(arr)) # [5, 6, 11, 12, 13]

병합 정렬 (Merge Sort)

병합 정렬은 분할 정복 알고리즘으로, 배열을 절반으로 나누어 각각을 정렬한 후 병합하여 정렬합니다. 시간 복잡도는 O(n log n)입니다.

JavaScript에서의 병합 정렬 구현

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

let arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // [3, 9, 10, 27, 38, 43, 82]

Python에서의 병합 정렬 구현

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1

    result.extend(left[left_index:])
    result.extend(right[right_index:])
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr)) # [3, 9, 10, 27, 38, 43, 82]

퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복 알고리즘으로, 피벗을 선택하여 배열을 분할하고, 각 부분을 정렬하여 병합합니다. 시간 복잡도는 평균 O(n log n)입니다.

JavaScript에서의 퀵 정렬 구현

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

let arr = [10, 7, 8, 9, 1, 5];
console.log(quickSort(arr)); // [1, 5, 7, 8, 9, 10]

Python에서의 퀵 정렬 구현

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[-1]
    left = []
    right = []

    for x in arr[:-1]:
        if x < pivot:
            left.append

(x)
        else:
            right.append(x)

    return quick_sort(left) + [pivot] + quick_sort(right)

arr = [10, 7, 8, 9, 1, 5]
print(quick_sort(arr)) # [1, 5, 7, 8, 9, 10]

연습 문제

문제 1: K번째 작은 요소 찾기

주어진 배열에서 K번째로 작은 요소를 찾는 프로그램을 작성하세요.

JavaScript

function kthSmallest(arr, k) {
  let sortedArr = quickSort(arr);
  return sortedArr[k - 1];
}

let arr = [12, 3, 5, 7, 19];
let k = 2;
console.log(kthSmallest(arr, k)); // 5

Python

def kth_smallest(arr, k):
    sorted_arr = quick_sort(arr)
    return sorted_arr[k - 1]

arr = [12, 3, 5, 7, 19]
k = 2
print(kth_smallest(arr, k)) # 5

결론

이번 글에서는 코딩 테스트 준비를 위해 정렬 알고리즘에 대해 배웠습니다. 이를 통해 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬의 개념과 구현 방법을 익힐 수 있었습니다. 다음 글에서는 탐색 알고리즘에 대해 알아보겠습니다.

다음 글에서 만나요!