정렬, 삽입정렬 알고리즘

알고리즘 설명

<img alt="" src="https://static.podo-dev.com/blogs/images/2019/07/10/origin/AUD5BF181224235510.PNG" style="width:240px">

<br/>
1번째 원소 A를 시작하여 1-1부터 0번째까지 큰 값은 넘기고, 작은 값이 나올 경우, 그 값 앞에 A를 **"삽입"**하고 순회를 종료한다.

2번째 원소 B를 시작하여 2-1부터 0번째까지 큰 값은 넘기고, 작은 값이 나올 경우, 그 값 앞에 B를 **"삽입"**하고순회를 종료한다.

..

N번째 원소 K를 시작하여 N-1부터 0번째까지 큰 값은 넘기고, 작은 값이 나올 경우, 그 값 앞에 K를 **"삽입"**하고순회를 종료한다.

이과정을 N번째까지 반복한다.

<br/>

복잡도

선택정렬의 최선의 경우는 이미 정렬되어있는 경우이다.

그 경우 바로 앞에 삽입 되기 때문에 1번의 비교 연산을 한다.

따라서 최선의 경우는 O(N) 이다.

최악의 경우는 역순으로 정렬되어있는 경우이다.

N번동안 i번째일때 i-1번의 순회를 한다. N(N-1)/2 비교 횟수를가진다

따라서 최악의 경우 O(N^2) 이다.

평균 비교 횟수는 따라서 (N(N-1) + N ) / 4 이므로 O(N^2) 이다.

<br/>

장단점

삽입정렬은 비교적 많은 배열들의 이동을 포함하고있다.

따라서 배열 길이가 길고, 배열의 데이터가 클 경우 적합하지 않을 수 있다.

반면에 삽입정렬은 안전한 정렬방법으로, 레코드 수가 적을 경우 다른 복잡한 정렬방법보다 유리 할 수 있다.

또한 어느정도 정렬되어있는상태라면 삽입정렬 매우 효율적이다.

<br/>

소스코드

public class InsertionSort {

	public void sort(int[] arr) {
		int n = arr.length;

		int k;
		int i, j;
		for (i = 1; i < n; i++) {
			k = arr[i];
			for (j = i - 1; j >= 0; j--) {
				if (k < arr[j]) {
					arr[j + 1] = arr[j];
				} else {
					break;
				}
			}

			arr[j + 1] = k;

		}

	}

	public static void main(String[] args) {
		int arr[] = { 10, 8, 1, 7, 3, 2, 15, 9, 5 };
		new InsertionSort().sort(arr);
		System.out.print(Arrays.toString(arr));
	}

}

<br/>

<br/>

<br/>

<br/>