알고리즘 | 삽입정렬

삽입정렬(Insert Sort)


  • 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘
  • 아직 정렬 되지 않은 임의의 데이터를 이미 정렬 된 부분의 적절한 위치에 삽입해가며 정렬하는 방식

  • 시간 복잡도

    • 최선
      • list가 이미 정렬 되어 있는 경우에는 외부 루프 n-1번만 실행되고 각 단계에서 데이터의 이동 없이 1번의 비교 연산만 수행
      • 삽입 정렬은 비교적 정렬이 된 리스트에서는 이동 횟수가 선택 정렬과 버블 정렬에 비해 적게 일어난다는 장점
      • O(n)
    • 최악
      • 오름차순으로 정렬해야 하는 데이터가 역순으로 내림차순으로 정렬 되어 있다면 각 단계에서 앞에 놓인 데이터들은 전부 한 칸씩 뒤로 이동 해야하고, 외부 루프 안의 각 반복마다 i번 비교가 수행
      • 따라서 데이터의 수가 많고 크기가 큰 경우에는 적합하지 않음
      • O(n^2)

동작원리


  1. key 값을 기준으로 key의 앞은 정렬이 된 상태이다. i번째 요소를 정렬을 하기 위해서 i번째 배열의 값을 key로 저장을 한다.
  2. key값을 기준으로 i-1부터 검사를 하며 key 값보다 값이 클 경우 값을 한 칸씩 오른쪽으로 이동 시킨다.
  3. key 값보다 작거나 같은 값이 나올 때까지 2번 과정을 반복한다.
  4. 3번 과정에서 key값이 들어갈 위치를 찾으면 key값을 위치에 삽입한다.
  5. i+1 번째 배열의 값을 key로 저장 하며 모든 레코드가 정렬될 때 까지 1번 과정부터 반복

예제코드


1
2
3
4
5
6
7
8
9
10
11
void insertSort()
{
intDataSet[]={6,4,2,3,1,5};
for(inti=1; i<n; i++){
key=DataSet[i]; //두 번째 값부터 선택
for(intj=i-1; j>=0&&list[j]>key; j—-)//선택된 값(key)보다 작은 값을 찾는다
DataSet[j+1]=DataSet[j];// 작은 값을 찾은 경우 그 값뒤의 모든 값을 우측으로 이동
DataSet[j+1]=key;//해당되는 곳에 값을 삽입
}
}
Share