정렬(Sorting)

💡 유용 사이트

Python compiler - visualize, debug, get AI help from ChatGPT

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

📝 정렬(Soring)이란?

어떤 데이터들이 주어졌을 때, 이를 정해진 순서대로 나열하는 것

참고) 각 정렬에 대한 설명은 오름차순을 기준으로 작성되었고, 쉬운 이해를 위해 파이썬으로 코드를 작성함

 

📌 버블 정렬(Bubble Sort)

버블 정렬에서는 인접한 두 개의 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 교체하며 정렬을 수행한다.

 

정렬 과정 속에서 데이터가 이동하는 모습이 마치 물속에서 거품이 올라오는 모양(가장 큰 데이터가 리스트 끝에 '올라가는' 모습을 상상해보자!)과 비슷하다고해서 '버블' 정렬이라고 한다.

 

 

예제 코드

def bubble_sort(data_list):
    for i in range(len(data_list) - 1):
        for j in range(len(data_list) - 1 - i):
            if data_list[j] > data_list[j+1]:
                data_list[j], data_list[j+1] = data_list[j+1], data_list[j]
    return data_list
    
data_list = [29, 10, 14, 37, 12]
print(bubble_sort(data_list))

# [10, 12, 14, 29, 37]

ㄴ j는 i보다 하나씩 적게 (n - 1 - i) 돈다.

 

하지만 한번도 swap 되지 않았다는 것은, 이미 정렬이 되어있다는 것이므로

아래와 같이 조금 더 효율적으로 동작할 수 있도록 코드를 수정할 수 있다.

def bubble_sort(data_list):
    for i in range(len(data_list) - 1):
        is_swap = False
        for j in range(len(data_list) - 1 - i):
            if data_list[j] > data_list[j+1]:
                data_list[j], data_list[j+1] = data_list[j+1], data_list[j]
                is_swap = True
        if is_swap == False:
    	    break
    return data_list
    
data_list = [29, 10, 14, 37, 12]
print(bubble_sort(data_list))

# [10, 12, 14, 29, 37]

 

시간 복잡도

• 반복문이 두 개이므로 $O(n^{2})$
  • 최악의 경우, $\frac{n * (n - 1)}{2}$
  • 완전 정렬이 되어 있는 상태라면 최선은 $O(n)$

 

극단적인 경우로, 입력 데이터가 우연히 작은 순서로 나열되어 있을 때는 교체가 한 번도 발생하지 않는다.

반대로, 숫자가 큰 순서대로 나열되어 있다면 비교할 때마다 교체해 주어야 한다.

(아래의 짤을 참고하자!)

 

 

📌 선택 정렬(Selection Sort)

선택 정렬은 다음과 같은 순서를 반복하며 정렬하는 알고리즘이다.

 

1. 주어진 데이터 중 최소값을 찾는다.

2. 해당 최소값을 리스트 맨 앞(왼쪽 끝)에 위치한 데이터와 교체한다.

3. 맨 앞의 위치를 제외하고 나머지 데이터를 동일한 방법으로 반복한다.

 

정렬되지 않은 리스트에서 가장 작은 요소를 선택하며 정렬하기 때문에 '선택' 정렬이라고 부른다.

 

예제 코드

def selection_sort(data_list):
    for stand in range(len(data_list)-1):
        lowest = stand
        for index in range(stand + 1, len(data_list)):
            if data_list[index] < data_list[lowest]:
                lowest = index
        data_list[stand], data_list[lowest] = data_list[lowest], data_list[stand]
    
    return data_list

data_list = [29, 10, 14, 37, 12]
print(selection_sort(data_list))

# [10, 12, 14, 29, 37]

ㄴ index가 stand 바로 뒤 부터 리스트 끝까지 돌면서 가장 작은 값이 저장된 인덱스를 찾는다.

 

시간 복잡도

• 반복문이 두 개이므로 $O(n^{2})$
  • 실제로 상세하게 계산하면, $\frac{n * (n - 1)}{2}$

 

또한, 숫자 교체는 각 턴에서 최대 1회이다.

입력 데이터가 이미 작은 순으로 나열되어 있다면 교체는 한 번도 발생하지 않는다.

(아래의 짤을 참고하자!)

 

 

📌 삽입 정렬(Insertion Sort)

삽입 정렬은 리스트의 좌측부터 차례대로 정렬하는 방식이다.

진행하다보면 좌측에는 정렬이 끝난 데이터가 오게되고, 우측에는 아직 확인하지 않은 데이터들이 남게 된다.

우측의 아직 확인하지 않은 데이터 리스트에서 데이터를 하나 꺼내,

정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식이므로 '삽입' 정렬이라고 부른다.

 

 

예제 코드

1. 처음에는 첫 번째 인덱스를 정렬된 부분으로 간주한다. (따라서, 정렬되지 않는 부분인 두 번째 인덱스부터 시작함)

2. 정렬되지 않은 부분에서 다음 요소를 선택한다.

3. 선택된 요소를 이미 정렬된 부분에서 삽입할 위치를 찾는다.

4. 적절한 위치를 찾으면 해당 위치에 삽입한다.

5. 이 과정을 정렬되지 않은 부분 리스트의 모든 요소에 대해 반복한다.

 

def insertion_sort(data_list):
    for i in range(1, len(data_list)):
        temp = data_list[i] # 삽입할 요소를 선택
        j = i - 1
        
        # temp보다 큰 모든 요소를 오른쪽으로 이동
        while j >= 0 and temp < data_list[j]:
            data_list[j + 1] = data_list[j]
            j -= 1
        
        # temp를 올바른 위치에 삽입
        data_list[j + 1] = temp

    return data_list
    
my_list = [29, 10, 14, 37, 12]
print(insertion_sort(my_list))

# [10, 12, 14, 29, 37]

 

시간 복잡도

반복문이 두개이므로 $O(n^{2})$

• 최악의 경우, 모든 요소를 비교하여 삽입해야하기 때문에 $\frac{n * (n - 1)}{2}$

 

• 완전 정렬이 되어 있는 상태라면, 각 요소를 삽입하는 과정만 수행하기 때문에 최선은 경우 시간 복잡도는 $O(n)$

 

📌 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)은 재귀용법을 활용한 정렬 알고리즘이다.

 

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

2. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.

3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

 

 

예제 코드

크게 두 개의 함수(mergesplit, merge)가 있다.

def merge(left, right):
    merged = []
    left_idx, right_idx = 0, 0
    
    # 케이스 1) left와 right가 둘 다 있을 때
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] <= right[right_idx]:
            merged.append(left[left_idx])
            left_idx += 1
        else:
            merged.append(right[right_idx])
            right_idx += 1
            
    # 케이스 2) left 데이터가 없을 때
    while left_idx < len(left):
        merged.append(left[left_idx])
        left_idx += 1
    
    # 케이스 3) right 데이터가 없을 때
    while right_idx < len(right):
        merged.append(right[right_idx])
        right_idx += 1
        
    return merged

def mergesplit(data_list):
    if len(data_list) <= 1:
        return data_list
    
    medium = len(data_list) // 2
    left = mergesplit(data_list[:medium])
    right = mergesplit(data_list[medium:])
    return merge(left, right)
    
my_list = [29, 10, 14, 37, 12]
print(mergesplit(my_list))

# [10, 12, 14, 29, 37]

 

시간 복잡도

알고리즘 분석은 쉽지 않음, 이 부분은 참고로만 알아두자!

• 몇 단계 깊이까지 만들어지는지를 depth라고 하고, i로 놓자. 맨 위 단계는 0
  • 다음 그림에서 $n/2^{2}$는 2단계 깊이라고 해보자.
  • 각 단계에 있는 하나의 노드 안의 리스트 길이는 $n/2^{2}$가 된다.
  • 각 단계에는 $2^{i}$개의 노드가 있다.
• 따라서, 각 단계는 항상 $2^{i} * \frac{n}{2^{i}} = O(n)$
• 단계는 항상 ${log_2}n$개 만큼 만들어짐, 시간 복잡도는 결국 $O(logn)$, 2는 상수이므로 무시
• 결과적으로, 단계별 시간 복잡도 $O(n) * O(logn) = $O(nlogn)$

좀 더 쉽게 정리)

병합 정렬은 입력 리스트를 반으로 나눈 후 각각 정렬하고, 그 다음에 정렬된 두 개의 리스트를 합쳐서 정렬된 리스트를 생성한다. 이 과정에서 각 레벨에서 $O(n)$의 작업이 필요하며, 전체 높이가 $O(logn)$이 되기 때문제 전체 시간 복잡도는 $O(nlogn)$이 된다.

 

📌 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)에서는 기준점(pivot, 피봇)을 리스트 안에서 임의로 하나 선택해서,

피봇 이외의 수를 [피봇보다 작은 데이터]와 [피봇 이상인 데이터] 두 그룹으로 나누고 이를 다음과 같이 배치한다.

 

[피봇보다 작은 데이터] < 피봇 <  [피봇 이상인 데이터] 

 

그 다음에는 각 [ ] 안을 정렬만 하면 전체가 정렬된다.

단, [ ] 안을 정렬할 때도 다시 퀵 정렬이 사용된다.

 

예제 코드

• 피봇을 하나 정함
• 피봇보다 작은 데이터는 왼쪽(left), 피봇보다 큰 데이터는 오른쪽(right)으로 모으는 함수를 작성함
• 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출해 위 작업을 반복함
• 함수는 왼쪽(left) + 피봇 + 오른쪽(right)을 리턴함

def qsort(data_list):
    if len(data_list) <= 1:
        return data_list
    
    left, right = [], []
    pivot = data_list[0] # 임의로 리스트 맨 앞의 데이터를 피봇으로 둔다
    
    for idx in range(1, len(data_list)):
        if data_list[idx] < pivot:
            left.append(data_list[idx])
        else:
            right.append(data_list[idx])
    
    return qsort(left) + [pivot] + qsort(right)
    
my_list = [29, 10, 14, 37, 12]
print(qsort(my_list))

# [10, 12, 14, 29, 37]

 

위의 코드를 리스트 내포(list comprehension)를 사용해서 더 깔끔하게 작성할 수 있다.

def qsort(data_list):
    if len(data_list) <= 1:
        return data_list
    
    left, right = [], []
    pivot = data_list[0] # 임의로 리스트 맨 앞의 데이터를 피봇으로 둔다
    
    left = [item for item in data_list[1:] if item < pivot]
    right = [item for item in data_list[1: ] if pivot <= item]
    
    return qsort(left) + [pivot] + qsort(right)
    
my_list = [29, 10, 14, 37, 12]
print(qsort(my_list))

# [10, 12, 14, 29, 37]

 

시간 복잡도

• 병합 정렬과 유사, 시간 복잡도는 $O(nlogn)$
• 맨 처음 피봇이 가장 크거나, 가장 작으면 모든 데이터를 비교하는 최악의 상황이 발생 👉 $O(n^{2})$