[알고리즘] 자바에서의 삽입정렬

삽입 정렬(Insertion Sort)

- 삽입 정렬은 두번째 인덱스부터 시작하여 마지막 인덱스 까지 로직을 수행한다.

- 해당 인덱스(key 값) 앞에 있는 데이터부터 key 값과 비교를 시작한다.

- 만약 key 값 보다 key 값의 앞에 있는 데이터가 클 경우, 두 요소의 위치를 바꿔주고 이를 key 값이 앞에 있는 값보다 더 클 때가지 반복한다.

- 만약 key 값이 배열에서 가장 작은 값일 경우, 더 작은 값이 앞에 나타나지 않고 계속 위치를 변경해주게 되어 해당 인덱스는 배열에서 가장 앞에 위치하게 된다.

- 만약 중간에 key 값 보다 작은 값이 나타날 경우, 더 이상 위치를 바꿔주지 않고 해당 회차의 반복문을 종료해준다. 

 

삽입 정렬 알고리즘의 패턴?

* 배열 길이 별 데이터 비교 최대 횟수 및 전체 반복 최대 횟수

- 배열의 길이가 2일 경우 : 데이터 비교 횟수 1, 전체 반복 횟수 1

- 배열의 길이가 3일 경우 : 데이터 비교 횟수 2, 전체 반복 횟수 2

- 배열의 길이가 4일 경우 : 데이터 비교 횟수 3, 전체 반복 횟수 3

https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

자바 코드로 직접 구현해보자.

- InsertionSort.java

public class InsertionSort {
	
	private int[] array;
	
	public InsertionSort(int[] array) {
		this.array = array;
	}
	
	public int[] insertionSort() {
		
		for(int i = 0; i < this.array.length-1; i++) {
			for(int index = i + 1; index > 0; index--) {
				if(this.array[index] < this.array[index-1]) {
					int temp = this.array[index-1];
					this.array[index-1] = this.array[index];
					this.array[index] = temp;
				}
				else
					break;
			}
		}
		
		return this.array;
	}
}

 

코드가 제대로 동작하는지 확인하기 위한 main 코드는 다음과 같다.

- InsertionSort_main.java

import java.util.Arrays;
import java.util.Random;

public class InsertionSort_main {
	public static void main(String[] args) {
		int[] array = new int[10];
		
		Random random = new Random();
		
		for(int i = 0; i < array.length; i++) {
			array[i] = random.nextInt(100);
		}
		
		InsertionSort sortArray = new InsertionSort(array);
		int[] resultArray = sortArray.insertionSort();
		
		Arrays.stream(resultArray).forEach(x -> System.out.print(x + " "));
	}
}

 

삽입 정렬 알고리즘 분석

- 2중첩 반복문으로 알고리즘을 수행하기 때문에 O(n^2) 이다.

    - 최악의 경우 n * (n - 1) / 2

- 완전 정렬이 되어 있는 상태라면 최선의 경우이므로 O(n) 이다.