[Algorithms/python] 정렬 알고리즘 총정리 (quick sort, merge sort, )

정렬

알고리즘최선 시간 복잡도평균 시간 복잡도최악 시간 복잡도공간 복잡도안정성비고

버블 정렬	O(n)	O(n^2)	O(n^2)	O(1)	안정	비효율적인 경우가 많음
선택 정렬	O(n^2)	O(n^2)	O(n^2)	O(1)	불안정	간단하지만 비효율적
삽입 정렬	O(n)	O(n^2)	O(n^2)	O(1)	안정	작은 데이터 세트에서 효율적
합병 정렬	O(n log n)	O(n log n)	O(n log n)	O(n)	안정	대규모 데이터에 효율적
퀵 정렬	O(n log n)	O(n log n)	O(n^2)	O(log n)	불안정	대부분의 경우 가장 빠름
힙 정렬	O(n log n)	O(n log n)	O(n log n)	O(1)	불안정	메모리 사용량이 적음
계수 정렬	-	O(n + k)	O(n + k)	O(k)	안정	k는 입력 데이터의 범위. 작은 범위의 정수에 적합
기수 정렬	-	O(nk)	O(nk)	O(n + k)	안정	k는 숫자의 최대 자릿수. 큰 숫자에 효율적

• python은 sort() 또는 sorted() 함수로 정렬 가능하다 -> O(nlogn)의 시간복잡도
• 카운팅 정렬
  • 주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘
• sorted 다중 조건
  • f = sorted(dic.items(), key = lambda x : (x[0], -x[1]))

안정 정렬 / 불안정 정렬

• 안정 정렬(Stable Sort): 동일한 값을 가진 원소들의 상대적 순서 유지. 복잡한 데이터 정렬에 유용.
  • 예: 병합 정렬, 삽입 정렬, 버블 정렬.
• 불안정 정렬(Unstable Sort): 동일한 값의 원소들 사이 순서 보장하지 않음. 구현 단순, 속도 빠를 수 있음.
  • 예: 퀵 정렬, 힙 정렬, 선택 정렬.

정렬 알고리즘

1. Quick Sort

• 불안정 정렬
• 분할 정복
• 시간 복잡도
  • O(NlogN) : 대부분의 경우 제일 빠름
  • 최악의 경우 O(N^2)
    • pivot이 최솟값 혹은 최댓값인 경우에는 배열이 분할되지 않게 된다.
• 퀵 정렬의 핵심은 pivot을 어떻게 선정하느냐
• 아래의 코드는 3-way Quick Sort, 중복된 값이 많을 때 효율적임.
  • 기존의 퀵소트와는 달리, 3-분할 퀵소트는 피벗과 같은 원소들을 별도로 처리하기 때문에, 중복된 값이 많아도 불균형한 분할을 피할 수 있어 성능이 개선됨.

def quick_sort(arr):
    if len(arr)<=1:
        return arr 
    
    pivot = arr[len(arr)//2] # pivot을 중앙값으로 선정 
    left = [i for i in arr if i < pivot] # pivot보다 값이 작은 경우 왼쪽 
    middle = [i for i in arr if i==pivot] # pivot과 값이 같은 경우 가운데
    right =[i for i in arr if i> pivot] # pivot보다 값이 큰 경우 오른쪽 
    return quick_sort(left)+middle+quick_sort(right)
    

arr = list(map(int,input().split()))
sorted_arr = quick_sort(arr)
print(sorted_arr)

2. Merge Sort

• 안정 정렬
• 분할 정복
• 시간복잡도
  • O(NlogN)
  • 최악의 경우 O(NlogN)
• 안정정렬이기에 대규모 데이터에 효율적이지만 배열 복사로 인해서 메모리 사용량 높음

def merge_sort(arr): 
    if len(arr)<2: 
        return arr
        
    # 1. 중간값을 기준으로 분할하여 재귀 수행 
    mid = len(arr)//2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])
    
    # 2. 두 arr 돌면서 더 작은 값을 입력해주기 
    merged_arr = []
    l, h = 0, 0
    while l<len(low_arr) and h<len(high_arr): # 둘 중 하나 다 돌 때까지 
        if low_arr[l]<high_arr[h]:
            merged_arr.append(low_arr[l])
            l+=1
        else : 
            merged_arr.append(high_arr[h])
            h+=1
    
    # 하나 먼저 다 끝났을 경우 
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr
    
arr = list(map(int, input().split()))
sorted_arr = merge_sort(arr)
print(sorted_arr)

3. Heap Sort

• 불안정 정렬
• heapq 사용
• 시간 복잡도
  • O(NlogN)
  • 최악의 경우 O(NlogN)
• 메모리 사용량 적음

from heapq import *

def heap_sort(arr): 
    heapify(arr)
    sorted_arr= []
    while arr:
        sorted_arr.append(heappop(arr))
    return sorted_arr
    
arr =list(map(int,input().split()))
sorted_arr = heap_sort(arr)
print(sorted_arr)

4. Insertion Sort

• 안정 정렬
• 시간 복잡도
  • O(n^2)
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 

  

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

 

5. Bubble Sort

• 안정 정렬
• 시간 복잡도
  • O(n^2)
• 인접한 두 개의 원소 비교해가면서 옮기기

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

 

 

6. Selection Sort

• 불안정 정렬
• 시간 복잡도
  • O(n^2)
• 최솟값 찾아서 앞에 넣고, 그 다음 부분부터 다시 찾아나가기 

  

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

 

 

https://github.com/AAISSJ/AlgorithmStudy/tree/main/2024/Sort

AlgorithmStudy/2024/Sort at main · AAISSJ/AlgorithmStudy