[Java] 자바 삽입 정렬 / java 삽입 정렬 구현하기

2020-09-24

---

삽입 정렬(揷入整列, insertion sort)은

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다.

각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다.

그러므로 다음과 같은 결과가 된다.

배열이 길어질수록 효율이 떨어진다.

다만, 구현이 간단하다는 장점이 있다.

선택 정렬이나 거품 정렬과 같은 같은 O(n2) 알고리즘에 비교하여 빠르며,

안정 정렬이고 in-place 알고리즘이다.

 

 

출처: 위키피디아

---

소스코드

		Scanner scan = new Scanner(System.in);
		
		int key = 0;
		//비교가 되는 키값 변수
		int number = 0;
		//배열의 값을 넣기 위한 변수
		int [] arr= new int [11];
		
		
		
		do {
			number++;
			arr[number] = scan.nextInt();
		}while(number < 9);
		
		//배열의 정렬을 원하는 값 입력
		int temp = 0;
		//j값을 잠시 담아둘 변수
		
		for(int i = 2; i <= 9; i++) {
			key = arr[i];
			//키값은 배열의 두번째 부터 시작해서 비교
			for(int j = i-1; j >= 0; j--) {
				//범위는 키값보다 하나 작은 값부터
				//처음 범위까지 비교하면됨
				if(arr[j] > key) {
					arr[j + 1] = arr[j];
					//비교하는 값이 더 크기 때문에
					//그다음 수에 큰 값을 넣어줌
					temp = j;
				}else {
					temp = j;
					break;
				}
			}
			
			arr[temp + 1] = key;
			//더이상 키값보다 작은 값이 없으므로
			//작은값 +1 자리가 key의 자리가 됨
			temp = 0;
		}
		
		for(int i = 1; i < arr.length-1; i++) {
			System.out.print(arr[i] + " ");
		}