알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 6. 정렬 - 개념

  • 0
  • 0
0
0

1. 기준에 따라 데이터를 정렬

A. 정렬 알고리즘 개요

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것.

데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 가장 많이 사용되는 알고리즘 중 하나다. 정렬하면 이진 탐색(Binary Search)이 가능해진다.

정렬부터 공부하면 알고리즘의 효율성을 쉽게 이해할 수 있다. 문제에서 요구하는 조건에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 정렬 알고리즘을 공부하다보면 자연스럽게 알고리즘 효율의 중요성을 깨닫는다.

컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없기에, 정렬을 수행하는 과정을 소스코드로 작성하여 구체적으로 명시해야 한다.

앞으로의 예제는 모두 오름차순 정렬을 수행한다고 가정한다. 내림차순 정렬은 오름차순 정렬을 수행하는 알고리즘에서 크기 비교를 반대로 수행하면 된다. 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드를 제공한다. 내림차순 정렬은 오름차순 정렬을 수행한 뒤에 그 결과를 뒤집기하여 만들 수 있다. 리스트를 뒤집는 연산은 O(N)의 복잡도를 가진다.

정렬 알고리즘에서는 흔히 데이터의 개수를 N이라 표현한다.

2. 선택 정렬 (Selection Sort)

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복

가장 작은 것을 선택한다는 의미에서 선택 정렬(Selection Sort) 알고리즘이다.

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

선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N - 1번 반복한다.

A. 소스코드


array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]  
  
for i in range(len(array)):  
    min_index = i  
    for j in range(i+1, len(array)):  
        if array[min_index] > array[j]:  
            min_index = j  
    array[i], array[min_index] = array[min_index], array[i]  
  
    print(array)
    

B. 시간 복잡도

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

O(N^2)

선택 정렬을 이용하는 경우 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려지는 것을 확인할 수 있다. 파이썬에 내장된 기본 정렬 라이브러리는 내부적으로 C언어 기반이며, 다양한 최적화 테크닉이 포함되어 있어 더욱 빠르게 동작한다.

다른 알고리즘에 비해 매우 비효율적이다.

다만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서는 잦으므로 선택 정렬 형태에 익숙해질 필요가 있다.

3. 삽입 정렬 (Insertion Sort)

특정한 데이터를 적절한 위치에 삽입한다.

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

선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘.

특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.

삽입 정렬은 두 번째 데이터부터 시작한다. 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

정렬이 이루어진 원소는 항상 오름차순을 유지한다. 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 된다.

A. 소스코드


array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]  
  
for i in range(1, len(array)):  
    for j in range(i, 0, -1):  
        if array[j] < array[j-1]:  
            array[j], array[j-1] = array[j-1], array[j]  
        else:  
            break  
  
print(array)

B. 시간 복잡도

O(N^2)

삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

최선의 경우 O(N).

보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다.

4. 퀵 정렬 (Quick Sort)

기준 데이터를 정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸자.

가장 많이 사용되는 알고리즘.

퀵 정렬과 비교할 만큼 빠른 알고리즘인 병합 정렬 알고리즘은 대부분 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.

기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준 데이터를 피벗(pivot)이라 한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다.

여기서는 가장 대표적인 분할 방식인 호어 분할 방식을 사용한다. 호어 분할 방식은 리스트에서 첫 번째 데이터를 피벗으로 정한다.

피벗을 설정한 뒤 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그리고 큰 데이터와 작은 데이터의 위치를 서로 교환한다. 이를 반복한다.

왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 경우 작은 데이터와 피벗의 위치를 서로 변경한다.

피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 분할(Divide) 또는 파티션(Partition)이라 한다.

각 파티션에 피벗을 설정하여 정렬이 완료될 떄까지 반복한다.

퀵 정렬은 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다. 재귀 함수와 동작 원리가 같다. 종료 조건은 현재 리스트의 데이터 개수가 1개인 경우이다. 리스트의 원소가 1개라면, 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능하다.

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

A. 소스 코드

a. 정상

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]  
  
def quick_sort(array, start, end):  
    if start >= end:  
        return  
    pivot = start  
    left = start + 1  
    right = end  
  
    while left <= right:  
        while left <= end and array[left] <= array[pivot]:  
            left += 1  
        while right > start and array[right] >= array[pivot]:  
            right -= 1  
        if left > right:  
            array[right], array[pivot] = array[pivot], array[right]  
        else:  
            array[left], array[right] = array[right], array[left]  
    quick_sort(array, start, right - 1)  
    quick_sort(array, right + 1, end)  
  
quick_sort(array, 0, len(array) - 1)  
print(array)

b. 파이써닉한 코드

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]  
  
def Quick_sort(array):  
    if len(array) <= 1:  
        return array  
  
    pivot_data = array[0]  
    tail = array[1:]  
  
    left_list = [x for x in tail if x <= pivot_data]  
    right_list = [x for x in tail if x > pivot_data]  
  
    return Quick_sort(left_list) + [pivot_data] + Quick_sort(right_list)  
  
quick = Quick_sort(array)  
  
print(quick)

B. 시간 복잡도

평균 시간 복잡도는 O(NlogN)

최악의 경우 O(N^2)

데이터의 개수가 N개일 때 높이는 약 logN이다.

컴퓨터 과학에서 log의 의미는 밑이 2인 로그를 의미한다. log_2N

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

5. 계수 정렬 (Count Sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.

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

모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언한다.

계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다.

데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬은 사용할 수 없다.

가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000이면 총 1,000,001개의 수가 존재한다.

직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다.

계수 정렬은 데이터의 크기가 제한되어 있을 때에 한해서 데이터의 개수가 매우 많더라도 빠르게 동작한다.

가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 가장 큰 데이터가 '9'이고 가장 작은 데이터가 '0'이다. 따라서 정렬할 데이터의 범위는 0부터 9까지이므로 리스트의 인덱스가 모든 범위를 포함할 수 있도록 한다. 크기가 10인 리스트의 모든 데이터가 0이 되도록 초기화한다.

그리고 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

정렬된 결과는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력한다.

A. 소스 코드

a. 책에 나온 예시

array = [7, 5, 6, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2, 99, 150]  
  
count = [0] * (max(array) + 1)  
  
for i in array:  
    count[i] = count[i] + 1  
  
print("count = ", count)  
  
print("sorted = ", end='')  
for j in range(len(count)):  
    for k in range(count[j]):  
        print(j, end=' ')
        

count =  [2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

sorted = 0 0 1 1 2 2 3 4 5 5 6 6 7 8 9 99 150 

b. 내가 생각한 코드

아래 공간 복잡도 문제를 제시하길래, "어? 그럼 딕셔너리를 사용하면 공간 복잡도 문제는 해결되는 것 아닌가?"하면서 코드를 작성했다.

아.. 이러면 sorted 함수를 사용하니까 공간 복잡도는 해결해도 시간 복잡도는 증가하겠구나..


array = [7, 5, 6, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2, 99, 150]  
  
count = dict()  
  
for i in array:  
    if i in count:  
        count[i] = count[i] + 1  
 else:  
        count[i] = 1  
  
count = sorted(count.items(), key=lambda x:x[0])  
  
print("count = ", count)  
  
print("sorted = ", end='')  
for i_key, i_value in count:  
    for j in range(i_value):  
        print(i_key, end=' ')


count =  [(0, 2), (1, 2), (2, 2), (3, 1), (4, 1), (5, 2), (6, 2), (7, 1), (8, 1), (9, 1), (99, 1), (150, 1)]
sorted = 0 0 1 1 2 2 3 4 5 5 6 6 7 8 9 99 150 

B. 시간 복잡도

계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행한다.

기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다. 기수 정렬은 계수 정렬에 비해서 동작은 느리지만, 처리할 수 있는 정수의 크기는 더 크다.

C. 공간 복잡도

계수 정렬은 때에 따라 심각한 비효율성을 초래할 수 있다. 데이터가 0과 999,999 단, 2개만 존재하는 경우 리스트의 크기가 100만 개가 되도록 선언해야 한다.

따라서 항상 사용할 수 있는 알고리즘은 아니고, 동일한 값을 가지는 데이터가 여러 개 등장했을 때 적합하다.

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

코테 시스템 환경에서는 메모리 공간상의 제약과 입출력 시간 문제로 인하여 입력되는 데이터의 개수를 1,000만 개 이상으로 설정할 수 없는 경우가 많기 때문에, 정렬 문제에서의 데이터 개수는 1,000만 개 미만으로 출제될 것이다.

6. 파이썬 정렬 라이브러리

정렬 알고리즘 문제는 어느 정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제라고 할 수 있다.

파이썬은 sorted() 함수를 제공한다. sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다. 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.

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

리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수도 있다. 리스트 객체의 내장 함수인 sort() 를 이용하는 것이다. 이 함수는 값을 반환하지 않고 리스트 내부 원소가 바로 정렬된다.

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

A. 소스 코드

a. sorted()

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]  
  
result = sorted(array)  
print(result)

b. sort()

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]  
  
array.sort()  
print(array)

c. key 매개변수 사용

array = [('바나나', 2), ('사과', 5), ('당근', 3)]  
  
def setting(data):  
    return data[1]  
  
result = sorted(array, key=setting)  
print(result)

B. 시간 복잡도

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

7. 결론 및 각 정렬별 사용 예시

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

  1. 정렬 라이브러리로 풀 수 있는 문제
  2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
    • 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알아야 풀 수 있다.
  3. 더 빠른 정렬이 필요한 문제
    • 계수 정렬이나 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 한다.

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.