1일1개 (64) - 안정 정렬

1일 1개념정리 24.08.09.금 ~ 

 

큰 결정에 큰 동기가 따르지 않을 때도 있다. 하지만 큰 결심이 따라야 이뤄낼 수 있다.

무조건 무조건 1일 1개의 개념 정리하기 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!

---

#64. 안정 정렬

어제는 정렬 알고리즘의 기본 개념 중, 안정성과 제자리성에 대해서 알아보았다. 그 중 오늘은 안정성을 만족하는 정렬들에 대해서 알아보자. 삽입, 버블, 합병 뿐만 아니라 계수, 기수 정렬도 있지만 뒤에 2개는 약간 마이너한 느낌이 들어서..... 앞에 3개만 정리해보려 한다. 시간이 없는 것은 아님

 

 

	제자리성	안정성	최선 시간복잡도	평균 시간복잡도	최악 시간복잡도
삽입 정렬	O	O	O(n)	O(n²)	O(n²)
선택 정렬	O	X	O(n²)	O(n²)	O(n²)
버블 정렬	O	O	O(n)	O(n²)	O(n²)
셸 정렬	O	X	O(n)	O(n^1.5)	O(n²)
퀵 정렬	O	X	O(n log n)	O(n log n)	O(n²)
병합 정렬	X (메모리 사용)	O	O(n log n)	O(n log n)	O(n log n)
힙 정렬	O	X	O(n log n)	O(n log n)	O(n log n)
기수 정렬	X (메모리 사용)	O	O(nk)	O(nk)	O(nk)
계수 정렬	X (메모리 사용)	O	O(n + k)	O(n + k)	O(n + k)

 

삽입 정렬 (Insertion Sort)

배열을 두번째 인덱스 부터 시작해서 앞의 원소들과 비교하며 정렬된 부분으로 삽입하는 것이다.

 

EX) [4, 2, 7, 1, 3]

1. 두번째 인덱스부터 시작함. 1번째 인덱스를 "정렬된 부분"으로 표현.
2. 두 번째 원소(2)를 앞의 정렬된 부분에 삽입 = [2, 4, 7, 1, 3]
3. 세 번째 원소(7)를 정렬된 부분에 넣으려고 보니, 이미 내 자리에 와있음. = [2, 4, 7, 1, 3]
4. 네 번째 원소(1)를 정렬된 부분에 삽입 = [1, 2, 4, 7, 3]
5. 다섯 번째 원소(3)를 정렬된 부분에 삽입 = [1, 2, 3, 4, 7]

def insertion_sort(arr):
    # 두 번째 요소부터 시작하여 정렬된 부분에 삽입
    for i in range(1, len(arr)):
        key = arr[i]  # 현재 요소를 임시 변수에 저장
        j = i - 1

        # 정렬된 부분에서 현재 요소보다 큰 요소를 오른쪽으로 이동
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # 현재 요소를 정렬된 부분의 적절한 위치에 삽입
        arr[j + 1] = key

    return arr

arr = [4, 2, 7, 1, 3]
sorted_arr = insertion_sort(arr)
print("삽입 정렬된 배열:", sorted_arr)

 

버블 정렬 (Bubble Sort)

배열의 첫 번째 인덱스부터 시작하여 "인접한" 두 요소를 비교하며 정렬하는 방식이다. 같은 값의 원소는 위치를 바꾸지 않으므로 안정성을 만족한다. 매 회전마다 최대값이 뒤로 이동한다는 것이 큰 특징 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 5,4,3,2,1을 정렬하면 1번째 정렬때 5가 맨 뒤로 가고, 두번째 정렬땐 4가 뒤로 가서 ~~~ 4, 5가 되고 그 다음에는 ~~~ 3, 4, 5가 되고 .... 이런 식

 

EX) [5, 3, 8, 4, 2]

1) 첫번째 회전.

• 5와 3 비교 → [3, 5, 8, 4, 2]
• 5와 8 비교 → [3, 5, 8, 4, 2]
• 8과 4 비교 → [3, 5, 4, 8, 2]
• 8과 2 비교 → [3, 5, 4, 2, 8] (8이 맨 뒤로 이동)

2) 두번째 회전.

• 3과 5 비교 → [3, 5, 4, 2, 8]
• 5와 4 비교 → [3, 4, 5, 2, 8]
• 5와 2 비교 → [3, 4, 2, 5, 8] (5가 뒤로 이동)

3) 세번째 회전.

• 3과 4 비교 → [3, 4, 2, 5, 8]
• 4와 2 비교 → [3, 2, 4, 5, 8] (4가 뒤로 이동)

4) 네번째 회전.

• 3과 2 비교 → [2, 3, 4, 5, 8] (완료)

def bubble_sort(arr):
    n = len(arr)
    # 배열의 끝까지 반복
    for i in range(n):
        # 인접한 요소들을 비교하고 교환
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # 순서가 잘못된 경우 두 요소를 교환
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return arr

# 예제 실행
arr = [5, 3, 8, 4, 2]
sorted_arr = bubble_sort(arr)
print("버블 정렬된 배열:", sorted_arr)

 

병합 정렬 (Merge Sort)

병합 정렬은 배열을 재귀적으로 반으로 나누고, single element까지 나눈 뒤, 정렬된 두 부분을 병합하면서 전체 배열을 정렬해나가는 방식이다. "Divide and Conquer" 방식으로, 쪼개고 합치며 정복하는 것이다.

 

EX) [5, 2, 4, 7, 1, 3, 6]

1. 배열을 반으로 나눔 = [5, 2, 4, 7] / [1, 3, 6]
2. 나눈 배열을 다시 반으로 나눔 = [5, 2] / [4, 7] / [1, 3] / [6]
3. 단일 요소가 될 때까지 나눔 = [5] / [2] / [4] / [7] / [1] / [3] / [6]
4. 병합하며 정렬한다. 5랑 2 비교했더니 2가 크니깐 2, 5로 합쳐주는 방식, 나머지도 똑같음. = [2, 5] / [4, 7] / [1, 3] / [6] ////// 요기 합쳐지는 과정이 이해 안될 수 있는데, 아래 코드로 보자. [2,5]랑 [4,7] 합칠 때 첫번째 원소끼리 비교해서 2, 4중에 2가 작으깐 빈 리스트에 2를 넣는 방식이다. 그럼 [5]랑 [4,7]이 남았으니, 다시 첫번째 원소인 5랑 4를 비교한다. 4가 더 작으니깐 4를 넣어준다. 그럼 정렬 리스트는 [2,4]고 이제 남은 것은 [5], [7]이다. 이것도 같은 방식으로 정렬. 이런식으로 정렬한다. (합병시 매번 맨 앞의 원소끼리 비교.)
5. 계속 합쳐줌. 합칠 때 정렬함. = [2, 4, 5, 7] / [1, 3, 6]
6. 완료. [1, 2, 3, 4, 5, 6, 7]

def merge_sort(arr):
    # 배열의 길이가 1 이하이면 이미 정렬된 상태이므로 그대로 반환
    if len(arr) <= 1:
        return arr

    # 배열을 중간 지점에서 나누기
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 재귀적으로 좌우 반을 정렬
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    # 정렬된 좌우 반을 병합
    return merge(left_sorted, right_sorted)

def merge(left, right):
    # 병합된 결과를 저장할 배열
    result = []
    i = j = 0

    # 두 배열을 비교하며 작은 요소를 결과에 추가
    while 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

    # 남은 요소들을 결과 배열에 추가
    # 왼쪽 배열에 남은 요소가 있다면 추가
    while i < len(left):
        result.append(left[i])
        i += 1

    # 오른쪽 배열에 남은 요소가 있다면 추가
    while j < len(right):
        result.append(right[j])
        j += 1

    # 병합된 결과 반환
    return result

# 예제 실행
arr = [5, 2, 4, 7, 1, 3, 6]
sorted_arr = merge_sort(arr)
print("정렬된 배열:", sorted_arr)