[알고리즘] 정렬 알고리즘 파이썬 구현 (버블정렬/선택정렬/삽입정렬/병합정렬/퀵정렬)

1. 버블 정렬

시간복잡도: O(n^2)

# 기본 구현

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                
# 최적화: 스왑이 일어났는지 여부를 체크해줌으로써 정렬이 이미 완료되어있는 경우(즉 스왑이 일어나지 않은 경우)
# 더 효율적으로 작동

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        swapped = False
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            swapped = True
        if not swapped:
            break

참고 코드: https://www.daleseo.com/sort-bubble/

[알고리즘] 거품 정렬 - Bubble Sort (Python, Java)

2. 선택 정렬

시간복잡도: O(n^2)

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

참고 코드: https://www.daleseo.com/sort-selection/

[알고리즘] 선택 정렬 - Selection Sort (Python, Java)

3. 삽입 정렬

시간복잡도

• 최악의 경우: O(n^2)
• 최선의 경우: O(n) (이동 없이 1번의 비교만으로 끝)

def insertion_sort(arr):
    for i in range(1, len(arr)):
        for j in range(i - 1, -1, -1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

참고 코드: https://www.daleseo.com/sort-insertion/

[알고리즘] 삽입 정렬 - Insertion Sort (Python, Java)

4. 병합 정렬

시간복잡도: O(nlogn)

def merge_sort(arr):

    def sort(unsorted_arr):
        if len(unsorted_arr) <= 1:
            return unsorted_arr
            
        mid = len(unsorted_arr) // 2
        left = unsorted_arr[:mid]
        right = unsorted_arr[mid:]
        
        return merge(sort(left), sort(right))
        
    def merge(left, right):
        sorted_arr = []
        i, j = 0, 0
        
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                sorted_arr.append(left[i])
                i += 1
            else:
                sorted_arr.append(right[j])
                j += 1
                
        while i < len(left):
            sorted_arr.append(left[i])
            i += 1
        
        while j < len(right):
            sorted_arr.append(right[j])
            j += 1
            
        return sorted_arr
        
    return sort(arr)

참고 코드: https://codingsmu.tistory.com/133

파이썬으로 구현하는 병합정렬(Merge Sort)

https://www.daleseo.com/sort-merge/

[알고리즘] 병합 정렬 - Merge Sort (Python, Java)

5. 퀵 정렬

시간복잡도

• 평균: O(nlogn)
• 최악: O(n^2) (기준값pivot이 한쪽 끝에 쏠려 있을 경우)

def quick_sort(arr, start, end): # start, end는 arr의 시작과 끝 인덱스

    # 원소가 1개인 경우 종료
    if start >= end:
        return
        
    pivot = start
    # start, end는 고정이므로 계속 +1, -1 될 가변적인 변수 left와 right를 새로 선언해줌
    left = start + 1
    right = end
    
    # left, right가 엇갈릴 때까지
    while left <= right:
    
        # pivot값보다 큰 값이 나올 때까지 left += 1
        while arr[left] <= arr[pivot] and left <= end:
            left += 1
        
        # pivot 값보다 작은 값이 나올 때까지 right -= 1
        while arr[right] >= arr[pivot] and right > start:
            right -= 1
            
        # 엇갈린 경우 (바깥 while loop 빠져나가기 직전에) 작은 데이터와 pivot 값 교체, 즉 pivot을 중간으로 보냄
        # pivot과 교체해주면 피벗 기준으로 앞은 작은 값들, 뒤는 큰 값들만 모임
        if left > right:
            arr[pivot], arr[right] = arr[right], arr[pivot] # 엇갈렸으므로 left 원소보다 right 원소가 작아진 상태
        
        # pivot값보다 큰 left값과 작은 right값 서로 스왑
        else:
            arr[left], arr[right] = arr[right], arr[left]
            
    # 현재 right 인덱스에는 pivot 값이 있는 상태
    quick_sort(arr, start, right - 1)
    quick_sort(arr, right + 1, end)
    
quick_sort(arr, 0, len(arr) - 1)

참고 코드:

https://youtu.be/KGyK-pNvWos