정렬들

개요

공부 겸 정렬을 다 정리해보자

버블 정렬

아이디어

가장 간단한 아이디어, j 인덱스와 j+1 인덱스 값을 비교하여 큰 값을 뒤로 단계적으로 밀어낸다.

구현

def bubble(arr):
    for i in range(0,len(arr)):
        for j in range(0,len(arr)-i-1):
            if arr[j+1] < arr[j]:
                arr[j], arr[j+1] = arr[j+1], arr[j]





arr = [5,4,1,3,7,0]

bubble(arr)

print(arr)

출력

[5, 4, 1, 3, 7, 0] # Input
[4, 1, 3, 5, 0, 7]
[1, 3, 4, 0, 5, 7]
[1, 3, 0, 4, 5, 7]
[1, 0, 3, 4, 5, 7]
[0, 1, 3, 4, 5, 7]
[0, 1, 3, 4, 5, 7]
[0, 1, 3, 4, 5, 7] # anw

n번쨰 줄에서 n번째 최대 값을 배열 끝으로 밀착시킨다.

특징

배열의 길이를 N이라 할때 첫 for 문이 N번, 2번째 포문도 최대 N번 동작하므로

시간복잡도

$O(N^2)$

구현이 쉽다. 오래걸린다. 잘 안쓴다?

안정 정렬 : 같은 값 끼리는 교환이 일어나지 않으므로..

---

카운팅 정렬

아이디어

주어진 배열의 값이 정수일 때 사용 가능, 배열 내의 값의 최대 값이 K라 할때, K가 N보다 작고 중복된 값들이 많다면 사용할 만 하다.

배열의 정수가 나타난 횟수를 카운트한 리스트를 만든 뒤, 앞에서 부터 누적시켜 인덱스를 바로 얻어낼 수 있게한다.

구현

def counting(arr):
    max_num = 10
    anw = [0]*len(arr)
    countsum = [0]*(max_num+1)
    for i in arr:
        countsum[i] += 1
    for idx in range(len(countsum)-1):
        countsum[idx+1] += countsum[idx]
    for idx in range(len(arr)-1,-1,-1):
        countsum[arr[idx]] -= 1
        anw[countsum[arr[idx]]] = arr[idx]
    return anw

arr = [5,4,1,3,7,7,0,0,10]
anw = counting(arr)
print(arr)
print(anw)

카운트 횟수를 앞에서 부터 누적시키는 countsum을 만들면,

이 예제에서 countsum은

[2, 3, 3, 4, 5, 6, 6, 8, 8, 8, 9]

다음과 같다. 다음으로 소팅해야할 arr를 뒤에서부터 접근해서 anw에 인덱스대로 배치해준다.

순서대로 써본다면

1. arr[-1] 값인 10을 만나면 countsum[10]을 가서 anw[8]:(9-1) 에 배치해준다. anw[8]에 10을 올려주고 만약 arr에 10이 또있다면 countsum[10]은 8이 되어서 다음에는 anw idx 7에 배치해야 함을 알 수 있다.

2. arr[-2] 값인 0을 만나면 countsum[0]을 가서 anw[1]:(2-1)에 배치해준다. 다음 arr[-3] 값인 0도 anw[0]에 배치가 된다.

arr를 전체 다 훑을 때까지 반복

출력

[5, 4, 1, 3, 7, 7, 0, 0, 10] # input

[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 10]
[0, 0, 0, 0, 0, 0, 0, 0, 10]
[0, 0, 0, 0, 0, 0, 0, 7, 10]
[0, 0, 0, 0, 0, 0, 7, 7, 10]
[0, 0, 0, 3, 0, 0, 7, 7, 10]
[0, 0, 1, 3, 0, 0, 7, 7, 10]
[0, 0, 1, 3, 4, 0, 7, 7, 10]
[0, 0, 1, 3, 4, 5, 7, 7, 10] # anw

Input 배열 뒤에서부터 자리를 채워나간다.

특징

인풋 배열 사이즈 N과 누적합 배열 크기 K에 대해 1중 포문이 쓰이므로

시간복잡도

$O(N+K)$

매우 빠르지만, 정수 단위의 배열에 밖에 사용할 수 없고, N이 작지만 K가 크다면 별로 효과적인 접근이 아니게된다.

인풋 배열에 바로 정렬을 하게 되면, 순서가 꼬여 사용할 수가 없다. 길이 N의 새로운 배열 anw을 써야만 한다.

안정정렬 : 안정정렬을 위해서 anw 배열을 채울 때 idx를 뒤에서부터 시행

---

선택 정렬

아이디어

전체 구간 내의 최소값을 찾은 뒤 0번째로 옮겨주고, 1번부터 시작하는 구간에서 최소값을 찾은 뒤 1번째로 옮겨주고.. 의 반복

버블 정렬과 비슷하지만 교환 횟수가 적다.

구현

def selectingsort(arr):
    for i in range(len(arr)):
        print(arr)
        min_idx = i
        for j in range(i,len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j

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

arr = [5,4,1,3,7,0]
selectingsort(arr)
print(arr)

출력

[0, 5, 4, 1, 3, 7, 0] # input
[0, 5, 4, 1, 3, 7, 0]
[0, 0, 4, 1, 3, 7, 5]
[0, 0, 1, 4, 3, 7, 5]
[0, 0, 1, 3, 4, 7, 5]
[0, 0, 1, 3, 4, 7, 5]
[0, 0, 1, 3, 4, 5, 7]
[0, 0, 1, 3, 4, 5, 7]

버블 정렬과 반대로 n번째 최소값을 처음에 밀착

특징

버블정렬과 비슷하게

시간복잡도

$O(N^2)$

하지만 교환하는 횟수가 줄어 버블정렬보다 빠르다.

불안정 정렬

ex.
[B, b, a, c] ( a < b==B < c) 라면
첫 포문에서 [a, b, B, c] 가 되고 그 뒤로 마무리

---

빠른 정렬

아이디어

분할정복 개념을 사용한 정렬,

배열에서 임의의 pivot 값을 잡고, pivot 값보다 큰 값은 오른쪽으로 pivot 값보다 작은 값은 왼쪽으로 정렬한 뒤 스왑한 뒤

pivot을 기준으로 구간을 나누어 반복

구현

def quick_sort(arr):
    def sort(low, high):
        if high <= low:
            return None

        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        pivot = arr[(low + high) // 2]
        while low <= high:
            while arr[low] < pivot:
                low += 1
            while arr[high] > pivot:
                high -= 1
            if low <= high:
                arr[low], arr[high] = arr[high], arr[low]
                low, high = low + 1, high - 1
        return low

    return sort(0, len(arr) - 1)



arr = [1,2,3,10,0,9,8,7] + [1,2,3,10,0,9,8,7]
print(arr)
print(quick_sort(arr))

퀵 소트는 주어진 구간에서 피봇을 정하고 정렬을 반복하는

partition 함수와 다음 구간을 정해주는 sort 함수 2개로 나눠진다.

pivot_idx를 구간의 가운데로 잡고, 구간의 양쪽 끝에서 좁혀오며 pivot보다 큰 값을 가진 arr[low]와 작은 값을 가진 arr[high]를 교환해주고 low와 high가 만났을 때 그 idx를 다음 구간으로 mid 정해준다.

sort 함수에서는 partition(low,high)에서 mid를 받아 mid 기준으로 구간을 2개로 나누어 sort를 반복한다.

이제보니 명명법이 반대가 되야 맞는거 아닌가 싶다.

출력

[1, 2, 3, 10, 0, 9, 8, 7, 1, 2, 3, 10, 0, 9, 8, 7] #Input

low 0 high 15 pivot_idx 7
[1, 2, 3, 7, 0, 0, 3, 2, 1, 7, 8, 10, 9, 9, 8, 10]

low 0 high 8 pivot_idx 4
[0, 0, 3, 7, 2, 1, 3, 2, 1, 7, 8, 10, 9, 9, 8, 10]

low 0 high 1 pivot_idx 0
[0, 0, 3, 7, 2, 1, 3, 2, 1, 7, 8, 10, 9, 9, 8, 10]

low 2 high 8 pivot_idx 5
[0, 0, 1, 1, 2, 7, 3, 2, 3, 7, 8, 10, 9, 9, 8, 10]

low 2 high 3 pivot_idx 2
[0, 0, 1, 1, 2, 7, 3, 2, 3, 7, 8, 10, 9, 9, 8, 10]

low 4 high 8 pivot_idx 6
[0, 0, 1, 1, 2, 3, 2, 3, 7, 7, 8, 10, 9, 9, 8, 10]

low 4 high 6 pivot_idx 5
[0, 0, 1, 1, 2, 2, 3, 3, 7, 7, 8, 10, 9, 9, 8, 10]

low 4 high 5 pivot_idx 4
[0, 0, 1, 1, 2, 2, 3, 3, 7, 7, 8, 10, 9, 9, 8, 10]

low 7 high 8 pivot_idx 7
[0, 0, 1, 1, 2, 2, 3, 3, 7, 7, 8, 10, 9, 9, 8, 10]

low 9 high 15 pivot_idx 12
[0, 0, 1, 1, 2, 2, 3, 3, 7, 7, 8, 8, 9, 9, 10, 10]

low 9 high 12 pivot_idx 10
[0, 0, 1, 1, 2, 2, 3, 3, 7, 7, 8, 8, 9, 9, 10, 10]

low 9 high 10 pivot_idx 9
[0, 0, 1, 1, 2, 2, 3, 3, 7, 7, 8, 8, 9, 9, 10, 10]

low 11 high 12 pivot_idx 11
[0, 0, 1, 1, 2, 2, 3, 3, 7, 7, 8, 8, 9, 9, 10, 10]

low 13 high 15 pivot_idx 14
[0, 0, 1, 1, 2, 2, 3, 3, 7, 7, 8, 8, 9, 9, 10, 10]

low 13 high 14 pivot_idx 13
[0, 0, 1, 1, 2, 2, 3, 3, 7, 7, 8, 8, 9, 9, 10, 10] # Output

partition 함수에 프린트를 찍어본 것.
pivot_idx가 mid가 아님을 유의하자.
구간의 크기가 불규칙함을 볼 수 있다.

특징

길이가 N인 구간에 대한 비교, 정렬은 N번.
처음 배열의 길이가 $N= 2^K$이라면 길이가 $2^{K-1}$인 배열 2개에 대한 정렬이 일어나고 배열의 길이는 계속 2의 배수로 줄면서 배열의 개수는 2배가 되는 것을 알 수 있다.
연산 량을 정리하면 [구간 개수 * 구간에 대한 연산량]의 합이 되고 구간의 길이가 $N= 2^K$ 라면

$1*2^K+(2*2^{K-1})+(4*2^{K-2})+...+(2^{K-1}*2^{1}) \dots(1)$

다음같이 정리할 수 있다.

$N= 2^K, K = log_2N$ 이므로 (1) 식을 $N$에 대해서 정리하면 시간복잡도는 N값을 가지는 항의 개수가 총 K개 이므로

시간복잡도

$O(Nlog_2{N})$

로 나타낼 수 있다.

최악의 경우는 적절하지 않은 pivot을 잡아 구간이 잘 분할되지 않는 경우다. 만약 길이가 N인 구간이 다음 분할에서 N-1과 1인 구간으로만 나눠지게 된다면 결국 $O(N^2)$의 시간 복잡도를 가지게 된다.

앞으로 나올 정렬들만큼 성능도 좋고 구현도 쉬운 편이라 자주 쓰는 편.
메모리도 따로 안쓴다.

불안정 정렬 : 출력에서 2번째 출력과 3번째 출력을 비교해보면 0,0을 보면 순서가 바뀌어있다는 것을 알 수 있다. 1, 2 가 0, 0과 바뀌면서 1, 2가 2, 1이 됨.

---

합병 정렬

아이디어

앞선 빠른 정렬은 pivot을 정의한 뒤 pivot 값을 기준으로 정렬하고 구간을 나누어 분할정복하였다.

pivot이 없이 그냥 구간을 나눈 뒤 구간들을 합치면서 정렬하면 되지 않을까?

가 되겠다.
이미 정렬된 두 배열의 합병 정렬은 앞에서부터 비교해가며 더 작은 값을 꺼내가며 붙이면 된다.

pivot이 없으므로 앞선 적절치 않은 pivot을 골랐을 때의 단점은 사라지고, 구간의 분할 크기가 항상 일정하다는 장점이 있지만, 합병을 위한 메모리를 써야한다는 단점이 있다.

구현

def merge_sort(arr):
    def sort(low,high):
        #print('sort',low,high)
        if high-low <= 1:
            return arr[low:high]

        mid = (low+high)//2
        left_list = sort(low,mid)
        right_list = sort(mid,high)
        return merge(left_list,right_list)

    def merge(left,right):
        #print('merge',left, right)
        result = []
        i = 0
        j = 0
        while i < len(left) or j < len(right) :
            if i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            elif i < len(left):
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        #print('result', result)
        return result
    return sort(0,len(arr))

arr = [1,2,3,10,0,9,8,7] + [1,2,3,10,0,9,8,7]
anw = merge_sort(arr)
print(anw)

앞선 빠른 정렬과 비슷하게, idx의 중간값으로 구간을 나누고 구간이 길이가 1이라면 해당 배열의 값을 배열로 보내준다.

mid를 기준으로 분할된 두 배열이 만나면 합병을 하는데, 두 배열이 이미 정렬이 되었다고 가정하고 앞에서부터 차근차근 작은 값을 빼내 합병한다.

출력

[1, 2, 3, 10, 0, 9, 8, 7, 1, 2, 3, 10, 0, 9, 8, 7, 3] # Input
merge [1] [2]
result [1, 2]
merge [3] [10]
result [3, 10]
merge [1, 2] [3, 10]
result [1, 2, 3, 10]
merge [0] [9]
result [0, 9]
merge [8] [7]
result [7, 8]
merge [0, 9] [7, 8]
result [0, 7, 8, 9]
merge [1, 2, 3, 10] [0, 7, 8, 9]
result [0, 1, 2, 3, 7, 8, 9, 10]
merge [1] [2]
result [1, 2]
merge [3] [10]
result [3, 10]
merge [1, 2] [3, 10]
result [1, 2, 3, 10]
merge [0] [9]
result [0, 9]
merge [7] [3]
result [3, 7]
merge [8] [3, 7]
result [3, 7, 8]
merge [0, 9] [3, 7, 8]
result [0, 3, 7, 8, 9]
merge [1, 2, 3, 10] [0, 3, 7, 8, 9]
result [0, 1, 2, 3, 3, 7, 8, 9, 10]
merge [0, 1, 2, 3, 7, 8, 9, 10] [0, 1, 2, 3, 3, 7, 8, 9, 10]
result [0, 0, 1, 1, 2, 2, 3, 3, 3, 7, 7, 8, 8, 9, 9, 10, 10]
[0, 0, 1, 1, 2, 2, 3, 3, 3, 7, 7, 8, 8, 9, 9, 10, 10] # Output

특징

빠른 정렬과 같이

N/2 길이의 2개의 배열을 합병하는데 N번 시행
1 길이의 N개의 배열을 합병하는데도 N번 시행,
N번의 시행을 총 $log_2N$번 반복하므로

시간복잡도는 $O(Nlog_2N)$ 이 됩니다.

자료구조가 연결리스트라면 다음 리스트를 연결해주는 포인터 주소만 바꿔주면 되서
따로 메모리가 필요 없다고 합니다. 이 예제에선 필요합니다.. 자료구조의 분산이 너무 클 땐, 안정성을 위해서 합병 정렬이 나을 것 같습니다.

안정 정렬 : 합병 시 비교 대상이 같은 값이라면 항상 left_list에 있는 친구를 먼저 왼쪽으로 써준다. 순서가 보존된다.

---

결론

배열이 정수로 이루어져 있고 최대 값 K가 작다 -> 카운팅정렬

일반적인 경우는 그냥 편하게 -> 빠른 정렬

안정 정렬을 해야할 때 -> 합병 정렬

빠른 정렬이 합병 정렬보다 빠른 이유는 합병 정렬에서 합병을 위한 배열을 만들고 채우는 과정에서 지연되는 점이 많아서 그렇다고 합니다.

힙 정렬은 배열 전체를 정렬하는 것은 아니므로 트리 관련 포스팅을 하게 된다면 다루려고 합니다.

글 쓰는게 힘드네요!