삽입정렬(Insert Sort)
- 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘
아직 정렬 되지 않은 임의의 데이터를 이미 정렬 된 부분의 적절한 위치에 삽입해가며 정렬하는 방식
시간 복잡도
- 최선
- list가 이미 정렬 되어 있는 경우에는 외부 루프 n-1번만 실행되고 각 단계에서 데이터의 이동 없이 1번의 비교 연산만 수행
- 삽입 정렬은 비교적 정렬이 된 리스트에서는 이동 횟수가 선택 정렬과 버블 정렬에 비해 적게 일어난다는 장점
- O(n)
- 최악
- 오름차순으로 정렬해야 하는 데이터가 역순으로 내림차순으로 정렬 되어 있다면 각 단계에서 앞에 놓인 데이터들은 전부 한 칸씩 뒤로 이동 해야하고, 외부 루프 안의 각 반복마다 i번 비교가 수행
- 따라서 데이터의 수가 많고 크기가 큰 경우에는 적합하지 않음
- O(n^2)
- 최선
동작원리
- key 값을 기준으로 key의 앞은 정렬이 된 상태이다. i번째 요소를 정렬을 하기 위해서 i번째 배열의 값을 key로 저장을 한다.
- key값을 기준으로 i-1부터 검사를 하며 key 값보다 값이 클 경우 값을 한 칸씩 오른쪽으로 이동 시킨다.
- key 값보다 작거나 같은 값이 나올 때까지 2번 과정을 반복한다.
- 3번 과정에서 key값이 들어갈 위치를 찾으면 key값을 위치에 삽입한다.
- i+1 번째 배열의 값을 key로 저장 하며 모든 레코드가 정렬될 때 까지 1번 과정부터 반복
예제코드
|
|