[이코테] 05. 정렬

---

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다.

---

정렬(Sorting)

연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘

• 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다. 즉, 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다.
• 정렬 알고리즘에는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등이 있고, 파이썬에서 제공하는 기본 정렬 라이브러리를 이용할 수도 있다.
• 아래의 예제는 모두 오름차순 정렬을 수행하고, 내림차순 정렬은 오름차순 정렬 알고리즘에서 크기 비교를 반대로 수행하면 된다.
  • 파이썬에서는 리스트의 원소를 뒤집는 메서드를 제공하기 때문에 오름차순 정렬을 수행한 뒤에 그 결과를 뒤집기(Reverse)하여 내림차순 리스트를 만들 수도 있다.

---

선택 정렬(Selection Sort)

가장 작은 것을 선택해 앞으로 보내는 과정을 반복

1. 정렬된 데이터를 제외한 이후 데이터 중에서 가장 작은 데이터를 선택한다.
2. 처리되지 않은 데이터 중 가장 앞에 있는 데이터와 바꾼다.
3. 1~2 과정을 N-1번 반복하면 마지막 데이터는 가만히 두어도 이미 정렬된 상태이다.

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(arr)):
    # 가장 작은 원소의 인덱스
    min_idx = i

    for j in range(i+1, len(arr)):
        if arr[min_idx] > arr[j]:
            min_idx = j

    arr[i], arr[min_idx] = arr[min_idx], arr[i]

print(arr)

선택 정렬의 시간 복잡도

선택 정렬은 N-1번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위한 비교 연산이 필요하다.

연산 횟수는 N + (N - 1) + ⋯ + 2 ≃ N X (N + 1) / 2 번이고, O(N²)으로 표현할 수 있다.

---

 

삽입 정렬(Insertion Sort)

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입

특정 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.

삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.

1. 첫 번째 데이터는 정렬이 되어있다고 판단하고, 두 번째 데이터부터 어떤 위치로 들어갈지 판단한다.
2. 첫 번째 데이터의 왼쪽 혹은 오른쪽으로 들어가는 두 경우만 존재한다. 이후 데이터가 삽입될 수 있는 위치는 (정렬된 데이터의 수 + 1) 가지이다.
3. 삽입될 데이터보다 작은 데이터를 만나면 그 위치에 삽입한다.
4. 적절한 위치에 삽입하는 과정을 N-1번 반복한다.

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(arr)):
    # 인덱스 i부터 1까지 감소하며 반복
    for j in range(i, 0, -1):
        # 한 칸씩 왼쪽으로 이동
        if arr[j] < arr[j-1]:
            arr[j], arr[j-1] = arr[j-1], arr[j]
        # 작은 데이터를 만나면, 그 위치에 삽입
        else:
            break

print(arr)

삽입 정렬의 시간복잡도

삽입 정렬의 시간 복잡도는 O(N²)이다.

데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 최선의 경우 O(N)의 시간 복잡도를 가진다.

---

 

퀵 정렬(Quick Sort)

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 교환한 후 리스트를 반으로 나누는 방식으로 동작

퀵 정렬은 피벗을 설정하고 리스트를 분할하는 방법에 따라 여러 가지 방식으로 구분한다.

• 피벗(Pivot): 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준

가장 대표적인 분할 방식인 호어 분할(Hoare Partition) 방식

1. 리스트에서 첫 번째 데이터를 피벗으로 정한다.
2. 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
3. 큰 데이터와 작은 데이터의 위치를 서로 교환한다.
4. 두 값이 엇갈린 경우에는 작은 데이터와 피벗의 위치를 서로 변경한다.
5. 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트에서 각각 동일한 방식으로 정렬을 수행한다.
   • 왼쪽 리스트는 피벗보다 작은 데이터가 위치하고, 오른쪽 리스트는 피벗보다 큰 데이터가 위치한다.
   • 이 작업을 분할(divide) 또는 파티션(partition)이라고 한다.
6. 분할된 리스트의 원소가 1개 일 때 정렬이 종료된다.

# 정렬을 수행할 리스트, 시작 인덱스, 끝 인덱스
def quick_sort(arr, start, end):
    # 원소가 1개라면, 종료
    if start >= end:
        return

    # 피벗은 첫 번째 인덱스
    pivot = start
    left = start+1
    right = end

    while 1:
        # 왼쪽에서부터 피벗보다 큰 데이터
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        # 오른쪽에서부터 피벗보다 작은 데이터
        while right > start and arr[right] >= arr[pivot]:
            right -= 1

        # 두 값이 엇갈렸다면, 작은 데이터와 피벗을 교체 후 분할
        if left > right:
            arr[pivot], arr[right] = arr[right], arr[pivot]
            break
        # 엇갈리지 않았다면, 큰 데이터와 작은 데이터를 교체
        else:
            arr[left], arr[right] = arr[right], arr[left]

    # 분할 후 각각 정렬 수행
    quick_sort(arr, start, right-1)
    quick_sort(arr, right+1, end)


quick_sort(arr, 0, len(arr)-1)
print(arr)

파이써닉한 퀵 정렬 소스코드

  arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

  def quick_sort(arr):
      # 원소가 하나 이하이면 종료
      if len(arr) <= 1:
          return arr

      pivot = arr[0]
      tail = arr[1:]

      # 분할된 왼쪽 리스트: 피벗보다 작은 데이터
      left_side = [x for x in tail if x <= pivot]
      # 분할된 오른쪽 리스트: 피벗보다 큰 데이터
      right_side = [x for x in tail if x > pivot]

      # 분할 이후 각각 정렬을 수행하고 전체 리스트 반환
      return quick_sort(left_side) + [pivot] + quick_sort(right_side)

  print(quick_sort(arr))

• 피벗과 테이블을 비교하는 비교 연산 횟수가 증가해 시간 면에서는 조금 비효율적이다.

퀵 정렬의 시간 복잡도

퀵 정렬의 평균 시간 복잡도는 O(NlogN)이지만 최악의 경우에는 O(N²)이다.

리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다.

---

 

계수 정렬(Count Sort)

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다.

일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

계수 정렬은 비교 기반의 정렬 알고리즘이 아니다. 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

1. 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 리스트의 모든 데이터가 0이 되도록 초기화한다.
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
3. 모든 데이터를 확인하면 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다.
4. 정렬된 결과를 확인하려면, 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력한다.

# 모든 원소의 값이 0보다 크거나 같다고 가정
arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

# 모든 범위를 포함하는 리스트 선언
count = [0] * (max(arr) + 1)

for i in range(len(arr)):
    # 각 데이터에 해당하는 인덱스 값 증가
    count[arr[i]] += 1

# 정렬된 리스트에서 등장 횟수만큼 출력
for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=" ")

계수 정렬의 시간 복잡도

모든 데이터가 양의 정수인 상황에서 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N + K)를 보장한다. 따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.

현존하는 정렬 알고리즘 중에서 기수 정렬(Radix sort)과 더불어 가장 빠르다고 할 수 있다.

기수 정렬은 계수 정렬에 비해서 동작은 느리지만, 처리할 수 있는 정수의 크기는 더 크다.
다만 알고리즘 원리나 소스코드는 복잡하다.

계수 정렬의 공간 복잡도

계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며, 항상 사용할 수는 없다. 하지만 정렬해야 하는 데이터의 개수가 매우 많을 때에도 효과적으로 사용할 수 있다.

일반적인 경우에서 퀵 정렬이 평균적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리할 수 있다.

---

 

파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리 sorted() 함수를 제공한다.

sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다.

(병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 O(NlogN)의 시간 복잡도를 보장한다.)

sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아 정렬된 결과를 출력한다. 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다.

리스트 객체의 내장 함수인 sort()는 리스트 내부 원소를 바로 정렬한다.

sorted()나 sort()는 key 매개변수를 입력으로 받을 수 있다. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.

정렬 라이브러리의 시간 복잡도

정렬 라이브러리는 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.

정렬 라이브러리는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 알고리즘을 사용하고 있다.

문제에서 별도의 요구가 없다면 단순 정렬해야 하는 상황에서 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용할 수 있다.

---

 

코딩 테스트에서 정렬 알고리즘이 사용되는 경우

1. 정렬 라이브러리로 풀 수 있는 문재
   • 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리로 어렵지 않게 풀 수 있다.
2. 정렬 알고리즘의 원리에 대해 묻는 문제
   • 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제
   • 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

---