[Jungle] Week1. 정렬 개념

정글 week01. 핵심 키워드

정렬 개념

• 버블 정렬
• 삽입 정렬
• 선택 정렬
• 병합 정렬
• 셸 정렬
• 퀵 소트
• 힙 소트

삽입 정렬(Insertion Sort)

from typing import MutableSequence

def insertion_sort(a: MutableSequence) -> None:
    n = len(a)
    for i in range(1,n):
        j = i
        tmp = a[i]
        while j > 0 and a[j-1] > tmp:
            a[j] = a[j-1]
            j -=1
        a[j] = tmp

퀵 정렬(Quick Sort)

빠른 속도의 분할 정복 알고리즘 중 하나

• 피봇을 설정하고 피봇보다 큰 값, 작은 값으로 분리하여 정렬 -> 병합 정렬과 달리 리스트를 비균등하게 분할

퀵 정렬은 배열을 나눌 때 피벗을 어떤 값으로 선택하느냐에 따라 성능이 달라진다 -> 최악 O(N^2), best case: O(nlogn)

퀵 정렬을 많이 사용하는 이유?

퀵 소트는 동일한 배열 내에서 자리를 이동 시킴. 제일 처음에 배열에 접근할 때만 실제 메모리에서 배열을 가져옴. 이후에는 캐시로 배열에 접근 가능 -> 메모리에 접근할 때보다 훨씬 빠른 접근이 가능하다.
추가적인 공간을 할당하는 시간이 없다.
그리고 한번 결정한 피벗은 이후 연산에서 제외되므로 분할을 할 수록 계산 해야하는 데이터의 수가 점점 줄어든다.

def qsort(arr, left, right):
	pl = left
    pr = right
    pivot= arr[(left+right)//2]
    
    while pl <= pr:
    	while arr[pl] < pivot:
        	pl +=1 
        while arr[pr] > pivot:
        	pr -=1 
     	if pl <= pr:
        	arr[pl], arr[pr] = arr[pr], arr[pl]
            pl +=1 
            pr -=1
    if left < pr: qsort(arr, left, pr)
    if pl <right: qsort(arr, pl, right) 

병합 정렬(Merge Sort)

크기가 1인 배열로 분할하고 합병하면서 정렬을 진행하는 분할/정복 알고리즘

def merge_sort(arr):
    if len(arr)<=1:
        return arr

    #리스트를 반으로 나누기
    mid = len(arr)//2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half )


def merge(left,right):
    result = []
    left_idx, right_idx=  0,0

    #왼쪽과 오른쪽 리스트 합병
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            result.append(left[left_idx])

            left_idx +=1

        else:
            result.append(right[right_idx])
            right_idx +=1

    result.extend(left[left_idx:])
    result.extend(right[right_idx:])

    return result

arr = [3, 7, 2, 5, 1, 4, 6]
sorted_arr = merge_sort(arr)
print("정렬된 배열:", sorted_arr)