[알고리즘] #3 삽입 정렬(Insertion Sort)

오늘은 삽입 정렬(Insertion Sort)을 java코드로 구현 해 보자

---

 

삽입(Insertion) 정렬 이란?

배열의 요소를 하나씩 확인하며, 각 요소를 이미 정렬된 부분 배열의 올바른 위치에 삽입하여 정렬한다.

선택정렬과 유사하지만 데이터가 조금이라도 정렬되어 있는 경우 매우 효율적인 알고리즘이다.

손안에 카드 여러장을 한장씩 뽑아 왼쪽부터 순서대로 정렬하는것과 유사하다.

 

 

동작원리

1. 처리되지 않은 데이터를 순차적으로 선택

: 현재 요소와 앞 요소를 비교해야 하기 때문에 첫 라운드는 배열의 두번째 인덱스에 위치한 요소부터 시작함.

 

2. 정렬된 부분 배열에서 삽입할 위치를 찾기

: 현재 요소를 임시 변수(temp)에 저장하고, 정렬된 부분 배열에서 해당 요소가 들어갈 위치를 찾음,

이전 요소들과 비교하면서 더 큰 요소들을 오른쪽으로 이동시켜 공간을 만듬.

 

3. 올바른 위치에 삽입

: 올바른 위치를 찾으면, 임시 변수에 저장된 값을 그 위치에 삽입.

 

4. 반복

: 1번으로 돌아가 라운드를 정렬이 완료 될때 까지 반복함.

자바코드로 구현

import java.util.Arrays;
	//삽입정렬
public class Insertion_Sort {

	public static void main(String[] args) {
		int[] arr = {6, 5, 3, 1, 8, 7, 2, 4};
		System.out.println("정렬 전 : " + Arrays.toString(arr));
		insertionSort(arr);
		System.out.println("정렬 후 : " + Arrays.toString(arr));
	}
	
	private static void insertionSort(int[] arr) {
		for(int i = 1; i < arr.length; i++) { // 두번째 요소 부터 마지막 요소 까지 순차적으로 반복
			int temp = arr[i];	// 현재 인덱스의 값을 임시 변수에 저장
			int prev = i-1; 	// 현재 인덱스의 이전 인덱스번호를 가리키는 변수
			
			// 이전 인덱스에있는 요소의 값이 현재 값보다 크면 위치를 교환
			while(prev >= 0 && arr[prev] > temp) {
				arr[prev+1] = arr[prev]; // 이전값을 현재 인덱스로 이동
				prev--;	// 이전 인덱스로 이동
			}
			arr[prev+1] = temp; // 현재 값을 올바른 위치에 삽입
		}
	}

}

·버블정렬과 선택정렬과 마찬가지로 반복문2개가 중첩이 되있으나 이중 for문이 아닌 for문안에 while문이 중첩되어 있음,

=>이는 조건에따라 내부 반복문이 실행되는 것이기 때문에 데이터가 조금이라도 정렬되어 있으면 내부 반복문인 while문이 실행되지 않아 버블정렬과 선택정렬보다 효율적인 정렬이라고 할 수 있음

 

1. 두번째 인덱스에 있는 요소를 현재 요소로 지정

: for문안에 있는 i는 인덱스를 가리키며 i = 1을 초기값을 설정해 두번째 인덱스에 있는 요소를 현재 요소로 지정해줌

 현재 인덱스에 위치한 요소의 값을 임시변수인 temp에 저장하고 prev에는 현재 요소의 인덱스번호의 이전 인덱스 번호를 뜻함.

 

2. 이전 인덱스의 값이 현재 인덱스의 값보다 크면 위치를 교환(arr[prev] > temp 조건), 라운드시작

: prev가 음수면 실행되지 않으며, arr[prev] > temp 조건을 만족하면 내부 반복문인 while문을 실행하며 요소들의 위치를 교환해줌

prev를 이용하여 큰 요소는 한 단계씩 오른쪽으로 이동하며 이전 요소가 현재 요소보다 작을때 까지 반복함

 

 

3. 올바른 인덱스 위치에 요소 삽입

: while반복문이 끝나면 prev는 반복문안에서 조건이 맞을때마다 증감을 했으므로 prev의 값은 현재 temp값 보다 작은 값들 중 가장 큰 값의 위치를 가리키게 됨

그러므로 arr[prev+1] = temp는 prev위치 바로 다음 인덱스에 temp값을 삽입해 준 것

(현재 temp값 보다 작은 값들중 가장 큰 값의 바로 오른쪽위치에 삽입하기 위함) 

1~3번의 과정이 한 라운드임

 

4. 1번으로 돌아가 라운드를 반복하여 배열을 정렬함

 

※  위 코드는 오름차순 정렬이나 while문의 조건문 부등호를 바꾸어 주면 내림차순 정렬이 가능함

출력결과

정렬 전 : [6, 5, 3, 1, 8, 7, 2, 4]

정렬 후 : [1, 2, 3, 4, 5, 6, 7, 8]

 

GIF로 이해하기

 

특징

• 단순함 : 구현이 간단하며 이해하기 쉽다.
• 효율적 : 요소들이 조금이라도 정렬되어 있으면 내부 반복문을 실행하지 않으므로 매우 효율적이지만 시간복잡도의 평균이 O(n^2)므로 버블정렬과 선택정렬과 같이 대규모 데이터에는 비효율적이다.
• 적은 공간 사용 : 추가적인 메모리 공간이 필요하지 않다. 제자리(in-place) 정렬
• 안정성 : 동일한 값에 대해서는 순서가 유지되므로 안정 정렬(Stable Sort)이다
• 시간 복잡도 : 최선인 경우에는 O(n)이므로 매우 효율적이지만 평균 및 최악의 경우에는 O(n^2)이므로 비효율적이다. (최악의 경우는 역순으로 정렬이 되어있을시)
• 공간 복잡도 : 주어진 배열 안에서 요소들의 위치를 바꾸어 수행하므로 O(n) 이다.

 

마치며

·오늘은 삽입 정렬을 알아보고 구현해 보았다.

· 삽입정렬은 카드게임을 할때 손안에 있는 여러 카드를 한장씩뽑아 순서대로 정렬하는 방법과 비슷하다고 하여 이해하는데 도움이 많이 되었다.

· 선택 정렬과 삽입정렬 둘다 각 반복에서 배열의 일부분을 정렬된 부분과 비교하며 정렬을 진행하고 n번째 반복 이후 첫 n개 요소는 정렬된 순서로 오기 때문에 비슷해 보이지만 

탐색 과정에서 선택정렬은 전체 배열을 순회하여 최소값을 찾는 반면, 삽입정렬은 정렬된 부분 배열에서 삽입할 위치를 찾기 위해 필요한 만큼만 탐색한다. 그러므로 삽입정렬은 이미 정렬된 부분을 활용하여 탐색과 삽입을 효율적으로 진행할 수 있기 때문에 더 효율적이다.