개발자 서류 / 면접 준비 #4 - 정렬 뽀시기

정렬 알고리즘은 데이터의 양, 정렬된 정도, 최적/ 평균/ 최악 조건에서의 성능, 메모리 사용 등 상황에 맞게 쓰인다.
(어떤 것이 최고라고 말할 수 없음)

🔎 버블 정렬

시간 복잡도 O(n^2)

코드- 파이썬

def bubble_sort(lst):
    LEN = len(lst)
    for last_idx in range(LEN-2, 0, -1):  # 각 턴의 마지막 인덱스
        is_swap = False  # 최적화
        for l_idx in range(0, last_idx+1):
            if lst[l_idx] > lst[l_idx+1]:
                lst[l_idx], lst[l_idx+1] = lst[l_idx+1], lst[l_idx]
                is_swap = True
        if not is_swap:  # swap이 일어나지 않았으면 정렬 완료상태
            return lst
    return lst

🔎 선택 정렬

시간 복잡도 O(n^2)

맞바꾸는 횟수는 O(n)이기 때문에 복사 연산이 매우 느린 경우 적합

코드- 파이썬

def select_sort(lst):
    LEN = len(lst)
    for cur_idx in range(0, LEN-1):  # 최소값을 위치시킬 인덱스
        search_start, min_idx = cur_idx+1, cur_idx
        for search_idx in range(search_start, LEN):
            if lst[search_idx] < lst[min_idx]:
                min_idx = search_idx
        lst[cur_idx], lst[min_idx] = lst[min_idx], lst[cur_idx]
    return lst

🔎 삽입 정렬

시간 복잡도 O(n^2)

이미 정렬된 데이터 집합에 대해 매우 효율적

코드- 파이썬

def insert_sort(lst):
    LEN = len(lst)
    for search_start in range(1, LEN):  # 탐색 시작 인덱스
        while search_start > 0:
            if lst[search_start] < lst[search_start-1]:
                lst[search_start], lst[search_start - 1] \
                    = lst[search_start-1], lst[search_start]
                search_start -= 1
            else:
                break
    return lst

🔎 퀵 정렬

시간 복잡도 O(nlogn)

분할 정복 알고리즘
최악의 경우 - O(n^2) ; pivot 값이 맨 왼쪽값으로 설정되고 정렬되어 있는 경우

코드- 파이썬

def quick_sort(lst):
    LEN = len(lst)
    if LEN <= 1:
        return lst
    middle = len(lst) // 2  # 최악의 케이스를 막기 위해  pivot을 middle로 설정
    pivot = lst[middle]
    rest = lst[:middle] + lst[middle+1:]
    left = [num for num in rest if num <= pivot]
    right = [num for num in rest if num > pivot]
    return quickSort(left) + [pivot] + quickSort(right)

참고 : 최적화된 퀵정렬
인덱스 두개를 사용하여 탐색 후 맞바꿈

🔎 병합 정렬

시간 복잡도 O(nlogn)

분할 정복 알고리즘, 어떤 조건에서도 O(nlogn), 메모리에 전부 집어넣을 수 없는 데이터 집합 정렬 시 유용

코드- 파이썬

def merge(left, right):
    merged = []
    while left or right:
        # left나 right 가 비었을 때
        if not left:
            merged += right
            return merged
        elif not right:
            merged += left
            return merged
        # left나 right 첫번째 원소값 비교
        if left[0] < right[0]:
            merged += [left[0]]
            left = left[1:]
        else:
            merged += [right[0]]
            right = right[1:]
    return merged


def merge_sort(lst):
    LEN = len(lst)
    if LEN <= 1:
        return lst
    middle = len(lst) // 2
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    return merge(left, right)

---

💡   참고 : 정렬 관련 문제

팬 케이크 뒤집기 문제

• 맨 아래부터 차례로 정렬한다.
• 제일 큰 팬케이크가 맨아래 오는 경우는 맨위로 위치시킨 후 뒤집는 경우.
• 최악의 시간 복잡도 (2n-3) : 제일 큰 팬케이크를 찾는 경우를 O(1)로 보았을 때
• 마지막은 뒤집을 필요 없고 두개 남았을 때도 두번 뒤집을 일이 없으니 2n에서 3번을 빼준다.