CS 지식/자료구조와 알고리즘(Python)

[자료구조와 알고리즘 | 파이썬] Sorting (정렬)

2022.12.31

1. Sorting (정렬) 이란?

Sorting Algorithms의 종류

Bubble sort (버블 정렬)
Insertion sort (삽입 정렬)
Quick sort (퀵 정렬)
Merge sort (병합 정렬)
Topological sort (위상 정렬)

Sorting이란 크기 순으로 오름차순 정렬된 리스트로 모든 아이템을 배치하는 것을 말합니다.

위 (a) 리스트에는 숫자가 212인 item이 여러개가 있기 때문에 숫자를 key값으로 sorting하게 되면 그들 간의 순서를 정하기가 모호합니다.

이 경우에, 같은 숫자의 key에 대한 item들이 정렬되지 않은 리스트에서 정렬되어있던 순서가 sorted data에 반영되어 정렬되면 Stable sort(안정 정렬)라 하고, 그렇지 않으면 Unstable sort(불안정 정렬)라고 합니다.

위 그림에서는 정렬되지 않던 (a) 데이터의 212 key의 아이템들이 green, yellow, blue 순서로 나열되어 있는데 이 순서가 정렬된 후의 리스트에서 보장된다면 Stable sort(안정 정렬)라고 하는 것입니다.

즉, 같은 key를 갖는 데이터가 그들의 relative input order(관계적 입력 순서)를 output에서 유지하는 방식이라고 할 수 있습니다.

다음 표는 각 정렬의 stablility(안정성), complexity(복잡도), in-place(내부정렬) 여부를 나타낸 것입니다.

복잡하고 성능이 좋은 sort 방식들은 대개 O(nlogn)의 시간복잡도를 갖습니다.

quick sort의 복잡도는 위 표를 보면 O(n²)이라고 되어있는데 이는 특정 경우에 n²을 갖긴 하지만, 굉장히 희박하게 일어나는 경우에 갖는 것이기 때문에 quick sort는 코드를 조금만 바꾸면 nlogn의 시간복잡도를 가져서 사실상 O(nlogn)으로 생각해도 큰 문제가 없습니다.

참고로 quick sort에서 정렬이 하나도 되어있지 않은 경우에만 O(n²)를 갖습니다.

실제 시스템에 적용했을 때 속도가 빠른 sort는 quick sort입니다.

모두 같은 O(nlogn)일지라도 실제 적용했을 때 heap 정렬이나 merge 정렬에 비해서 평균적으로 더 빠르기 때문에 보통은 quick sort를 굉장히 많이 사용하는 것입니다. 프로그램 언어마다 sorting을 해주는 라이브러리들을 만들어 놓았는데 c++이나 java의 sorting 알고리즘에서 quick sort를 사용하여 만들어진 것이고, python의 내장 sort 함수들은 merge sort를 사용하여 만들어졌습니다.

2. Bubble sort algorithms(버블 정렬 알고리즘)

리스트에서 인접한 element들을 비교한 후에 크기 순으로 올바르게 배치하는 방식입니다.

만약, 리스트 안의 item들이 올바르지 않은 순서라면, 각각의 인접한 item들을 swapping하면서 작동합니다.

또한, n개의 item에 대해 비교를 할 때 (n-1) 번의 비교가 진행된다는 특징이 존재합니다.

맨 마지막에 하나 남은 경우는 당연히 제일 작은 값일 것이기 때문에 할 필요가 없어서 sorting이 그대로 끝나기 때문에 n-1번의 process가 진행되는 것임.

과정은 다음과 같이 진행됩니다.

The 1st iteration

6개의 데이터를 왼쪽부터 시작하여 쭉 비교하면서 제일 큰 값을 맨 오른쪽에 넣은 모습을 볼 수있습니다.

그러면 맨 끝 값은 sorting이 완료되었다고 보고, 다시 남은 5개의 item에 대해서 sorting(iteration 2)를 진행하는 것입니다.

Why Bubble?

그렇다면 왜 버블이라고 불릴까요?

첫 값인 45는 방울(bubble)과 같이 뿅 솟아올라 오른쪽으로 흘러갑니다. 흘러가면서 비교하다가 현재 bubble보다 더 큰 값이 나오면 해당 bubble이 툭 튀어올라서 해당 bubble이 오른쪽으로 흘러가게 됩니다.

이처럼 값이 정렬되는 방식이 bubble과 같이 보인다 하여 bubble sort라는 이름이 붙여지게 된 것입니다.

The 2nd iteration

The 3rd iteration

The 4th iteration

The 5th iteration

리스트에 n개의 원소가 있을 때, 최대 operation의 횟수는 n-1번이고 각 operation을 n/2번 반복하기 때문에
(n-1) * n/2 이므로 O(n²)의 시간복잡도를 갖게 됩니다.

(n-1) + (n-2) + ... + 1
- (n-1)(n-1+1) / 2

파이썬 코드로 구현

def bubble_sort(unordered):
    iteration = len(unordered)-1    # n-1
    for i in range(iteration):        # 0~n-2
        for j in range(iteration - i): #각 iteration에서 뒤져봐야 되는 index의 범위 
            if unordered[j] > unordered[j+1]:
                unordered[j], unordered[j+1] = unordered[j+1], unordered[j]


test = [45, 23, 87, 12, 32, 4]
bubble_sort(test)
print(test)
# [4, 12, 23, 32, 45, 87]

j - for 문이 한 번 돌 때마다 현재 리스트에서 제일 큰 값이 제일 오른쪽에 배치되게 됩니다.

3. Insertion sort algorithms(삽입 정렬 알고리즘)

삽입 정렬 알고리즘은 항상 정렬된 상태의 서브 리스트를 유지하면서, 다른 나머지 element들은 정렬되지 않은 상태로 남아있습니다.

해당 방식은 정렬되지 않는 서브 리스트로부터 element를 한 개씩 취하여 정렬된 서브 리스트의 알맞은 위치에 그 element들을 삽입하는 방식인 것입니다.

그래서 서브리스트는 정렬된 채로 남아있는 것이다. 그리하여 이는 우리가 카드 놀이를 할 때 주어진 내 카드 덱 안에서 무의식적으로 정렬하는 방식과 굉장히 유사하다고 볼 수 있겠습니다.

다음과 같은 배열을 생각해 봅시다.

알고리즘은 1번과 4번 인덱스들 사이를 돌기위해 for loop를 사용하면서 시작합니다.

핵심 아이디어는 0번 인덱스는 이미 정렬된 상태의 서브리스트로 보는 것입니다.

그렇기 때문에 정렬 되지 않은 element의 가장 첫번째인 1번 index부터 시작합니다.

즉, 0번 index의 '5' 카드를 쥐고 있다고 생각하면 카드가 하나밖에 없으므로 이를 정렬할 필요가 없다는 의미인 것입니다.

그런데 딜러가 다음 카드인 1번 인덱스의 1이라는 카드를 저어게 주었습니다. 그러면 이 때, sorting된 상태를 유지하면서 내 손에 가진 덱의 가장 오른쪽에 위치한, 즉 가장 마지막 값부터 비교하여 알맞은 위치에 삽입시킵니다.

1과 5를 비교했을 때 1이 5보다 작기 때문에 새로 받은 카드인 1은 5의 왼쪽에 삽입하는 것입니다.

이와 같은 과정을 모든 element에 대해서 진행하고 그 과정을 그림으로 나타낸 것은 다음과 같습니다.

정리하자면, 딜러가 주는 카드덱(오른쪽 정렬되지 않은 서브리스트)에서 한 장씩 카드를 나에게 주는데 내 손에 있는 카드덱의 가장 큰 것부터 비교하기 때문에 me < dealer 일 때까지 swapping을 한다고 생각하면 될 것 같습니다.

(n-1)번의 iteration을 평균 n/2번 진행합니다.

파이썬 코드로 구현

def insertion_sort(unordered):
    for i in range(1, len(unordered)):
        key = unordered[i] #딜러한테 새로 받는 카드

        j = i # j의 정확한 위치를 찾아줄 것이다.

        while j > 0 and unordered[j-1] > key: # 내 손의 카드의 가장 마지막 값부터 시작하여 비교
            unordered[j] = unordered[j-1] # 바꿔야 되면 큰 걸 앞으로 땡겨온다.
            j-=1  # j는 다음 인덱스를 찾으러 감.
        unordered[j] = key # while문이 통과되면 key값이 제 자리(j)를 찾은 것이므로 삽입


test = [45, 23, 87, 12, 32, 4]
insertion_sort(test)
print(test)

[4, 12, 23, 32, 45, 87]

4. Quick sort algorithms(퀵 정렬 알고리즘)

Quick sort 알고리즘은 매우 효율적인 sorting 방식입니다. 더 구체적으로 퀵정렬은 문제를 해결하기가 훨씬 더 쉽고, 작은 서브 문제들로 나누는 merge sort 알고리즘과 유사한 알고리즘의 종류인 분할정복 알고리즘입니다.

분할 정복 알고리즘은 아래 링크를 통해 확인할 수 있습니다.

[자료구조와 알고리즘] Recursion and Backtracking(재귀 & 백트래킹) + Divide and Conquer(분할정복) 알고리즘

1. Recursion 우리는 성취하고자 하는 목표를 달성하기 위해서 어떠한 메소드 안에서 다른 메소드를 호출할 수 있다는 사실을 알고 있습니다. 이와 유사하게 메소드는 자기 스스로 또한 호출할 수

cdragon.tistory.com

이 알고리즘은 정렬되지 않은 배열을 두 개의 sub-array로 나누는 것이 핵심 아이디어입니다.(즉, 분할)

구조상으로는 모든 elements가 분기점(pivot이라고도 함)을 기준으로 하여 왼쪽 부분에 있는 모든 element들은 그 값보다 작은 값을 갖게 되고 pivot의 오른쪽 부분의 모든 element들은 pivot 값보다 더 큰 값을 가진 애들만 있게 되는 구조입니다.

첫 번째 iteration 이후에 두 개의 정렬되지 않은 sub-list를 얻고 이러한 두 sub-list위에서 똑같은 process가 진행됩니다.

따라서 퀵정렬 알고리즘은 전체 리스트를 정렬하기 위해 두 개의 서브 리스트로 계속 나누는 재귀적인(recursive) 정렬 방식인 것입니다.

위 그림에서는 pivot 값을 가장 첫번째 인덱스로 잡았고 각각의 left pointer, right pointer가 존재하게 되는데,
left pointer는 pivot값보다 작은 값을 가리키지 않으면 그 자리에서 멈춰야 하고 right pointer는 반대로 pivot 값보다 큰 값을 가리키지 않으면 그 자리에서 멈춰야 합니다.

그러다가 두 pointer가 멈추었을 때(위 그림에서 4단계) left pointer와 right pointer가 더 이상 움직이지 못하기 때문에 두 값의 위치를 바꾸고 다시 계속 진행합니다. (포인터는 바뀌지 않는 것임에 유의한다.)

정상이면 멈출 필요가 없기 때문에 다음 값을 보기 위해서 pointer를 움직이는 것이고 만약 비정상적이면 멈춰서 값을 바꿀 준비를 하는 것이다.
OK면 넘어가!

그리하여 계속해서 반복하면 아래 그림과 같이 될 것입니다.

위와 같은 과정이 끝나는 조건은 left pointer와 right pointer가 서로 교차 되었을 때, 즉 서로의 위치가 엇갈렸을 때이고 이 때 right pointer의 데이터와 pivot 데이터를 swap 하면 pivot 값인 45를 기준으로 왼쪽서브리스트와 오른쪽 서브리스트에는 각각 pivot 값보다 작은값과 큰 값이 들어있게 됩니다.

물론 이때 양 옆 서브 리스트들은 정렬되지 않은 상태일 것입니다.(아직은 pivotting만 진행한 것)

그렇다면 이제 우리는 두 개의 sub-list를 얻었고 똑같은 과정을 이 두 서브리스트들에 대하여 재귀적으로 퀵 정렬 알고리즘을 적용할 것이고 이를 전체 모든 리스트가 정렬될 때까지 반복할 것입니다. (각 서브리스트에 대해 pivotting)

왼쪽 서브 리스트에서 pivot값인 4를 기준으로 정렬을 진행하고 마지막 과정에서 4에 right pointer가 위치하여 right pointer와 pivot 값을 바꾸어 주어야 하는데 두 값이 같은 값(12)을 가리키기 때문에 그대로 두는 것입니다.
- 이는 4가 제일 작은 수라는 의미

# pivot을 기준으로 양 옆 값을 정하고 궁극적으로 pivot index를 반환해 주는 함수
def partition (unsorted, first, last):
    pivot = unsorted[first]
    left = first + 1
    right = last

    while True:
        while unsorted[left] <= pivot and left < last:
            left += 1
        while unsorted[right] > pivot and right >= first: # right이 pivot까지 가도 OK
            right -= 1

        if left < right:
            unsorted[left], unsorted[right] = unsorted[right], unsorted[left]
        else:
            break


    unsorted[first], unsorted[right] = unsorted[right], unsorted[first]#swap(pivot right)
    return right # pivot index


def quick_sort(unsorted, first, last):
    if first < last:
        pivot_index = partition(unsorted, first, last)
        quick_sort(unsorted, first, pivot_index-1) # 왼쪽 sub-list에 대해서 또 진행
        quick_sort(unsorted, pivot_index+1, last) # 오른쪽 sub-list에 대해서 또 진행

    # 만약 first와 last가 같아지면 (sub-list의 크기가 1) 그냥 return 한다.


test = [45, 23, 87, 12, 32 ,4]
quick_sort(test, 0, len(test) - 1)
print(test)

5. Sort Functions in Python (파이썬에 내장된 정렬 함수)

sorting을 위한 python 내장 함수 두 가지가 존재합니다.

sort() - 리스트 자체를 in-place 정렬하는 방식의 함수
sorted() - 어떤 리스트의 정렬된 복사본을 반환해 주는 함수 (인자로 들어간 함수는 in-place 정렬 되진 않는다.)

Lambda functions(람다 함수)

lambda function은 작은 익명 함수 객체입니다.(A lambda function is a small anonymous function object)
이는 매우 많은 parameter들을 가질 수 있지만 오직 하나의 표현식만 가질 수 있습니다.

>>> def temp(a, b):
    return a + b
>>>
>>> temp(2, 3)
5
>>>
>>> x = lambda a, b: a + b
>>>
>>> x(3, 4)
7
>>>
>>> def base(n):
        return lambda a: a * n
>>>
>>> doubler = base(2)  # doubler : a * 2
>>> tripler = base(3)  # tripler : a * 3
>>>
>>> doubler(11)
22
>>> tripler(11)
33

위처럼 람다 함수 자체가 반환이 되기도 합니다.

Python sort()

sort() 함수는 list class의 멤버 함수입니다.
병합 정렬과 이 안정성을 기반으로 하는 Timsort를 사용하여 구현됩니다.
- It is implemented using Timsort, which is based on Merge sort and this stable.

>>> numbers = [3, 8, 5, 1]
>>> numbers.sort()
>>> numbers
[1, 3, 5, 8]
>>>
>>> numbers.sort(reverse=True)
>>> numbers
[8, 5, 3, 1]
>>>
>>> tuples = [(2, 2), (3, 4), (4, 1), (1, 3)]
>>> tuples.sort()
>>> tuples
[(1, 3), (2, 2), (3, 4), (4, 1)]
>>>
>>> tulples.sort(key=lambda x: x[1]) # tuple의 두 번째 element를 기준으로 sorting
>>> tuples
[(4, 1), (2, 2), (1, 3), (3, 4)]
>>>

>>> test = [(2, 'b'), (3, 'd'), (3, 'a'), (1, 'c')]
>>> test.sort()
>>> test
[(1, 'c'), (2, 'b'), (3, 'a'), (3, 'd')]
>>>

>>> test = [(2, 'b'), (3, 'd'), (3, 'a'), (1, 'c')]
>>> test.sort(key=lambda x: x[0])
>>> test
[(1, 'c'), (2, 'b'), (3, 'd'), (3, 'a')]
>>>

>>> test = [(2, 'b'), (3, 'd'), (3, 'a'), (1, 'c')]
>>> test.sort(reverse=True)
>>> test
[(3, 'd'), (3, 'a'), (2, 'b'), (1, 'c')]
>>>

>>> test = [(2, 'b'), (3, 'd'), (3, 'a'), (1, 'c')]
>> test.sort(key=lambda x: (-x[0], x[1]))
>>> test
[(3, 'a'), (3, 'd'), (2, 'b'), (1, 'c')]
>>>

>>> test = [(2, 'b'), (3, 'd'), (3, 'a'), (1, 'c')]
>>> test.sort(key=lambda x: x[1], reverse=True)  # (3, 'd'), (1, 'c'), (2, 'b'), (3, 'a')
>>> test.sort(key=lambda x: x[0])
>>> test
[(1, 'c'), (2, 'b'), (3, 'd'), (3, 'a')]
>>>

별도로 지정을 하지 않은 경우 첫 번째 element가 같은 경우 두 번째 element를 기준으로 정렬한다.
- sort()
그러나 key=lambda x: x[0] 를 명시하여 첫 번째 element를 기준으로 정렬을 하겠다 하면 그 값이 같은 경우에 두 번째 element에 대하여는 original의 순서를 그대로 사용하는 stable 정렬 방식이다.

Python sorted()

sorted() 함수는 파이썬 내장 함수 이다.
이는 리스트, 튜플, 집합, 문자열을 받고 정렬된 리스트를 반환한다.

>>> data = [3, 8, 5, 1]
>>> data.sort()
>>> data
[1, 3, 5, 8]
>>>
>>> data = [3, 8, 5, 1]
>>> data1 = sorted(data)
>>> data1
[1, 3, 5, 8]
>>> data
[3, 8 ,5 ,1]
>>>

>>> data = (3, 8, 5, 1)
>>> data1 = sorted(data)
>>> data1
[1, 3, 5, 8]
>>> data
(3, 8, 5, 1)
>>>
>>> data = {3, 8, 5, 1}
>>> data1 = sorted(data)
>>> data1
[1, 3, 5, 8]
>>> data
{8, 1, 3, 5} # data의 순서가 바뀌어 있는데 set object이기 때문에 순서는 상관없다.

새소식

인기 검색어