컴퓨터 알고리즘 Ch01, Ch02

The problem of sorting (정렬 문제)

value를 갖는 원소들의 집합을 입력받아 순서를 지키도록 재배치한 후 정렬된 집합을 출력하는 문제

▶ Insertion sort (삽입 정렬)

• 배열에서 원소를 하나 뽑은 후 비교대상이 되는 원소보다 작으면 왼쪽으로, 크면 오른쪽으로 이동시키며 정렬하는 것을 반복
• 매 반복마다 정렬되는 원소가 배열의 왼쪽 부분에 하나씩 쌓여가며 loop invariant 만족

▶ Merge sort (합병 정렬)

• 분할 정복 알고리즘(divide and conquer)의 일종