알고리즘 정리 - 정렬

버블정렬(bubble sort)

n번의 라운드로 이뤄진 상황에서, 각 라운드마다 배열의 아이템을 한번씩 쭉 살펴봄
=> n번 검색
연달아 있는 2개의 아이템의 순서가 잘못되어 있는 경우 두 아이템을 바꾼다
=> O(n^2) 시간복잡도를 항상 가짐

# 버블 정렬
def bubblesort(arr):
	for i in range(1, len(arr)):
    	for j in range(0, len(arr)-1):
        	if arr[j] > arr[j+1]:
            	arr[j], arr[j+1] = arr[j+1], arr[j]

병합정렬(merge sort)

최선과 최악 모두 O(nlogn)의 시간복잡도를 가짐
대부분의 겨우 퀵정렬보다 느리지만 무엇보다 안정적임
분할 정복 알고리즘의 대표 예시

입력 값을 쪼갤 수 없을 때 까지 두 부분으로 분할함
그 후 두 숫자를 비교하여 정렬하며 합쳐나감

[38, 27, 43, 3, 9, 82, 10]
=> [38, 27, 43, 3] / [9, 82, 10]
=> [38, 27] / [43, 3] / [9, 82] / [10]
=> [27, 38] / [3, 43] / [9, 82] / [10]
=> [3, 27, 38, 43] / [9, 10, 82]
=> [3, 9, 10, 27, 38, 43, 82]

퀵정렬(quick sort)

피벗을 기준으로 좌우를 나눔(따라서 파티션 교환 정렬이라고 불리기도 함)
merge sort와 같이 분할 정복 알고리즘
피벗 이라는 개념을 더해 피벗보다 작으면 왼쪽, 크면 오른쪽과 같은 방식으로 파티셔닝 하며 쪼개 나감

def quicksort(arr, low, high):
	def partition(low, high):
    	pivot = arr[high] # 맨 오른쪽 선택
        left = low
        for right in range(low, high):
        	if arr[right] < arr[left]: #왼쪽 값이 오른쪽 값보다 크면
            	arr[left], arr[right] = arr[right], arr[left]
                left += 1
        arr[left], arr[high] = arr[high], arr[left]
    if low < high:
    	pivot = partition(low, high)
        quicksort(arr, low, high-1)
        quicksort(arr, pivot+1, high)

최악의 경우 시간복잡도 O(n^2)
이미 정렬된 배열이 입력으로 들어올 시 모든 경우를 다 확인하게 되므로 버블정렬화 됨

출처 : 파이썬 알고리즘 인터뷰