정렬 알고리즘 - 버블/선택/삽입/병합

> 버블 정렬 (bubble sort)

• 버블정렬은 두 인접한 원소를 검사하여 정렬하는 방법
• 시간 복잡도는 느리지만 코드가 단순하다
• 배열 전체를 순회하며 비교하기 때문에 시간복잡도는 O(n²)
• 배열 하나만 사용하기 때문에 공간복잡도는 O(n)

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

arr = [4, 3, 8, 5, 2, 1]
print(bubbleSort(arr))  # [1, 2, 3, 4, 5, 8]

 

선택 정렬 (selection sort)

• 배열의 가장 작은 값을 가지는 인덱스를 찾아서 가장 작은 값을 앞에서부터 채워나가면서 정렬하는 방식
• 시간복잡도 O(n²)
• 공간복잡도 O(n)

def selectionSort(arr):
    for i in range(len(arr)):
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[minIndex] > arr[j]:
                minIndex = j
        swap = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = swap
    return arr

 

삽입 정렬 (insertion sort)

• 최소값을 찾아서 이하 배열들의 원소와 비교하여 자신이 위치해야할 곳을 찾아 삽입해나가며 정렬하는 방식이다.
• 시간복잡도 O(n²)
• 공간복잡도는 O(n)

def insertionSort(arr):
    for i in range(1, len(arr)):
        cur = arr[i]
        left = i - 1
        while left >= 0 and arr[left] > cur:
            arr[left + 1] = arr[left]
            left -= 1
        arr[left + 1] = cur
    return arr

 

병합 정렬 (merge sort)

• 배열을 반씩 쪼개서 하나의 원소를 가진 배열로 만든 후 비교를 통해 각 배열을 정렬하여 병합하여 최종 정렬된 배열을 구하는 정렬방식이다.
• 시간복잡도 O(nlogn)
• 공간복잡도 O(n)

function merge(arr1, arr2) {
  let results = [];
  arr1Pointer = 0;
  arr2Pointer = 0;

  while (arr1Pointer < arr1.length && arr2Pointer < arr2.length) {
    if (arr2[arr2Pointer] > arr1[arr1Pointer]) {
      results.push(arr1[arr1Pointer]);
      arr1Pointer++;
    } else {
      results.push(arr2[arr2Pointer]);
      arr2Pointer++;
    }
  }

  // 반복문 두번째
  // 한바퀴 돌았으면, 끝까지 돌 수 있게 남은 애들을 넣어주는 것
  while (arr1Pointer < arr1.length) {
    results.push(arr1[arr1Pointer]);
    arr1Pointer++;
  }
  while (arr2Pointer < arr2.length) {
    results.push(arr2[arr2Pointer]);
    arr2Pointer++;
  }

  return results;
}

// ----------------------------------------------------------------------

let arr = [10, 24, 76, 73];

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

mergeSort(arr);