삽입 정렬(Insertion Sort) 에 대한 간단 정리 !

안녕하세요.

 

이는 면접 대비 맞춤 포스팅입니다.

 

그럼, 바로 진행하겠습니다.

 

 

 

 

 

 

 

삽입 정렬이란 ?

---

  -  손 안의 카드를 정렬하는 방법과 유사한 알고리즘이다.

 

  -  처음에는 두 번째 원소부터 시작하는데, 해당 원소를 꺼내든다. 

    그 후, 그 앞의 원소들과 하나씩 비교하여 삽입할 위치를 정한다.

  *** 만약, 앞의 원소보다 크기가 크면 종료한다.

 

  -  종료 시 그 지점에 원소를 넣고, 나머지 원소들은 한 칸씩 뒤로 밀려난다.

 

 

  -  장점

    ->  배열 원소의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 정렬들보다 유리할 수 있다.

    ->  대부분의 원소가 정렬된 상태에서는 매우 효율적일 수 있다. (이는 선택, 삽입, 버블 정렬 한정)

 

 

  -  단점

    ->  비교적 많은 원소들의 이동을 요구한다. 

    ->  원소 수가 많고 원소 크기가 클 경우에는 적합하지 않다.

 

*** 시간복잡도 : Best : n, Avg : n^2, Worst : n^2

 

삽입 정렬 코드

---

  -  수도코드

 Insertion-Sort(A, n) => A[1...n]
	for j <- 2 to n
		do key <- A[j]
		   i <- j – 1
		   while i >= 0 and A[i] > key
			do A[i + 1] <- A[i] // Shift 과정
			   i  <- i – 1
		   A[i + 1] = key

 

 

 

 

  -  실제코드

// sort는 1차원 int 배열로서, 정렬하고자 하는 배열이다.
int size = sort.length;
		for(int i = 1; i < size; i++) {
				int key = sort[i];
				int j = i - 1;
				while(j >= 0 && sort[j] > key) {
					sort[j + 1] = sort[j];
					j--;
				}
				sort[j + 1] = key;
		}

 

 

 

알고리즘 그림 설명

---

삽입 정렬(Insertion Sort) 진행 과정

 

초록색 : 정렬하기 위해 사용하는 원소 + 현재 해당 위치에 고정된 원소 (물론, 다음 번 째 탐색 시 변경될 수 있다.)

 

 

 

 

 

 

감사합니다.

 

 

 

 

그림 출처
https://www.thecshandbook.com/Insertion_Sort