정렬 알고리즘(sorting algorithm) - 삽입 정렬(insertion sort)

정렬 알고리즘

n개의 숫자가 주어졌을때 이를 오름차순 / 내림차순으로 정렬하는 알고리즘

다양한 알고리즘이 있으며, 알고리즘에 따라 시간 복잡도가 다르다

2. 삽입 정렬(insertion sort)

•자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

•key와 tmp를 사용하여 비교 및 위치를 찾아 삽입

    - key는 2번째 인덱스 부터 시작 (index -> 1)

    - tmp는 key의 값을 저장하고 있으며, 인덱스 (key - 1) 부터 (0) 까지 tmp에 저장된 값과 비교하여 더 크다면 (현재 인덱스 + 1)에 저장 후 (현재 인덱스 - 1)에서 비교를 반복

    - 만약 tmp의 값보다 현재 인덱스의 값이 작다면 inner 반복문 종료

•이중 반복문을 사용하게되며, 바깥의 반복문은 (n - 1)번 반복, 안쪽 반복문은 (바깥 반복문의 반복된 횟수)만큼 반복한다.

•정렬 방식

•시간 복잡도

탐색(비교)는 1, 2, 3, 4 번 실행 되었으므로

n-4, n-3, n-2, n-1 번

-> 1, 2, ...., n-1 이라 볼수있다.

즉 총 비교 수는 1 + 2 + ... + (n-2) + (n-1)

= ( (n-1) * (n - 1 + 1) )  / 2

= ( n * (n - 1) ) / 2 

= (n^2 - n) / 2

빅오표기법으로 표기하면

O(n^2) 이 된다.

•공간 복잡도

한개의 배열 [7, 2, 5, 4, 1] 과 tmp[1]을 사용하므로

5 + 1 만큼을 사용한다.

n개의 원소가 들어간 배열의 경우 n+1만큼의 공간을 사용하지만

빅오표기법에 의해 (상수항 무시 -> 1*n 이므로 n만 사용, 영향력 없는 항 무시에 의해 -> n + 1 이지만 영향력없는 1 무시하여 n만 사용)

O(n) 이 된다.