Selection Sort

• 이미 sort 된 부분과 아직 sort 안된 부분으로 나눔
• unsorted elements 중 가장 작은 것을 찾아서, 맞는 위치로 swap, sorted elements 하나씩 늘려감
• n-1 + n-2 + … + 2 + 1 = n(n-1) / 2 → $O(N^2)$

Bubble Sort

• 맨 마지막 element에서 부터 비교 시작하여 올바른 위치에 스왑
• 0 1 2 3 4 index 5칸 어레이일 경우, 4와 3 비교, 3과 2 비교 .. 형식
• n-1 + n-2 + … + 2 + 1 = n(n-1) / 2 → $O(N^2)$
• 문제 : 중도 과정에서의 의미 없는 swap 발생 가능

Insertion Sort

• key를 설정하고, 비교해서 swap 후 sorted 부분에 넣음
• sorted 부분에서도 key와 비교해서 정렬
• n-1 + n-2 + … + 2 + 1 = n(n-1) / 2 → $O(N^2)$
  • key에 따라 이거보다는 작게 나올 수 있음
• bubble sort 보다 좀 더 작은 swap