[정렬] 삽입 정렬

개념

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘이다.

정렬의 시작은 두번째 요소부터 시작되며 본인의 왼쪽으로는 이미 정렬된 상태라 생각하면 된다.

왼쪽의 값이 비교하려는 요소값보다 작을 때까지 위치를 왼쪽으로 이동시키면 된다.

 

처리과정

정렬의 시작은 두번째 요소인 4부터 왼쪽의 값들과 비교를 하면된다.

처음 비교할 값이 14 하나 뿐이고 4가 14보다 작기때문에 값을 서로 교체한다.

 

4와 14가 이미 정렬이 됐고 정렬할 다음 요소는 세번쨰 요소인 8이다.

같은 방법으로 왼쪽의 정렬된 요소들과 비교를 하여 자기 위치를 찾아가면 된다.

자세한 처리과정은 아래와 같다.

package S_20210126;

public class insertSort{
	public static void main(String[] args) {
		int[] arr = {2,8,1,4,6,5};
		
		// 오름차순
		for(int i=0;i<arr.length;i++) {
			for(int j=i;j>=1;j--) {
				if(arr[j-1]>arr[j]) {
					swap(j-1,j,arr);
				}else break;
			}
		}
		
		print(arr);
	}
	public static void swap(int orgIdx, int changeIdx, int[] arr) {
		int temp = arr[orgIdx];
		arr[orgIdx] = arr[changeIdx];
		arr[changeIdx] = temp;
	}
	
	public static void print(int arr[]) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
}