[JAVA] 삽입정렬(InsertionSort)

삽입정렬

- 안정정렬

- 시간복잡도: 

- 설명: 왼쪽에 있는 항목들은 정렬된 것으로 가정하고, 증가하는 인덱스의 값을 삽입하는 방법.

- 특징: 정렬대상이 적거나, 이미 부분적으로 정렬되어 있는 상황일 경우 효율적. 선택정렬과 버블보다는 빠름

	package kr.opid.sorting;
	public class InsertionSort {
	public static void main(String[] args) {
	int[] array = new int[10];
	array[0] = 33;
	array[1] = 11;
	array[2] = 99;
	array[3] = 1;
	array[4] = 22;
	array[5] = 88;
	array[6] = 55;
	array[7] = 44;
	array[8] = 66;
	array[9] = 77;
	System.out.println("before)");
	displayArray(array);
	System.out.println();
	System.out.println("after)");
	insertionSort(array);
	}
	static int[] insertionSort(int[] arr) {
	for (int i = 1; i < arr.length; i++) {
	int tmp = arr[i];
	int j = i;
	while (j > 0 && arr[j - 1] >= tmp) {
	arr[j] = arr[j - 1];
	--j;
	}
	arr[j] = tmp;
	}
	return arr;
	}
	/**
	* 배열 출럭
	*
	* @param arr
	*/
	static void displayArray(int[] arr) {
	for (int i = 0; i < arr.length; i++) {
	System.out.print(arr[i] + " ");
	}
	}
	}

view raw InsertionSort.java hosted with ❤ by GitHub