[자료구조] 6가지 Sort 알고리즘 완벽 총정리(코드, 시간복잡도, Stable sort, 서울대 기출)
1. Insertion sort 원소 이전의 까지는 전부 정렬돼있음. 를 ~까지의 올바른 자리에 삽입하기. 정렬되어 있는 배열에 나를 삽입하기. 수행시간 Best: O(n) → 완전 정렬돼있을 때. 각 원소마다 자기 하나 왼쪽의 원소랑이랑만 딱 한번 비교 수행. 이미 자기 왼쪽 배열의 최대(k-1)보다 자기가 큼으로 삽입이 일어나지 않음. Worst: O() → k번의 원소마다, k-1번의 삽입을 위한 비교가 일어남. 코드 target이 현재 값. num[cur]가 num[i-1]부터 num[0]까지 내려가면서, target보다 큰 값이 없을 때까지 cur를 감소시킴. num[cur]가 target보다 작다면 루프 멈추고, num[c..