DailyStudyNote

Linked List - 정렬 삽입 정렬 자료 배열의 모든 원소들을 앞에서 부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아냄으로써 정렬을 완성한다. [ 삽입 정렬의 정렬과정 ] 1) 정렬할 자료를 두 개의 부분집합 S 와 U로 가정한다. - 부분집합 S: 정렬된 앞부분의 원소들 - 부분집합 U: 아직 정렬되지 않은 나머지 원소들 2) 정렬되지 않은 부분 집합 U의 원소를 하나씩 꺼내며 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다. 3) 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. 4) 부분집합 U가 공집합이 되면 삽입 정렬이 완성된다. ✔ 시간 복잡도: O(n^2) 병합 정렬 여러 개의 정렬된..