[정리] 정렬 알고리즘(Sorting Algorithm)

기본정렬

---

1. 버블 정렬(Bubble Sort)

• 한번 순회할 때마다 마지막 하나가 정렬되므로 원소가 거품이 올라오는 것처럼 보여서 버블정렬
• 시간복잡도가 O(n^2)로 비효율적이나 코드가 단순해 간단한 코딩에는 쓰인다.
• 이를 양쪽에서 번갈아 사용하면 칵테일 정렬

• 알고리즘 진행순서

 1. 0번째 원소와 1번째 원소를 비교 후 정렬
 2. 1번째 원소와 2번째 원소를 비교 후 정렬
 ...
 3. n-1번째 원소와 n번째 원소를 비교 후 정렬(1회 사이클)
 4. 0번째 원소와 1번째 원소를 비교 후 정렬
 5. 1번째 원소와 2번째 원소를 비교 후 정렬
 6. n-2번째 원소와 n-1번째 원소를 비교 후 정렬(2회 사이클)
 ...
 7. 0번째 원소와 1번째 원소를 비교 후 정렬

코드

def BubbleSort(arr):
  length = len(arr) - 1  # j에서 j + 1까지 비교하므로 마지막 숫자 비교 후 반복을 중단시키기 위해 len(arr) - 1 해준다
  for i in range(length): # i 한턴 당 마지막 수가 정렬된다
    swap = 0  # swap의 진행 여부를 판별하기 위한 변수 swap
    for j in range(length - i):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
        swap = 1
      
    if swap == 0:  # 진행 중 어느 턴에서 swap이 진행되지 않았다면 정렬이 완료가 된 것이므로 for문을 빠져나감
      break
  
  return arr

array = [1,7,5,21,13,35,18]
print(BubbleSort(array))

• j가 (len(arr) -1) 번째 돌 때 j와 j + 1을 비교하므로 length = len(arr) - 1
• swap 변수는 굳이 필요없으나 j번째 돌 때 swap이 진행되지 않으면 정렬이 완료된 것이므로 break로 빠져나오면 반복을 줄일 수 있다.
• 따라서 배열이 이미 정렬되어 있다면 한번만 순회하면 되므로 효율적이다. (시간 복잡도 O(n))

---

2. 선택 정렬 (Selection Sort)

• 주어진 자료들 중에서 작은 순서대로 값을 찾아 자신에게 맞는 위치와 교환하는 정렬 알고리즘
• 자료의 정렬 여부와는 관계없이 무조건 1회 사이클 시 전체 리스트를 검사하며 가장 작은 값을 찾아내므로 항상 O(n^2)의 시간 복잡도를 갖는다

• 알고리즘 진행순서

1. 0번째 원소 ~ n번째 원소 중 가장 작은 값을 찾아 0번째 원소와 swap
2. 1번째 원소 ~ n번째 원소 중 가장 작은 값을 찾아 1번째 원소와 swap
...
3. n-1번째 원소 ~ n번째 원소 중 가장 작은 값을 찾아 n-1번째 원소와 swap

코드

def SelectionSort(arr):
    length = len(arr)
    
    for i in range(length - 1):  # n-1을 기준으로 검사 후에 정렬이 종료되므로 length - 1
        min_index = i
        for j in range(i, length):  # i번 원소부터 마지막 원소 중에 가장 작은 값의 위치를 min_index에 저장하고 i번 원소와 자리 바꾸기
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]


array = [1,7,5,21,13,35,18]
SelectionSort(array)
print(array)

• i번 원소부터 마지막 원소 중에 가장 작은 값의 위치를 min_index에 저장하고 모든 값의 검사가 끝나면 i번 원소와 swap
• 0번 원소부터 n-1번 원소까지 위 과정을 반복(for i)

---

3. 삽입 정렬 (Insertion Sort)

• 주어진 자료를 앞에서부터 차례대로 하나씩 늘려가면서 자신의 위치를 찾는 정렬
• 인간이 직접 정렬하는 방식과 유사하다
• 최선의 경우 하나씩 범위를 늘린 값이 가장 큰 값일 경우 O(n)의 시간복잡도를 가지지만, 최악의 경우 앞의 모든 숫자를 전부 바꿔야 하므로 O(n^2)의 시간복잡도를 가진다

• 알고리즘 진행순서

1. 0번 원소를 건너뛴다
2. 0~1번 원소 중 1번 원소가 들어가야 할 위치를 찾아서 넣는다
3. 0~2번 원소 중 2번 원소가 들어가야 할 위치를 찾아서 넣는다
4. 0~3번 원소 중 3번 원소가 들어가야 할 위치를 찾아서 넣는다
...
5. 0~n번 원소 중 n번 원소가 들어가야 할 위치를 찾아서 넣는다

코드

def InsertionSort(arr):
    length = len(arr)
    for i in range(1, length):  # 0번 원소는 건너 뛴다
        j = i
        while j > 0 and arr[j - 1] > arr[j]:  # 기본 범위에 추가된 i번째 원소가 그 전 원소 보다 작다면 반복해서 swap
            arr[j - 1], arr[j] = arr[j], arr[j - 1]
            j -= 1

array = [1,7,5,21,13,35,18]
InsertionSort(array)
print(array)

• (i-1)번째까지 정렬이 끝난 배열에 i번째 원소가 추가되면 i번째 원소의 위치를 찾기 위해 while문이 돌게 된다

---

4. 합병 정렬 (Merge Sort)

• 분할 정복법(Divide and Conquer) 중 하나로, 하나의 큰 문제를 작은 여러 개의 문제로 쪼갠 뒤 각각을 해결하고 그 결과를 모아 원래 문제를 해결하는 방법
• 같은 방식으로 계속 반복하여 병합하므로 보통 재귀함수로 구현한다.
• 항상 O(nlogn)의 시간복잡도를 가지므로 효율적이나, 원소의 개수만큼 리스트를 쪼개고 저장해두어야 하므로 O(n)의 공간복잡도를 가진다. (메모리로 시간을 사는 방법)

• 알고리즘 진행순서

1. [1, 0, 7, 4] 리스트를 받는다
2. 각 리스트의 길이가 1이 될 때까지 반으로 나눈다 ( [1], [0], [7], [4] )
3. 왼쪽의 0번 원소( [1] )와 오른쪽의 0번 원소( [0] ) 중 작은 값을 먼저 넣은 새로운 리스트를 생성한다 ( [0 , 1] )
4. 왼쪽의 0번 원소( [7] )와 오른쪽의 0번 원소( [4] ) 중 작은 값을 먼저 넣은 새로운 리스트를 생성한다 ( [4, 7] )
5. 왼쪽의 0번 원소( [0] )와 오른쪽의 0번 원소( [4] ) 중 작은 값을 먼저 넣은 새로운 리스트를 생성한다 ( [0, ] )
6. 왼쪽의 0번 원소( [1] )와 오른쪽의 0번 원소( [4] ) 중 작은 값을 새로운 리스트에 병합한다 ( [0, 1, ] )
7. 값이 남았으므로 나머지 값을 병합해준다 ( [0, 1, 4, 7] )

코드

def MergeSort_sort(arr):
    if len(arr) < 2:  # arr의 길이가 1이면 arr값을 그대로 리턴
        return arr
    
    mid = len(arr) // 2
    left = MergeSort_sort(arr[:mid])
    right = MergeSort_sort(arr[mid:])
                          
    return MergeSort_merge(left, right)

def MergeSort_merge(left, right):
    i, j = 0, 0
    new_list = []
    while (i < len(left)) and (j < len(right)):  # 왼쪽과 오른쪽 원소 0번 원소 중 작은 값을 먼저 넣은 새로운 리스트를 생성
        if left[i] > right[j]:
            new_list.append(right[j])
            j += 1
        else:
            new_list.append(left[i])
            i += 1
    
    if i == len(left): # 위 while문에서 left든 right든 한쪽 값을 다 사용했다면 나머지 값을 전부 병합
        new_list = new_list + right[j:]
    elif j == len(right):
        new_list = new_list + left[i:]
    
    return new_list


array = [1,7,5,21,13,35,18]
print(MergeSort_sort(array))

• 리스트를 쪼개는 MergeSort_sort함수와 쪼개진 리스트들을 정렬하며 병합하는 MergeSort_merge함수로 이루어져 있다.
• 먼저 MergeSort_sort함수에서 리스트를 길이 1의 리스트로 전부 쪼개고 left, right 변수에 하나씩 넣어서 MergeSort_merge함수로 넘겨준다
• MergeSort_merge함수에서 넘어온 리스트를 정렬해서 병합하고 다시 길이 2의 리스트를 MergeSort_sort함수로 리턴해주면 다시 길이 2의 리스트들을 MergeSort_merge함수로 보내서 병합하는 방식이다

---

5. 퀵 정렬 (Quick Sort)

• 병합 정렬(Merge Sort)와 마찬가지로 Divide and Conquer방식의 정렬 방법이다.
• 차이점은 병합 정렬은 Divide단계에서는 아무 것도 하지 않고 병합 단계에서 정렬을 수행하지만, 퀵 정렬은 Divide단계에서 중요한 작업들을 전부 수행하고 병합 단계에서 아무 것도 하지 않는다.

• 알고리즘 진행 순서
  

1. 입력된 자료에서 하나의 원소를 고르고 피벗이라고 부르기로 한다(코드에선 마지막 값으로 정함)
2. 피벗을 기준으로 왼쪽에는 피벗보다 작은 값을, 오른쪽에는 피벗보다 큰 값으로 옮겨준다
3. i = unknown(다음 검사할 값), 
   b = big_value(피벗보다 큰 수),
   p = 피벗(end),
   start = small_value(피벗보다 작은 수)
   이라고 할 때,
   처음에는 i, b = start = 0이다
4. 이제 i가 오른쪽으로 한칸씩 움직이면서 검사하는데, 조건에 따라 나누면
   list[i] < list[p]인 경우 i값과 b값을 swap하고 i와 b를 +1해준다
   list[i] >= list[p]인 경우 i를 +1해준다
   i가 p가 되면
   list[p]와 list[b]를 swap하고 다음 divide를 귀해서 p의 위치를 리턴한다

코드

def swap_elements(my_list, index1, index2):
    """index1과 index2를 swap하는 함수"""
    my_list[index1], my_list[index2] = my_list[index2], my_list[index1]
    return my_list
    
def partition(my_list, start, end):
    """my_list start~end까지 정렬하는 함수"""
    p = end
    b = start
    i = start
    
    while i < len(my_list):
        if my_list[i] > my_list[p]:
            i += 1
        elif my_list[i] < my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
            i += 1
        else:
            i += 1
    
    swap_elements(my_list, b, p)
    p = b
    return p 
    
def quicksort(my_list, start, end):
    """재귀함수"""
    # base case
    if end - start < 1:
        return 
    else:
        p = partition(my_list, start, end)
        quicksort(my_list, start, p-1)
        quicksort(my_list, p+1, end)
    return


array = [1,7,5,21,13,35,18]
quicksort(array, 0, len(array) - 1)
print(array)

• 리스트 안의 값을 함수를 통해서 직접 바꾸고 출력하게 된다
• swap_elements는 두 인덱스 값을 바꿔주는 서브함수
• partition은 위의 설명에 따라 i값을 한칸씩 움직이면서 p값을 기준으로 왼쪽과 오른쪽으로 값을 나누는 함수
• quicksort는 end == start가 되는 base case를 구분해주고 partition의 return인 p를 이용해 나눠서 재귀를 하는 함수

---

6. 계수 정렬 (Counting Sort)

• 특수한 상황에서 유용한 정렬
• 데이터가 양의 정수일 경우, 데이터의 min, max값의 차이가 작은 경우
• 일반적으로 값의 차이가 1,000,000(백만)을 넘지 않는 경우
• 중복된 값이 많은 경우 효과적임

-알고리즘 진행 순서

1. 가장 작은 데이터부터 가장 큰 데이터까지 모두 담길 수 있는 길이의 리스트를 생성한다(카운트 리스트)
2. 정렬하고자 하는 데이터를 하나씩 확인하며 카운트 리스트 인덱스에 해당하는 value를 +1해준다
3. 카운트 리스트에서 0인 값을 제외하고 하나씩 출력해준다
4. 출력할 때 카운트 리스트를 누적합한 리스트로 만들어 인덱스의 위치를 표현해 줄 수 있다

코드

array = [1,7,5,21,13,35,18]

count_list = [0] * (max(array) + 1)

for i in array:  # 카운트 리스트의 인덱스에 해당하는 값 +1씩 카운트
    count_list[i] += 1

for j in range(1, len(count_list)):  # 카운트 리스트를 누적합으로 만듦
    count_list[j] += count_list[j-1]
    
new_array = [0] * (len(array))  # 정렬된 리스트를 담을 리스트 선언

for k in array:  # 기존 배열의 값을 누적합 카운트 리스트의 인덱스에서 찾는다
    new_array[count_list[k] - 1] = k
    count_list[k] -= 1
print(new_array)