정렬 알고리즘 - 퀵/합병

정렬 알고리즘

• 버블 정렬(Bubble Sort)
• 선택 정렬(Selection Sort)
• 삽입 정렬(Insertion Sort)
• 퀵 정렬(Quick Sort)
• 합병 정렬(Merge Sort)

퀵 정렬

• O(nlogn) 시간 복잡도를 가진다.
• 재귀함수를 활용한다.

과정

• 리스트의 한 요소를 선택해 pivot으로 설정한다.
• pivot은 첫 번째 요소, 마지막 요소, 중앙에 위치한 요소 등 아무거나 선택 가능하다.
• pivot을 중심으로 pivot보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 구성된다.

Python 구현

# 퀵 정렬
def quicksort(array):
    # 원소의 개수가 0 or 1이면 이미 정렬된 상태이므로 배열 그대로 반환
    if len(array) <= 1:
        return array

    else:
        pivot = array[0] # 첫 번째 원소를 기준값(pivot)으로 사용
        less, greater = [], [] # pivot보다 작은 거, pivot보다 큰 거

        # array[1:] : pivot 포함하지 않아야 함
        for i in array[1:]:
            if i <= pivot:
                less.append(i)
            else: greater.append(i)
        
        # 재귀함수 사용하여 less list와 greater list 같은 과정 반복
        return quicksort(less) + [pivot] + quicksort(greater)

# 결과
list1 = [1, 3, 5, 7, 9, 11, 13, 11]
list2 = [28, 13, 9, 30, 1, 48, 5, 7, 15]
list3 = [2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]

[1, 3, 5, 7, 9, 11, 11, 13]
[1, 5, 7, 9, 13, 15, 28, 30, 48]
[1, 1, 2, 2, 4, 4, 4, 5, 6, 6, 7, 7, 10, 11, 13, 15]

합병 정렬

• O(nlogn) 시간 복잡도를 가진다.
• 재귀함수를 활용한다.

과정

Python 구현

# 합병 정렬
def merge_sort(arr):
    # 원소의 개수가 0 or 1이면 이미 정렬된 상태이므로 배열 그대로 반환
    if len(arr) < 2 :
        return arr

    mid = len(arr) // 2 
    left =  merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    merged_arr = []
    low = high = 0

    while low < len(left) and high < len(right):
        if left[low] < right[high]:
            merged_arr.append(left[low])
            low += 1
        else:
            merged_arr.append(right[high])
            high += 1

    merged_arr += left[low:]
    merged_arr += right[high:]
    
    return merged_arr

활용 예시

프로그래머스 Level1 K번째 수

def solution(array, commands):
    answer = []
    for c in commands:
        answer.append(sorted(array[c[0]-1:c[1]])[c[2] - 1])
        
    return answer

프로그래머스 Level2 가장 큰 수

• 4번 반복해주고 4자리 수만 사용하는 것이 핵심이다.
• (예) [‘6’, ‘10’, ‘2’] -> [‘6666’, ‘1010’, ‘2222’] -> ‘6666’ > ‘2222’ > ‘1010’ -> ‘6210’

  def solution(numbers):
    numbers = list(map(str, numbers))
    nums = sorted(numbers, key=lambda x: (x * 4)[:4], reverse=True)
    answer = ''.join(nums)
      
    if answer[0] == '0':
        return '0'
    return answer
  

프로그래머스 Level2 H-Index

• H번 이상 인용된 논문이 H번 이상이어야 하므로, 전체 논문 수 n보다 커질 수 없다..

  def solution(citations):
    citations = sorted(citations, reverse=False)
    length = len(citations)
      
    for i in range(len(citations)):
        if citations[i] >= length - i:
            return length - i
    return 0