[알고리즘][개념] Selection sort, Insertion Sort, Merge Sort, Quick sort

정렬 알고리즘은 사실 실제로는 코테 때 나는 아직 사용해본적은 없지만 수업 1주차 때 관련 내용이 나오기도 했고, 간단히 코드와 원리, 시간복잡도에 관해 이야기해보려고 한다. 

 

기본적으로 이 글에서는 오름차순으로 정렬된 배열이 정렬 되어있다고 할 것이다. 

https://hsp1116.tistory.com/33 을 참고하여 작성하였습니다.

Selection Sort(선택 정렬)

선택 정열은 이름 그대로 배열을 처음부터 끝까지 훑으면서 가장 작은 (또는 큰) 값을 선택하여 맨 앞자리 (또는 뒷자리)로 옮기는 방식이다. 

출처 위키피디아

 

• 시간 복잡도: O(n^2) (최선, 평균, 최악 모두)
• 장점: 구현이 매우 간단합니다.
• 단점: 시간 복잡도가 높아 큰 데이터셋에는 비효율적입니다.

 

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        # i+1부터 끝까지 중에서 최소값 찾기
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 최소값을 현재 위치 i와 교환
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Example usage:
# arr = [64, 25, 12, 22, 11]
# print(selection_sort(arr))  # Output: [11, 12, 22, 25, 64]

Insertion sort(삽입 정렬)

 

삽입 정렬은 이미 정렬된 부분 배열에 새로운 원소를 적절한 위치에 삽입하여 정렬하는 방식이다. 

기본 로직은 위의 그림과 같이 두번째 인덱스부터 시작하여 정렬된 list의 마지막 값과 비교하고 그보다 큰지 작은지를 확인하며(마지막이 아니어도 첫번째부터여도 괜찮음) 정렬한다. 

 

• 시간 복잡도: O(n^2) (최악), O(n) (최선)
• 장점: 데이터가 거의 정렬되어 있을 때 매우 효율적

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # 현재 key보다 큰 값들은 한 칸씩 뒤로 이동
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Example usage:
# arr = [12, 11, 13, 5, 6]
# print(insertion_sort(arr))  # Output: [5, 6, 11, 12, 13]

 

Bubble sort

매번 연속된 두개의 인덱스를 비교하여 정한 기준의 값을 뒤로 ㅈ넘겨 정렬한다. 오름차순으로 정렬하고자 할 경우, 비교시 마다 큰 값이 뒤로 이동하며, 1바퀴를 모두 돌아야 1회 끝난다. 이후 가장 큰 값이 맨 뒤에 저장된다.  (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

 

• 시간 복잡도: O(n^2) (최선, 평균, 최악 모두)
• 장점: 구현이 매우 간단합니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False  # 이번 패스에서 교환이 일어났는지 체크
        for j in range(0, n - i - 1):  # 이미 정렬된 마지막 i개의 요소는 비교하지 않음
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 두 요소 교환
                swapped = True
        if not swapped:  # 교환이 일어나지 않았다면 정렬이 완료된 것이므로 종료
            break
    return arr

# Example usage:
# arr = [64, 34, 25, 12, 22, 11, 90]
# print(bubble_sort(arr))  # Output: [11, 12, 22, 25, 34, 64, 90]

 

Merge Sort

출처 wiki

 

 

분할 정복(Divide and conquer) 방식으로 서계된 알고리즘이다. 배열을 절반으로 나누어 각각 정렬한 후, 두 정렬된 배열을 병합하는 방식이다. 

보다 자세히는 계속 쪼개고, 쪼개 배열의 크기가 1과 같아질 때까지 분할한다. 이후 하나씩 합하며 정렬한다. 

분할 과정의 기본 로직은 다음과 같다.
① 현재 배열을 반으로 쪼깬다. 배열의 시작 위치와, 종료 위치를 입력받아 둘을 더한 후 2를 나눠 그 위치를 기준으로 나눈다.
② 이를 쪼갠 배열의 크기가 0이거나 1일때 까지 반복한다.

합병 과정의 기본 로직은 다음과 같다.
① 두 배열 A,B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i,j로 가정하자.
② i에는 A배열의 시작 인덱스를 저장하고, j에는 B배열의 시작 주소를 저장한다.
③ A[i]와 B[j]를 비교한다. 오름차순의 경우 이중에 작은 값을 새 배열 C에 저장한다. 
    A[i]가 더 컸다면 A[i]의 값을 배열 C에 저장해주고, i의 값을 하나 증가시켜준다.
④ 이를 i나 j 둘중 하나가 각자 배열의 끝에 도달할 때 까지 반복한다.
⑤ 끝까지 저장을 못한 배열의 값을, 순서대로 전부 다 C에 저장한다.
⑥ C 배열을 원래의 배열에 저장해준다.

• 시간 복잡도: O(n log n) (최선, 평균, 최악 모두)
• 장점: 안정적인 정렬이며 시간 복잡도가 낮습니다.
• 단점: 추가적인 메모리 공간이 필요합니다.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)  # 왼쪽 절반 정렬
        merge_sort(right_half)  # 오른쪽 절반 정렬

        # 병합 과정
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 남아있는 요소들 병합
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# Example usage:
# arr = [38, 27, 43, 3, 9, 82, 10]
# print(merge_sort(arr))  # Output: [3, 9, 10, 27, 38, 43, 82]

 

Quick Sort

 

퀵정렬 또한 분할 정복을 이용한 알고리즘이다. 배열에서 하나의 원소(피벗)를 선택하고, 피벗을 중심으로 정렬을 한다. 즉, 피벗을 기준으로 큰 값은 피봇의 오른쪽에, 작은 것은 왼쪽에 둔다. 재귀적으로 정렬한다. 

 

기본 로직은 다음과 같다.

① pivot point로 잡을 배열의 값 하나를 정한다. 보통 맨 앞이나 맨 뒤, 혹은 전체 배열 값 중 중간값이나나 랜덤 값으로 정한다.

② 분할을 진행하기에 앞서, 비교를 진행하기 위해 가장 왼쪽 배열의 인덱스를 저장하는 left 변수, 가장 오른쪽 배열의 인덱스를 저장한 right변수를 생성한다. 

③ right부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며. 비교한 배열값이 pivot point보다 크면 right를 하나 감소시키고 비교를 반복한다.

    pivot point보다 작은 배열 값을 찾으면, 반복을 중지한다.

④ 그 다음 left부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며. 비교한 배열값이 pivot point보다 작으면 left를 하나 증가시키고 비교를 반복한다.

    pivot point보다 큰 배열 값을 찾으면, 반복을 중지한다.

⑤ left 인덱스의 값과 right 인덱스의 값을 바꿔준다.

⑥ 3,4,5 과정을 left<right가 만족 할 때 까지 반복한다.

⑦ 위 과정이 끝나면 left의 값과 pivot point를 바꿔준다.

⑧ 맨 왼쪽부터 left - 1까지, left+1부터 맨 오른쪽까지로 나눠 퀵 정렬을 반복한다.

• 시간 복잡도: O(n log n) (평균), O(n^2) (최악)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

# Example usage:
# arr = [10, 7, 8, 9, 1, 5]
# print(quick_sort(arr))  # Output: [1, 5, 7, 8, 9, 10]