[Sorting] 정렬 알고리즘 정리 + 선택/삽입/퀵/계수 정렬

정렬이란 ?

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

정렬 알고리즘으로 데이터를 정렬하면 다음 장에서 배울 이진 탐색(Binary Search)이 가능해진다. (정렬 알고리즘은 이진 탐색의 전처리 과정)

⇒ 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 다룰 예정

 

선택 정렬(Selection Sort) 알고리즘

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
		# 스와프(Swap)란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업
    array[i],array[min_index] = array[min_index],array[i]


print(array)

선택 정렬은 여러 개의 데이터가 무작위로 있을 때, 전체 데이터에서 매번 가장 작은(또는 가장 큰) 데이터를 선택하여 데이터 간의 위치를 변경하는 과정을 반복하여 데이터를 오름차순(또는 내림차순)으로 정렬할 때 사용

 

이 방법은 가장 원시적인 방법으로 매번 가장 작은 것을 ‘선택’한다는 의미에서 선택 정렬 알고리즘이라고 한다.

 

선택 정렬의 시간 복잡도는 Big-O 표기법으로 O(N^2) 이다. (직관적으로 이해하자면 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문)

 

따라서 선택 정렬은 기본 정렬 라이브러리를 포함해 뒤에서 다룰 알고리즘과 비교했을 때 매우 비효율적이다.

 

다만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦기 때문에 선택 정렬 소스코드에 익숙해질 필요가 있다.

 

삽입 정렬(Insertion Sort)

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

for i in range(1,len(array)): # 두번째 원소(index=1)부터 시작
		#(인덱스 i부터 1까지 감소하며 반복하는 문법)
    for j in range(i,0,-1): # step에 -1이 들어가면 start 인덱스(i)부터 시작해서 end+1 인덱스(1)까지 1씩 감소한다.

        if array[j] < array[j-1]: # 한칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]

        else : # 자신보다 작은 데이터를 만나면 그 위치에서 멈춤
            break
            
print(array)

삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

 

삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다.

 

특히 삽입 정렬은 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.(선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 변경)

 

삽입 정렬은 특정한 데이터를 적절한 위치에 ‘삽입’한다는 의미에서 삽입 정렬이라고 부른다.

 

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

 

정렬되어 있는 데이터 리스트에서 적절한 위치를 찾고, 그 위치에 삽입된다는 점이 특징이다.

 

삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때 지나온 데이터들을 거꾸로 순회하면서 자신보다 큰 데이터일 경우에는 자리를 바꾸고, 삽입될 데이터보다 작은 데이터를 만나면 스와핑을 멈춤으로써 해당 위치에 삽입하면 된다.⭐️⭐️

다시 말해 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬되어 있는 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 조사할 필요 없이 그 자리에 삽입하면 되는 것이다.

 

삽입 정렬의 시간 복잡도는 O(N^2) 이다. 하지만 꼭 기억해야할 내용은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상황에서는 매우 빠르게 동작하고, 이 경우에는 퀵 정렬보다 더 강력하다는 것이다. (최선의 경우 O(N))

 

퀵 정렬(Quick Sort)

분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법 https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

퀵 정렬은 하나의 리스트를 “피벗(pivot)”을 기준으로 두 개의 비 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

 

퀵 정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 병합 정렬(Merge Sort) 알고리즘이 있다.

👉🏻 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 한다.

 

퀵 정렬은 다음의 단계들로 이루어진다.

1. 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀호출 을 이용하여 다시 분할 정복 방법을 적용한다.
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

 

퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다.

 

Pivot을 설정하고 리스트를 분할하는 방법에 따라 여러가지 방식으로 퀵 정렬을 구분하는데, 책에서는 가장 대표적인 분할 방식인 “호어 분할(Hoare Partition)” 방식을 기준으로 퀵 정렬을 설명한다.

⇒ 리스트에서 첫 번째 데이터를 Pivot으로 정한다 !

 

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

 

이러한 과정을 반복하면 피벗에 대하여 정렬이 수행된다.

 

퀵 정렬에서는 이처럼 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다.(5장에서 다루었던 재귀 함수와 동작원리가 같음)

 

실제로 퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다.

 

재귀 함수와 동작 원리가 같다면, 종료 조건도 있어야 할 것이다.

⇒ 현재 리스트의 데이터 개수가 1개인 경우 종료 !

 

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

def quick_sort(array,start,end):
    if start >= end : # 원소가 1개인 경우 종료
        return
    
    pivot = start
    left = start + 1
    right = end

    while left <= right: # 왼쪽과 오른쪽이 엇갈리면 반복문 종료

        while left <= end and array[left] <= array[pivot]: # 피벗보다 큰 데이터를 찾을 때까지 인덱스 + 1
            left += 1
        
        while right > start and array[right] >= array[pivot]: # 피벗보다 작은 데이터를 찾을 때까지 인덱스 - 1
            right -= 1

        if left > right: # 왼쪽과 오른쪽이 엇갈렸다면 작은 데이터(right)와 피벗을 교체
            array[right],array[pivot] = array[pivot],array[right]
        else: # 엇갈리지 않았다면 작은 데이터(left)와 큰 데이터(right)를 교체
            array[left],array[right] = array[right],array[left]
    # 엇갈렸다면 right가 바꾼 자리가 되므로 그 자리를 기준으로 분할하여 재귀
    quick_sort(array,start,right-1)
    quick_sort(array,right+1,end)

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

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

def quick_sort(array):
    
    # 리스트가 1개 이하의 원소를 담고 있다면 종료
    if len(array) <= 1:
        return array
    
    pivot = array[0] # 피벗은 첫번째 원소
    tail = array[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(array))

퀵 정렬의 시간 복잡도

퀵 정렬의 평균 시간 복잡도는 O(N logN)이다. 앞서 다루었던 두 정렬 알고리즘에 비해 매우 빠른 편이다. 퀵 정렬의 평균 시간 복잡도는 O(N logN)이지만 최악의 경우에는 시간 복잡도가 O(N^2)이다.

 

데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다.

하지만 이 책에서의 퀵 정렬처럼 리스트의 가장 왼쪽 데이터를 피벗으로 삼을때, ‘이미 데이터가 정렬되어 있는 경우’에는 매우 느리게 동작한다.

 

앞서 다룬 삽입 정렬은 이미 데이터가 정렬되어 있는 경우에는 매우 빠르게 동작한다고 했는데, 퀵 정렬은 그와 반대된다.

 

계수 정렬(Count Sort)

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

# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array)+1)

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

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

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

모든 데이터가 양의 정수인 경우 데이터의 개수가 N, 데이터 중 최대값이 K일 때 계수 정렬은 최악의 경우에도 수행시간 O(N+K)를 보장한다.

⇒ 매우 빠르고 간단한 알고리즘 !

 

조건 1. 데이터(값)은 양의 정수여야 한다.
조건 2. 값의 범위가 너무 크지 않아야 한다.(일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1000000을 넘지 않을 때 효과적)

 

예를 들어 0 이상 100 이하인 성적 데이터를 정렬할 때 계수정렬이 효과적이다.

다만, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬을 사용할 수 없는데, 그 이유는 계수 정렬을 이용할 때는 ‘모든 범위를 담을 수 있는 크기의 리스트(배열)을 선해야 하기 때문’이다.

 

계수 정렬은 앞서 다루었던 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반 정렬 알고리즘)이 아니다.

계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

1. 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트(Index)를 생성한다. 처음에는 리스트의 모든 데이터가 0이 되도록 초기화한다.
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

계수 정렬의 시간 복잡도

앞서 언급했듯이 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할때, 계수 정렬의 시간 복잡도는 O(N+K)이다.

 

따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.(현존하는 정렬 알고리즘 중 기수 정렬과 더불어 가장 빠름)

 

보통 기수 정렬은 계수 정렬에 비해 동작은 느리고 더 복잡하지만, 처리할 수 있는 정수의 크기가 더 크다.

 

계수 정렬의 공간 복잡도

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. ex) 0, 999999

 

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

 

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

 

즉, 계수 정렬은 데이터의 크기가 한정되어 있고 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 효율적인 것은 아니다.

하지만 조건만 만족한다면 계수 정렬은 정렬해야 하는 데이터의 개수가 매우 많을 때도 효과적으로 사용할 수 있다.

 

파이썬의 정렬 라이브러리

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

 

알고리즘 문제를 풀 때는 앞서 다루었던 예제처럼 정렬 알고리즘을 직접 작성하게 되는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 더 많다.

 

파이썬은 기본 정렬 라이브러리인 ‘sorted() 함수’를 제공한다. sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(N logN)을 보장한다는 특징이 있다.

 

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

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

사실 정렬 라이브러리는 이미 잘 작성된 함수이므로 우리가 직접 퀵 정렬을 구현할 때보다 더욱 더 효과적이다.

 

앞서 파이썬은 병합 정렬에 기반한다고 했는데 정확히는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있다.

 

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

 

코딩 테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있다.

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