캐나다 IT 코딩 Selection Sort

Selection Sort(선택 정렬)는 배열의 정렬되지 않은 부분에서 반복적으로 최소(혹은 최고) 요소를 선택하고 정렬된 부분의 시작에 배치하는 정렬 알고리즘입니다. 이 과정은 전체 배열이 오름차순 (혹은 내림차순)으로 정렬될 때까지 계속됩니다.

Selection Sort(선택 정렬)의 정의

Selection Sort(선택 정렬)에서 배열은 정렬된 부분과 정렬되지 않은 부분으로 두 개의 하위 배열로 분할됩니다. 초기에는 정렬된 부분은 비어 있고, 정렬되지 않은 부분은 배열의 모든 요소를 포함합니다. 알고리즘은 정렬되지 않은 부분에서 최소 요소(혹은 최고)를 선택하고 정렬되지 않은 부분의 가장 왼쪽 요소와 교환합니다. 이렇게 하면 최소 요소가 정렬된 부분에서 올바른 위치에 배치됩니다. 정렬된 부분의 크기는 하나씩 증가하고, 정렬되지 않은 부분의 크기는 하나씩 감소합니다. 이 과정은 전체 배열이 정렬될 때까지 반복됩니다. 선택 정렬은 배열의 요소 수를 나타내는 n에 대해 O(n^2)의 시간 복잡도를 갖습니다. 

 

Selection Sort 코딩 예제

앞서 설명한 Selection Sort 이론에 대한 코딩 예제를 Python으로 구성해서 보여주고 있습니다

# Finds the smallest value in an array
def findSmallest(arr):
  # Stores the smallest value
  smallest = arr[0]
  # Stores the index of the smallest value
  smallest_index = 0
  for i in range(1, len(arr)):
    if arr[i] < smallest:
      smallest = arr[i]
      smallest_index = i
  return smallest_index

# Sort array
def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      # Finds the smallest element in the array and adds it to the new array
      smallest = findSmallest(arr)
      newArr.append(arr.pop(smallest))
  return newArr

print selectionSort([5, 3, 6, 2, 10])

 

findSmallest 함수는 배열에서 가장 작은 값을 찾아 해당 값의 인덱스를 반환하는 함수입니다. smallest 변수에는 현재까지 찾은 가장 작은 값을 저장하고, smallest_index 변수에는 해당 값의 인덱스를 저장합니다. 반복문을 통해 배열을 순회하며 가장 작은 값을 찾아 인덱스를 업데이트합니다. 이후 smallest_index를 반환합니다. selectionSort 함수는 주어진 배열을 선택 정렬하는 함수입니다. 빈 배열 newArr을 선언하고, 주어진 배열의 길이만큼 반복합니다. findSmallest 함수를 사용하여 배열에서 가장 작은 값을 찾고, 해당 값을 newArr에 추가한 뒤 원래 배열에서는 제거합니다. 이 과정을 반복하여 정렬된 newArr을 반환합니다. 예시로 [5, 3, 6, 2, 10] 배열을 주어진 selectionSort 함수에 입력하면 [2, 3, 5, 6, 10]이 출력됩니다.

 

Selection Sort 작동 기본 이미지

selection sort (선택 정렬) 작동 기본 원리

 

Selection Sort의 장, 단점

장점

• 효율성: O(n^2)의 시간 복잡도를 가지므로 작은 배열이나 부분적으로 정렬된 배열에 효율적입니다.
• 간단함: 직관적인 로직 때문에 이해하기 쉽고 구현하기 쉬운 특징을 가지고 있어 간단한 정렬 작업에 적합합니다.
• 제자리 정렬: 정렬 작업을 수행하기 위해 추가적인 메모리가 필요하지 않으며, 배열 내의 요소를 교환하여 정렬합니다. (참고로 앞선 예제에서는 이해의 편의를 위해 새로운 배열을 만든 후에 추가했습니다)

단점

• 비효율적인 시간 복잡도: 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있습니다. 배열의 크기(n)가 증가함에 따라 비교 및 교환 연산이 증가하기 때문에 큰 배열에는 적합하지 않습니다. 또한, 이미 정렬된 배열에서도 비효율적인 성능을 보입니다.
• 불안정한 정렬: 값이 같은 두 개의 요소를 정렬할 때 순서가 보장되지 않습니다. 따라서 정렬 결과의 순서가 입력 순서와 다를 수 있습니다.
• 교환 연산의 빈도: 각 반복에서 최솟값을 찾아 교환하는 과정을 반복합니다. 이로 인해 교환 연산의 빈도가 높아져 비교적 많은 연산이 필요합니다.
• 최악, 평균, 최선의 경우 모두 O(n^2): 입력 배열의 상태에 관계없이 항상 동일한 시간 복잡도를 가지므로, 최선의 경우에도 비효율적입니다.

코딩 테스트 실제 기출문제 - Selection Sort

캐나다 IT 회사에서 출제된 Selection Sort 관련 실제 기출문제를 소개합니다. Solution을 보시기 전에 반드시 우선 문제 자체를 풀어 보시고 접근하시기 바랍니다.

 

Question 1: Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

 

Example:

Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

 

Solution:

def sortColors(nums):
    n = len(nums)
    left, right = 0, n - 1
    current = 0

    while current <= right:
        if nums[current] == 0:
            nums[left], nums[current] = nums[current], nums[left]
            left += 1
            current += 1
        elif nums[current] == 2:
            nums[right], nums[current] = nums[current], nums[right]
            right -= 1
        else:
            current += 1

    return nums

 

Question 2: Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one duplicate number in nums, return this duplicate number.

 

Example:

Input: nums = [1,3,4,2,2] Output: 2

 

Solution:

def findDuplicate(nums):
    slow = nums[0]
    fast = nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

 

---

 

캐나다 IT 코딩 Binary Search