[python_파이썬] 정렬의 종류 (선택정렬, 삽입정렬, 퀵정렬, 병합정렬, 힙정렬, 기수정렬, 계수정렬)

공부하는허딩크 : https://www.youtube.com/live/tF7hUdWevB0?feature=shared

 

백준에서 알고리즘을 풀다보면 정렬 문제들이 나온다. 기본적으로 잘 알고 있는 append함수나 sort함수를 사용하면

쉽게 해결할 수 있다.

단, 시간복잡도에 따른 메모리 한계 제한으로 여러가지 정렬을 정리해보자.

와 근데 진짜 이런건 누가 개발했는지 천재다 천재야....

다 비슷 비슷한데 어떤 순서로 비교해서 순서를 정렬하느냐의 차이.

참고 : https://modulabs.co.kr/blog/algorithm-python/

정렬 알고리즘	평균시간 복잡도	특징
버블정렬(bubble sort)	O(N^2)	구현 쉬움, 효율성 매우 낮음 바로 옆에 있는 것과 비교해서 정렬
선택정렬(selection sort)	O(N^2)	효율 낮음 작은 데이터를 선별해서 데이터 앞으로 보내는 정렬
삽입정렬(insertion sort)	O(N^2)	배열의 모든 요소를 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입
퀵정렬(quick sort)	O(NlogN)	찰스 앤터리 리처드 호어 개발 다른 원소와이 비교만으로 정렬 수행
병합정렬(merge sort)	O(NlogN)	분할 정복 알고리즘
힙정렬(heap sort)	O(Nlog)	내림차순 정렬 : 최소 힙 오름차순 정렬 : 최대 힙
기수정렬(radix sort)	O(NW)	기수 별로 비교 없이 수행하는 정렬
계수정렬(count sort)	O(N + K)	작은 양의 정수들인 키에 따라 객체를 수집하는 것

 

1. 버블 정렬 : 이중for문으로 사용해서 일일이 하나씩 인덱스를 비교하면서 바꿔주는 코드이다. 자기 자리를 찾는 방법

arr = [5, 3, 1, 2, 4]

#버블 정렬

for i in range(len(arr)):

    for j in range(len(arr) - i - 1):

        if arr[j] > arr[j + 1]:

            arr[j], arr[j + 1] = arr[j + 1], arr[j]

print(arr)

i = 0, 1, 2, 3, 4

i = 0일때, j = 0, 1, 2, 3으로 

                               arr[0] > arr[1]: 5 > 3이 되기때문에 arr[0], arr[1] = arr[1], arr[0]로 arr = [3, 5, 1, 2, 4]가 된다.

                               arr[1] > arr[2]: 5 > 1이 되기 때문에 arr[1], arr[2] = arr[2], arr[1]로 arr = [3, 1, 5, 2, 4]가 된다.

                               arr[2] > arr[3]: 5 > 2가 되서 때문에 arr[2], arr[3] = arr[3], arr[2]로 arr = [3, 1, 2, 5, 4]가 된다.

                               arr[3] > arr[4]: 5 > 4이 되기 때문에 arr[3], arr[4] = arr[4], arr[3]로 arr = [3, 1, 2, 4, 5]가 된다.

                              => i = 0일때 arr[0]을 일일이 숫자들과 비교해서 자리 자리를 찾는다.

                              => 맨 앞에 있는 5가 제일 큰 수여서 자리를 한번씩 계속 바꿔서 자기 자리를 찾는다.

i = 1일때, j = 0, 1, 2

                               arr[0] > arr[1]: 3 > 1이 되기때문에 arr[0], arr[1] = arr[1], arr[0]로 arr = [1, 3, 2, 4, 5]가 된다.

                               arr[1] > arr[2]: 3 > 2이 되기 때문에 arr[1], arr[2] = arr[2], arr[1]로 arr = [1, 2, 3, 4, 5]가 된다.

                               arr[2] > arr[3]: 3 > 4가 되서 무시

i = 2일때, j = 0, 1

                               arr[0] > arr[1]:  1 > 2이 되서 무시

                               arr[1] > arr[2]: 2 > 3이 되서 무시

                               arr[2] > arr[3]: 3 > 4가 되서 무시

i = 3일때, j = 0

                              arr[0] > arr[1]:  1 > 2이 되서 무시

j = 4일때, range(0)이므로 루프 종료

 

=> 여기에서 len(arr)가 5이므로 여기서 끝나지만 숫자가 커지면 일일이 비교해서 마지막 range(0)이 나와서 루프 종료될때까지 모든 인덱스들을 확인하게 된다.

즉, arr[0]을 다른 인덱스들과 비교해서 크면 뒤로 보내고 작으면 무시해서 자기 자리를 찾는 방법이다.

※이중for문으로 일일이 비교하는 방법이 여기 있었구나. for i in range(N): for j in range(N - i - 1)을 하면 out of range가 발생 없이 모든 수의 크기를 비교할 수 있음

 

2. 선택 정렬 : 이중for문을 사용해 제일 작은 index를 찾아서 계속 정렬의 앞으로 보내준다. 작은수를 앞으로 보내는 방법

arr = [5, 3, 1, 2, 4]

#선택 정렬

for i in range(len(arr)):

    min_index = i

    for j in range(i + 1, len(arr)):

        if arr[min_index] > arr[j]:

            min_index = j

    arr[i], arr[min_index] = arr[min_index], arr[i]

print(arr)

제일 작은 index = min_index

i = 0, 1, 2, 3, 4 ==> min_index = i 조건으로 ==> arr[i]가 일단 가장 작다고 가정.

i = 0일때, j = 1, 2, 3, 4으로 

                               arr[0] > arr[1]:  5 > 3이 되기때문에 mid_index = 1이됨 

                               arr[1] > arr[2]: 3 > 1이 되기 때문에 mid_index = 2이됨

                               arr[2] > arr[3]: 1 > 2가 되서 무시

                               arr[2] > arr[4]: 1 > 4이 되서 무시

                 min_index = 2이므로

                 arr[0], arr[2] = arr[2], arr[0]로 arr = [1, 3, 5, 2, 4]가 된다.

i = 1일때, j = 2, 3, 4로

                               arr[1] > arr[2]: 3 > 5가 되서 무시

                               arr[1] > arr[3]: 3 > 2이 되기 때문에 mid_index = 3이됨

                               arr[3] > arr[4]: 2 > 4가 되서 무시

                 min_index = 3이므로

                 arr[1], arr[3] = arr[3], arr[1]로 arr = [1, 2, 5, 3, 4]가 된다.

i = 2일때, j = 3, 4

                               arr[2] > arr[3]:  5 > 3이 되기 때문에 mid_index = 3이됨

                               arr[3] > arr[4]: 3 > 4이 되서 무시

                 min_index = 3이므로

                 arr[2], arr[3] = arr[3], arr[2]로 arr = [1, 2, 3, 5, 4]가 된다.

i = 3일때, j = 4

                              arr[3] > arr[4]:  5 > 4이 되기 때문에 mid_index = 4이됨

                 min_index = 4이므로

                 arr[3], arr[4] = arr[4], arr[3]로 arr = [1, 2, 3, 4, 5]가 된다.

j = 4일때, range(5, 5)이므로 루프 종료

즉, i = 0, 1, 2, 3, 4을 일일이 min_index = i로 가정해서 가장 작은 숫자의 index를 구해서 앞으로 이동시킨다.

   처음 min_index가 0으로 초기화 후 비교해보고 min_index = 2로 변경 후 index 0과 2를 자리 바꿈

   두번째 min_index가 1로 초기화 후 비교해보고 자리바꿈.... 반복해서

 

3. 삽입 정렬 : 정렬 범위를 1칸씩 확장해 나가면서 새로운 범위의 값을 기존 값들과 비교해서 자기 자리를 찾는 방법

arr = [5, 3, 1, 2, 4]

#삽입 정렬

for i in range(1, len(arr)):

    for j in range(i, 0, -1):

        if arr[j - 1] > arr[j]:

            arr[j - 1], arr[j] = arr[j], arr[j - 1]

print(arr)

i = 1, 2, 3, 4 

i = 1일때, j = 1로 

                               arr[0] > arr[1]: 5 > 3이 되기때문에 arr[0], arr[1] = arr[1], arr[0]로 arr = [3, 5, 1, 2, 4]가 된다.

i = 2일때, j = 2, 1

                               arr[1] > arr[2]: 5 > 1이 되기때문에 arr[1], arr[2] = arr[2], arr[1]로 arr = [3, 1, 5, 2, 4]가 된다.

                               arr[0] > arr[1]: 3 > 1이 되기 때문에 arr[0], arr[1] = arr[1], arr[0]로 arr = [1, 3, 5, 2, 4]가 된다.

i = 3일때, j = 3, 2, 1

                               arr[2] > arr[3]: 5 > 2이 되기 때문에 arr[2], arr[3] = arr[3], arr[2]로 arr = [1, 3, 2, 5, 4]가 된다.

                               arr[1] > arr[2]: 3 > 2이 되기 때문에 arr[1], arr[2] = arr[3], arr[1]로 arr = [1, 2, 3, 5, 4]가 된다.

                               arr[0] > arr[1]: 1 > 4가 되서 무시

i = 4일때, j = 4, 3, 2, 1

                               arr[3] > arr[4]: 5 > 4이 되기 때문에 arr[3], arr[4] = arr[4], arr[3]로 arr = [1, 2, 3, 4, 5]가 된다.

                               arr[2] > arr[3]: 3 > 4이 되서 무시

                               arr[1] > arr[2]: 2 > 3이 되서 무시

                               arr[0] > arr[1]: 1 > 2이 되서 무시

루프 종료

이게 좀 어렵네. for j in range(i, 0, -1)을 어떻게 생각했을까....

즉, i = 1, 2, 3, 4을 j의 범위를 확장시키면서 일단 0과 1을 비교해서 바꿔주고, 다시 1, 2 / 0, 1을 비교해서 바꿔주고

2, 3 / 1, 2 / 0, 1을 비교해서 바꿔주고, 3, 4 / 2, 3 / 1, 2 / 0, 1으 비교해서 바꿔줌으로서 자기 자리를 찾게 된다.

 

4. 퀵 정렬 : 중간을 기준으로 왼쪽 배열, 오른쪽 배열을 구분한 후 나중에 왼쪽 + 중간 + 오른쪽을 합치면 완성 (재귀함수 이용)

#퀵 정렬

def quick_sort(arr):

    if len(arr) <= 1:

        return arr

    pivot = arr[len(arr) // 2] #일단 중심에 가까운 값을 지정

    left, equal, right = [], [], []

    for i in arr:

        if i > pivot:

            right.append(i)

        elif i < pivot:

            left.append(i)

        else:

            equal.append(i)

    return quick_sort(left) + equal + quick_sort(right)

arr = [5, 3, 1, 2, 4]

print(quick_sort(arr))

재귀함수를 활용한다.

1. 일단, 처음 quick_sort(arr)에 들어가면 pivot = arr[2]가 됨으로 값은 1이다.

    1을 기준으로 각 값이 작으면 left, 같으면 equal, 크면 right리스트에 append를 한다.

    left = [], equal = [1], right = [5, 3, 2, 4]가 나온다.

2. left는 아무것도 없으니까 그냥 빈 배열, equal은 1 그대로 맨 앞에 return

3. quick_sort(right)로 들어가서 arr = [5, 3, 2, 4]가 되고 pivot = arr[2]가 됨으로서 값은 2이다.

4. 2를 기준으로 각 값이 작으면 letf, 같으면 equal, 크면 right리스트에 append를 한다.

    left = [], equal = [2], right = [5, 3, ,4]가 나온다.

5. 2번 순서 뒤로 return equal은 2 + quick_sort(right)가 또 return된다

6. 다시 quick_sort(right)로 들어가서 arr = [5, 3, 4]가 되고 pivot = arr[1]가 됨으로서 값은 3이다.

7. 3을 기준으로 다시 돌아가면 equal = [3], right = [5, 4]가 된다.

8. 2번 + 5번 순서 뒤로 return equal은 3 + quick_sort(right)가 또 return된다

9. 다시 quick_sort(right)로 들어가서 arr = [5, 4]가 되고 pivot = arr[1]가 됨으로서 값은 4이다.

10. 4를 기준으로 다시 돌아가면 equal = [4], right = [5]가 된다.

11. 2 + 5번 + 8번 순서 뒤로 return equal은 4 + qucik_sort(right)가 또 return된다

12. 다시 quick_sort(right)로 들어가서 len(arr)는 1이므로 바로 right가 return된다.

최종 : 2번, 5번, 8번, 11번, 12번 return값들이 재귀함수로 돌면서 하나씩 나오게 되면서

최종 return 값은 [1] + [2] + [3] + [4] + [5]가 된다.

 

5. 병합 정렬 : 재귀함수를 이용해서 마지막 재귀호출에서 lfet, right 각 1개의 값이 나오면 이후로 비교해서 순서를 잡아간다.  => 이거 이해하는데 1시간 걸렸다.

#병합 정렬

def merge_sort(arr):

    if len(arr) < 2:

        return arr

   

    mid = len(arr) // 2

    left = merge_sort(arr[:mid])

    right = merge_sort(arr[mid:])

   

    answer = []

    l = 0

    r = 0

    while len(left) > l and len(right) > r:

        if left[l] > right[r]:

            answer.append(right[r])

            r += 1

        else:

            answer.append(left[l])

            l += 1

           

    answer += left[l:]

    answer += right[r:]

       

    return answer

arr = [5, 3, 1, 2, 4]

print(merge_sort(arr))

1. merge_sort함수를 만들고 각 함수가 실행될 때 마다 left, right 변수를 지정해서 재귀호출을 한다.

첫번째 동작 merge_sort(arr = [5, 3, 1, 2, 4])

                        mid = 5 //2 = 2

                        left = merge_sort(arr[:mid]) => merge_sort(arr = [5, 3])

                        right = merge_sort(arr[mid:]) => merge_sort(arr = [1, 2, 4])

두번째 동작 left = merge_sort(arr[:mid]) => merge_sort(arr = [5, 3]) 실행

                                       merge_sort(arr[5, 3])

                                           mid = 2 // 2 = 1

                                           left = merge_sort(arr[:mid]) => merge_sort(arr = [5])

                                           right = merge_sort(arr[mid:]) => merge_sort(arr = [3])

                     세번째 동작 left = merge_sort(arr[:mid]) => merge_sort(arr = [5])

                                       merge_sort(arr[5])

                                            if len(arr) < 2: 만족

                                                 return arr ==> [5]가 반환됨

                     네번째 동작 right = merge_sort(arr[mid:]) => merge_sort(arr = [3])

                                       merge_sort(arr[3])

                                            if len(arr) < 2: 만족

                                                 return arr ==> [3]가 반환됨

                     다섯번째 동작 left = [5]와 right = [3]을 while 반복 answer = []와 l과 r = 0으로 초기화

                                       while 1(len(left)) > 0 and 1(len(right)) > 0:

                                            if left[0] > right[0]: => 5 > 3 만족

                                                  answer.append(right[r]) ==> answer = [3]

                                                  r += 1 => while탈출

                    여섯번째 동작 answer에 left와 right의 나머지들을 다 넘겨줌 => answer = [3, 5] 가 최종반환

   ==> 여기서 두번째 left = [3, 5]가 됨.

일곱번째 동작 left = merge_sort(arr[:mid]) => merge_sort(arr = [1, 2, 4]) 실행

                                       merge_sort(arr[1, 2, 4])

                                           mid = 3 // 2 = 1

                                           left = merge_sort(arr[:mid]) => merge_sort(arr = [1])

                                           right = merge_sort(arr[mid:]) => merge_sort(arr = [2, 4])

                     여덟번째 동작 left = merge_sort(arr[:mid]) => merge_sort(arr = [1])

                                       merge_sort(arr[1])

                                            if len(arr) < 2: 만족

                                                 return arr ==> [1]가 반환됨

                     아홉번째 동작 right = merge_sort(arr[mid:]) => merge_sort(arr = [2, 4])

                                             left = merge_sort(arr[:mid]) => merge_sort(arr = [2, 4]) 실행

                                             merge_sort(arr[2, 4])

                                                  mid = 2 // 2 = 1

                                                  left = merge_sort(arr[:mid]) => merge_sort(arr = [2])

                                                  right = merge_sort(arr[mid:]) => merge_sort(arr = [4])

                                   열번째 동작 left = merge_sort(arr[:mid]) => merge_sort(arr = [2])

                                                             merge_sort(arr[2])

                                                                  if len(arr) < 2: 만족

                                                                        return arr ==> [2]가 반환됨

                                  열한번째 동작 right = merge_sort(arr[mid:]) => merge_sort(arr = [4])

                                                            merge_sort(arr[4])

                                                                 if len(arr) < 2: 만족

                                                                        return arr ==> [4]가 반환됨

                                  열두번째 동작 left = [2]와 right = [4]을 while 반복 answer = []와 l과 r = 0으로 초기화

                                                           while 1(len(left)) > 0 and 1(len(right)) > 0:

                                                                 if left[0] > right[0]: => 2 > 4 불만족

                                                                 else:   

                                                                     answer.append(left[l]) ==> answer = [2]

                                                                     l += 1 => while탈출

                                  열세번째 동작 answer에 left와 right의 나머지들을 다 넘겨줌 => answer = [2, 4] 가 최종반환

열네번째 동작 left = [1], right = [2, 4] while 반복 answer = []와 l과 r = 0으로 초기화

            while 1(len(left)) > 0 and 2(len(right)) > 0:

                      if left[0] > right[0]: => 1 > 2 불만족

                      else:   

                        answer.append(left[l]) ==> answer = [1]

                        l += 1 => while탈출

열다섯번째 동작 answer에 left와 right의 나머지들을 다 넘겨줌 => answer = [1, 2, 4] 가 최종반환

   ==> 여기서 두번째 right = [1, 2, 4]가 됨.

열여섯번째 동작 left = [3, 5], right = [1, 2, 4] while 반복 answer = []와 l과 r = 0으로 초기화

       while 2 > 0 and 3 > 0: 만족

           if left[0] > right[0] => 3 > 1 만족

                 answer.append(right[0])  ==> answer = [1]  

                 r += 1 ==> r = 1 => while 만족

           if left[0] > right[1] => 3 > 2 만족

                answer.append(right[1])  ==> answer = [1, 2] 

                r += 1 ==> r = 2 => while 만족

           if left[0] > right[2] => 3 > 4 불만족

           else:

                answer.append(left([0])  ==> answer = [1, 2, 3]

                l += 1 ==> l = 1 => while만족

           if left[1] > right[2] => 5 > 4 만족

                answer.append(right[2])  ==> answer = [1, 2, 3, 4]

                r += 1 ==> r = 3 => while 불만족 탈출

열일곱번째 동작 answer에 left[1:]와 right[3:]의 나머지들 다 넘겨줌=> answer = [1, 2, 3, 4, 5]

==> 최종 answer = [1, 2, 3, 4, 5] 반환        

 

6. 힙 정렬 : 최대 힙 트리(오름차순) / 최소 힙 트리(내림차순) 구성 정렬 => 현재 '24년 5월 4일 자료구조를 정확히 이해 못함 => 추가 학습 이후 정리 예정

<참고 코드 : 아래의 코드가 이해가지 않음. 왜 l = 2 * i + 1인지 r은 왜 있는지....>

def heap_sort(arr):

    def heapify(arr, n, i):

        largest = i

        l = 2 * i + 1

        r = 2 * i + 2

        if l < n and arr[i] < arr[l]:

            largest = l

        if r < n and arr[largest] < arr[r]:

            largest = r

        if largest != i:

            arr[i], arr[largest] = arr[largest], arr[i]

            heapify(arr, n, largest)

    n = len(arr)

    for i in range(n, -1, -1):

        heapify(arr, n, i)

    for i in range(n-1, 0, -1):

        arr[i], arr[0] = arr[0], arr[i]

        heapify(arr, i, 0)

    return arr

 

7. 기수 정렬 : 요소의 비교 없이 각 요소를 index로 변경 후 순서대로 꺼내서 정렬하는 방법 (%나머지를 활용해서 순서 정함) => 현재 '24년 5월 4일 자료구조를 정확히 이해 못함 => 추가 학습 이후 정리 예정

<참고 코드 : 일단 이해하기 힘드니까 그냥 넘어감>

def radix_sort(arr):

    RADIX = 10

    placement = 1

    max_digit = max(arr)

    while placement < max_digit:

        buckets = [list() for _ in range(RADIX)]

        print(buckets)

        for i in arr:

            tmp = int((i / placement) % RADIX)

            buckets[tmp].append(i)

            print(buckets)

        a = 0

        for b in range(RADIX):

            buck = buckets[b]

            for i in buck:

                arr[a] = i

                a += 1

                print(arr)

        placement *= RADIX

    return arr

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

print(radix_sort(arr))

 

8. 계수 정렬 : 이것도 index로 생각하네? arr의 각 요소의 숫자들을 index로 생각해서 해당 인덱스를 활용함. INDEX가 중요함.

#계수 정렬

arr = [5, 3, 1, 2, 4]

max_value = max(arr)

m = max_value + 1

count = [0] * m

for i in arr:

    count[i] += 1

   

index = 0

for i in range(m):

    for _ in range(count[i]):

        arr[index] = i

        index += 1

print(arr)

 

1. max를 활용해서 제일 큰 숫자를 뽑아준다. 

    ㄴ 그리고 m = max + 1을 해줌 ==> + 1이 중요함 why? 그래야 range(m)을 돌때 max숫자가 나올거아냐?

    ㄴ max = 5라고 한다면 m = 6이어야 range(6)을 했을때 0, 1, 2, 3, 4, 5 이렇게 해서 5가 나오잖아.

2. count변수에 [0] *m으로 m = 6이면 count = [0, 0, 0, 0, 0, 0]이 나옴

    ㄴ why? 6개 인가??? range(m)을 했을때 마지막 5가 나오는데 count[5]를 했을때를 위한 거임

3. for i in arr로 count[i] += 1로 arr의 숫자들을 count의 index로 전환해서 +1을 해줌, 숫자가 중복되면 2, 3...이 되겠지.

4. 이제 index = 0으로 초기화 후 for i in range(m)으로 0부터 최대값까지 숫자들을 하나씩 불러옴

    ㄴ 이중 for문으로 count[i] 개수만큼 반복해야함, 그래야 중복되는 숫자들을 넣을 수 있음

    ㄴ 만약 arr = [2, 2] 라면, count = [0, 0, 2]일거임 => i = 2에서 range(count[2])로 arr[0] = 2, arr[1] = 2 이렇게 넣을수 있음

 

흠... 계수 정렬 깔끔하고 좋네.

 

이렇게 몇시간동안 정렬 관련한 알고리즘을 확인했다.

 

자주 보면서 복습하자!!