Python, Swift로 { 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬 } 구현하기

 

기본 정렬 구현하기

오랜만에 알고리즘을 보며 기본 정렬(버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬)을 구현해봤어요.

알고리즘 풀이를 위해 제가 사용하는 언어인 Python과 iOS 개발을 위해 사용하는 언어인 Swift로 각각 구현했어요.

 

각 정렬의 시간복잡도나 자세한 정렬 알고리즘을 위한 글이 아니라, 단순히 기본 정렬 알고리즘들을 구현하고 싶은 분들을 위해 코드를 공유해요 :)

제가 구현할 때 했던 생각 정도만 설명으로 추가할게요.

 

입력되는 배열이 빈 배열인 상황 등은 고려하지 않은 코드예요.
혹시 빈 배열의 입력이 가능한 상황이라면 추가적인 처리가 필요해요 :)

 

혹시 코드에 미흡한 점이 있거나 더 좋은 코드로 개선 가능한 방향이 있다면 피드백 부탁드려요!

 

버블 정렬(Bubble Sort)

버블 정렬은 말 그대로 물 위에 떠있는 거품 방울들처럼 바로 옆에 있는 요소들을 비교하며 마지막부터 최댓값을 쌓아 나가는 구조로 오름차순 정렬을 해요.

여기서 포인트는 한 번 반복을 할 때 이미 정렬이 되어있다면 더이상 검색을 진행하지 않기 위해 isAscending이라는 장치를 만들었어요.

 

Python

def bubble_sort(unsorted: [int]) -> [int]:
    for end in range(len(unsorted)-1, 0, -1):
        isAscending = True
        for start in range(0, end):
            if unsorted[start] > unsorted[start+1]:
                unsorted[start], unsorted[start+1] = unsorted[start+1], unsorted[start]
                isAscending = False
        if isAscending: return unsorted
    return unsorted

 

Swift

func bubbleSort(unsorted: [Int]) -> [Int] {
    var unsorted = unsorted
    for end in stride(from: unsorted.count-1, through: 0, by: -1) {
      var isAscending = true
      for start in 0...end {
        if unsorted[start] < unsorted[start+1] {
          unsorted.swapAt(start, start+1)
          isAscending = false
        }
      }
      if isAscending { return unsorted }
    }
    return unsorted
  }

 

 

선택 정렬(Selection Sort)

선택 정렬은 0번 인덱스부터 뒤로 탐색하며 자신 이후의 배열 중 최솟값이 자신보다 작으면 swap 하는 형태로 구현해요.

버블 정렬에 비해 Swap이 덜 일어난다는게 좋은 것 같아요.

 

Python

def selection_sort(unsorted: [int]) -> [int]:
    for target in range(0, len(unsorted)-1):
        min_index = unsorted.index(min(unsorted[target+1:]))
        if unsorted[min_index] < unsorted[target]:
            unsorted[target], unsorted[min_index] = unsorted[min_index], unsorted[target]
    return unsorted

 

Swift

func selectionSort(unsorted: [Int]) -> [Int] {
    var unsorted = unsorted
    for start in 0..<unsorted.count-1 {
      var partialMinIndex = start
      for index in start+1..<unsorted.count {
        if unsorted[partialMinIndex] > unsorted[index] {
          partialMinIndex = index
        }
      }
      unsorted.swapAt(start, partialMinIndex)
    }
    return unsorted
  }

 

삽입 정렬(Insertion Sort)

1번 인덱스부터 체크하며 바로 앞부터 시작하여 자신보다 작은 값이 나올 때까지 이동하여 그다음에 위치시키는 정렬이에요.

 

Python

def insertion_sort(unsorted: [int]) -> [int]:
    for target in range(len(unsorted)):
        for index in range(target-1, -1, -1):
            if unsorted[index] > unsorted[index+1]:
                unsorted[index], unsorted[index+1] = unsorted[index+1], unsorted[index]
            else:
                break
    return unsorted

 

Swift

func insertionSort(unsorted: [Int]) -> [Int] {
    var unsorted = unsorted
    for end in 1..<unsorted.count {
      for start in stride(from: end-1, through: 0, by: -1) {
        if unsorted[start] > unsorted[start+1] {
          unsorted.swapAt(start+1, start)
        } else {
          break
        }
      }
    }
  return unsorted
}

 

퀵 정렬(Quick Sort)

피벗(Pivot)이라는 기준점을 만들어 그 피벗보다 작은 값을 피벗 왼쪽에, 큰 값을 오른쪽에 넣으며 정렬시켜요.

단, 아래 구현에서 pivot의 값은 중복되는 경우가 없게 설정했어요.

만약에 중복을 허용하여 구현하고 싶다면 pivot의 개수를 세어 그 개수만큼 넣어주면 될 거라고 생각해요.

그리고 피벗은 0번째 인덱스로 결정했어요.

 

Python

def quick_sort(unsorted: [int]) -> [int]:
    if len(unsorted) < 2:
        return unsorted
    left, right = [], []
    pivot = unsorted[0]
    for element in unsorted:
        if element < pivot:
            left.append(element)
        elif element > pivot:
            right.append(element)
    return quick_sort(left) + [pivot] + quick_sort(right)

 

Swift

func quickSort(unsorted: [Int]) -> [Int] {
  if unsorted.count < 2 { return unsorted }
  let pivot = unsorted[0]
  let left: [Int] = unsorted.filter { $0 < pivot }
  let right: [Int] = unsorted.filter { $0 > pivot }
  return quickSort(unsorted: left) + [pivot] + quickSort(unsorted: right)
}

 

병합 정렬(Merge Sort)

병합 정렬은 나누는 과정과 병합의 과정 두 가지로 구현이 돼요.

나누는 과정은 merge sort라는 메서드로, 병합의 과정은 merge라는 메서드로 구현했어요.

 

Python

def merge_sort(unsorted: [int]) -> [int]:
    if len(unsorted) < 2:
        return unsorted
    center = len(unsorted) // 2
    left = unsorted[:center]
    right = unsorted[center:]
    return merge(merge_sort(left), merge_sort(right))

def merge(left: [int], right: [int]) -> [int]:
    left_index, right_index = 0, 0
    merged = []
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
    merged += left[left_index:] if left_index < len(left) else right[right_index:]
    return merged

 

Swift

func mergeSort(unsorted: [Int]) -> [Int] {
    if unsorted.count <= 1 {
      return unsorted
    }
    let centerIndex = unsorted.count / 2
    let left = Array(unsorted[0..<centerIndex])
    let right = Array(unsorted[centerIndex..<unsorted.count])
    return merge(left: mergeSort(unsorted: left), right: mergeSort(unsorted: right))
}

func merge(left: [Int], right: [Int]) -> [Int] {
    var result: [Int] = []
    var leftIndex = 0
    var rightIndex = 0

    while leftIndex < left.count && rightIndex < right.count {
      if left[leftIndex] < right[rightIndex] {
        result.append(left[leftIndex])
        leftIndex += 1
      } else {
        result.append(right[rightIndex])
        rightIndex += 1
      }
    }

    if leftIndex == left.count {
      result += Array(right[rightIndex..<right.count])
    } else {
      result += Array(left[leftIndex..<left.count])
    }
    return result
}