[자바/알고리즘]알고리즘 삽입정렬

삽입 정렬(Insertion Sort)은 배열의 구간을 정한다음 원소를 비교하며 정렬을 하는 방식입니다.

1. 0 번째 인덱스의 원소와 1 번째 인덱스의 원소를 비교 합니다. (ex. 범위는 0-1 인덱스)

2. 1 번째 원소가 0 번째 원소보다 작으면 첫 번째 원소의 인덱스는 1 증가하고 두 번째 원소의 인덱스는 1 감소합니다.

3. 이런식으로 범위가 1씩 증가하며 원소를 비교한 뒤 큰 숫자의  인덱스를 1씩 늘려주고 작은 숫자의 인덱스를 숫자 만큼 감소 해주세요. 

 

아래는 위의 순서에 맞게 실행한 예제입니다.

- 배열에 저장되는 값은 [3, 6, 0, 9, 1] 입니다.

Sequence	Array	Arrange
1	[3, 6, 0, 9, 1]	변화 없음
2	[3, 6, 0, 9, 1]	0(a[2] -> a[0]) 3(a[0] -> a[1]) 6(a[1] -> a[2])
3	[0, 3, 6, 9, 1]	1(a[4] -> a[1]) 3(a[1] -> a[2]) 6(a[2] -> a[3]) 8(a[3] -> a[4])

 

 

 

아래는 삽입 정렬을 구현한 자바 예제입니다.

package algorithm;

import java.util.Arrays;

public class InsertionSort {

	public static void main(String[] args) {
		int[] a = { 3, 6, 0, 9, 1 };
		int[] sorted_a = insertionSort(a);
		System.out.println(Arrays.toString(sorted_a));
	}

	public static int[] insertionSort(int[] a) {
		int i, j;
		for (i = 0; i < a.length; i++) {
			int temp = a[i];
			int range = i-1;
			while (range >= 0 && a[range] > temp) {
				a[range+1] = a[range];
				range--;
			}
			a[range+1] = temp;
		}
		return a;
	}
}