Java - 정렬 알고리즘 - 2 (삽입 정렬)

◎삽입 정렬

현재 비교하고자 하는 target(타깃)을 그 이전의 원소들과 비교하며 자리를 교환(swap)하며 맞는 자리에 삽입하는 방식

 

---

 

◎삽입 정렬의 특징

1. 비교 정렬(comparison sort)

삽입 정렬은 데이터를 바교하면서 찾는다.

 

2. 제자리 정렬(in-place sort)

정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다.

 

3. 안정 정렬(stable sort)

정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다.

 

---

◎삽입 정렬의 동작

idx 0의 원소는 앞의 원소가 존재하지 않기 때문에, idx 1부터 비교를 시작한다.

 

삽입 정렬의 동작 출처: https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

 

1. idx 1의 원소 5가 target원소이다. 5가 idx 0의 원소 8보다 작으므로 8을 밀고 5를 그 자리에 넣는다.

2. idx 2의 원소 6이 tartget원소이다. 6이 idx 1의 원소 8보다 작으므로 8을 밀고,

   idx 0의 원소 5보다 크므로 5는 밀지 않고 8이 밀린 자리에 넣는다.

3. idx 3의 원소 2가 tartget원소이다. 8,6,5가 2보다 크므로 한 칸씩 밀고 맨 앞자리에 2를 넣는다.

 

.... 반복

삽입 정렬 출처: https://dev-lagom.tistory.com/39

---

◎삽입 정렬의 구현

package SortAlgorithm;

import java.util.Arrays;

public class sort {

	//삽입 정렬
	private void insertionsort(int[] numarr) {
		for(int i = 1; i<numarr.length; i++) {
			int target = numarr[i]; //타겟 원소 설정
			int j = i-1; //타겟 원소보다 작은 idx를 가지는 원소들을 비교
			while(j>=0 && target<numarr[j]) { // 타겟이 이전 원소보다 크기 전 까지 반복
				swap(numarr, j, j+1); // 이전 원소를 한 칸씩 민다
				j--;
			}
			
			//j는 타겟원소보다 작은 원소의 idx를 의미하므로 target원소는 idx j+1에 들어가야한다
			numarr[j+1] = target;
		}
		
		print(numarr, "삽입정렬");
	}

	// swap
	private void swap(int[] numarr, int i, int j) {
		int temp = numarr[i];
		numarr[i] = numarr[j];
		numarr[j] = temp;
	}

	// 출력
	private void print(int[] numarr, String sortname) {
		System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = { 5, 6, 3, 1, 4, 2 }; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));

		sort Sort = new sort();

		Sort.insertionsort(numarr);

	}
}

실행 결과:

원래 배열:[5, 6, 3, 1, 4, 2]
삽입 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]

---

 

◎삽입 정렬의 시간 복잡도

 

최선의 상황:

입력 배열이 이미 정렬되어 있는 경우에, target이 언제나 이전 원소들 중 가장 큰 idx의 값보다 언제나 크기때문에 while문에 들어가지 않고, 각 회전당 1번만 비교하여, O(N)의 시간 복잡도를 가진다.

 

최악의 상황:

입력 배열이 역순으로 정렬되어있는 경우에 target이 언제나 이전 원소들중 가장 작은 idx의 값보다 언제나 작기 때문에 while문을 언제나 target의 인덱스 - 1만큼 반복하게 되므로,  O(N^2)의 시간복잡도를 가진다.

 

시간 복잡도:

시간 복잡도는 언제나 가장큰 차수의 값만을 남기므로, 삽입정렬의 시간복잡도는 O(N^2)이다.

하지만, 평균 시간 복잡도가 O(N^2)인 정렬 알고리즘(삽입, 버블, 선택) 중에서는 빠른 편에 속하는 알고리즘이다.

 

---

◎Sorting algorithm 시간 복잡도(time complexity) & 평균 정렬 속도(average sorting rate)

Sorting algorithm 시간복잡도(time complexity) & 평균 정렬 속도(average sorting rate) 출처: https://st-lab.tistory.com/195

---

◎정렬 알고리즘 구현-github

github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/sorting_algorithm

jerry-ryu/java_problemsolving_algorithm