2024 자료구조개론 & 알고리즘개론 정리 - 5. Sorting

 

 

2024 자료구조개론 & 알고리즘개론 정리 - 5. Sorting 

 

 

 

• 1. 배열과 링크드리스트 
• 2. Hash Table
• 3. Queue & Stack 
• 4. Tree & Graph 
• 5. Sorting 
• 6. Recursion 
• 7. 최적화 기법 (DP, Greedy, Divide & Conquer)

 

 

 

생각해보니까 목차에 Recursion이 먼저 오는 게 맞았을지도 ... ㅎㅎㅎ 

 

 

 

 

---

 

 

• 정렬은 크게 안정 정렬, 불안정 정렬이 있을 수 있겠다 
  • 안정 정렬은 동일한 숫자의 데이터가 여러 개 들어왔을 때, 그 들어온 순서가 변하지 않는 방식으로 정렬된다 
    • 합병 정렬, 삽입 정렬, 버블 정렬이 그 예이다. 
  • 불안정 정렬은 그 순서를 보장하지 않는다 
    • 퀵 정렬, 힙 정렬, 선택 정렬 

 

 

 

퀵 정렬 

 

• 불안정 정렬 
• 시간 복잡도
  • 평균 시간 복잡도는 O(NlogN)
  • 최악의 경우 O(N^2) : pivot의 최솟값이거나 최댓값일 떄 
  • 공간 복잡도 O(logN) : 매번 두 개로 쪼개지기 때문에 
• 아래의 코드는 3-way Quick Sort, 중복된 값이 많을 때 효율적임.
  • 기존의 퀵소트와는 달리, 3-분할 퀵소트는 피벗과 같은 원소들을 별도로 처리하기 때문에, 중복된 값이 많아도 불균형한 분할을 피할 수 있어 성능이 개선됨

 

def quick_sort(arr):
    if len(arr)<=1: 
        return arr 
    
    pivot = arr[len(arr)//2]
    left = [i for i in range(a) if i<pivot]  
    middle = [i for i in range(a) if i==pivot]  
    right = [i for i in range(a) if i>pivot]  
    return quick_sort(left)+middle+quick_sort(right)

 

 

 

합병 정렬 

 

• 안정 정렬 
• 시간 복잡도 
  • 평균 O(NlogN)
  • 최악 O(NlogN)
  • 공간복잡도 O(N) - 추가적인 배열 하나를 더 쓰기 때문에 

def merge_sort(arr):
    if len(arr)<=1:
        return arr 
        
    mid = len(arr)//2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    
    merged_arr = []
    l, r = 0, 0 
    while l<len(left_arr) and r<lend(right_arr):
        if left_arr[l]< right_arr[r]:
            merged_arr.append(left[l])
            l+=1
        else: 
            merged_arr.append(right_arr[r])
            r+=1
    merged_arr+=low_arr[l:]
    merged_arr+=right_arr[r:]
    
    return merged_arr

 

 

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)

 

 

 

Bubble Sort 

• 안정 정렬
• 시간 복잡도
  • O(n^2)
• 인접한 두 개의 원소 비교해가면서 옮기기
  • 정렬 과정에서 더 큰 요소들이 배열의 끝으로 "버블처럼" 떠오른다는 데에서 유래

 

def bubble_sort(arr): 
    for i in range(len(arr)): # N번 반복 
        for j in range(len(arr)-1-i): # 오른쪽으로는 하나씩 줄여가면서 탐색해야 되니까 
            if arr[j]> arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

 

 

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

 

 

 

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