선택 정렬

: 매번 "가장 작은 것 선택" 후 앞의 데이터와 swap

구현

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

	#python에서의 swap
	arr[min_idx], arr[j] = arr[j], arr[min_idx]

시간복잡도

(가장 작은 수 찾기 : N-1 )*(가장 작은수 찾기 위해 매번 비교: N+(N-1)+(N-2)+ ... + 2)

≈ N*(N+1) → O(N^2)

→ 비효율적인 정렬방법

삽입 정렬

: 데이터를 하나씩 확인하면서 적절한 위치에 삽입

→ 해당 위치 앞까지는 이미 정렬되어 있다고 가정

구현

for i in range(1, len(arr)):
    for j in range(i, 0, -1):
        if arr[j-1] > arr[j]:
            arr[j-1], arr[j] = arr[j], arr[j-1]
        else:
            break

→ 데이터가 거의 정렬되어 있을때 효율적

시간복잡도

O(N^2)

→ 거의 정렬된 상태에서는 최대 O(N)

퀵 정렬

: 기준 데이터 설정 후 해당 기준보다 크고 작은 데이터 위치 변경

→ 첫번째 데이터를 피봇으로 삼음

구현

def quick_sort(arr, start, end):
    #원소가 1개인 경우 종료
    if start >= end:
        return
    #맨 첫번째원소를 피봇으로
    pivot = start
    left = start+1
    right = end

    while left <= right:
        #피봇보다 큰 데이터 찾을때까지
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        #피봇보다 작은 데이터 찾을때까지
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        
        #엇갈린 경우 작은 데이터와 피봇 교체
        if left > right:
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else:
            arr[left], arr[right] = arr[right], arr[left]
        
    #피봇 기준 왼쪽, 오른쪽 부분에 대해 정렬 수행
    quick_sort(arr, start, right-1)
    quick_sort(arr, right+1, end)

→ 더 파이썬스럽게

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]
    tail = arr[1:] #피봇을 제외한 리스트

    left_side = [x for x in tail if x<=pivot]
    right_side = [x for x in tail if x>pivot]
    return quick_sort(left_side)+[pivot]+quick_sort(right_side)

시간복잡도

최악 : O(N^2) → 이미 정렬된 데이터에 대해서

평균: O(NlogN)

계수 정렬

: 데이터의 크기 범위가 제한되어 정수형태로 표현 가능할 때 사용

• abs(max(arr)-min(arr)) < 1000000인 경우
• 비교 기반 알고리즘이 아님

유리한 경우

• 데이터의 크기 한정
• 데이터가 많이 중복

구현

for i in range(len(arr)):
    count[arr[i]] +=1 

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

arr : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

1. 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담기는 리스트 생성
   

2. 데이터를 하나씩 확인하며 데이터 값과 동일한 인덱스 데이터 1씩 증가
   

3. 리스트의 첫번째 데이터부터 값만큼 인덱스 출력

시간복잡도

데이터의 크기 N, 최대값의 크기 K에 대해 O(N+K)

공간복잡도

비효율적인 경우 존재

e.g. 0, 999999 2개의 데이터 존재시 리스트의 크기 100만개