나동빈 실전 알고리즘 4강 - 삽입 정렬(Insertion Sort)

<문제> 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요
1 10 5 8 7 6 4 3 2 9

---

이번에는 삽입정렬을 이용하여 다음의 숫자들을 오름차순으로 정렬해보자.

삽입정렬은 앞에서부터 차례대로 봤을 때 적절한 위치에 숫자를 삽입해주는 정렬을 말을한다.

 

1이 선택되었을때는 가장 작기때문에 10부터 살펴본다.

10은 앞에 있는 숫자들을 봤을때 1 양 옆중에 자신이 들어갈 위치가 오른쪽에 위치해야한다.

5는 앞에 있는 숫자들을 봤을 때 1과 10 사이 중에 1과 10 사이에 들어가면 되므로 1 5 10으로 위치한다

8은 앞에 있는 숫자들을 봤을 때 1과 5와 10 사이 중에 5와 10 사이에 들어가면 되므로 1 5 8 10으로 위치한다.

 

이렇게 해당 숫자가 선택적으로 자리를 골라서 자리하게 되는 프로그램을 작성해보자.

 

package excercise;

public class algorithm {
	public static void main(String[] args) {
		int temp = 0;
		int j = 0;
		int arr[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
		
		for(int i = 0; i < arr.length - 1; i++) {
			j = i;
			while(j >= 0 && arr[j] > arr[j+1]) {
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				
				j--;
			}
		}
		
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}	
}

 

복잡도는 선택정렬과 버블정렬과 비슷하지만 삽입 정렬은 하나의 가정을 하고 시작한다.

숫자가 정렬이 되어있다면 굉장히 효율적으로 숫자 위치를 오름차순으로 정렬할 수 있다.

 

blog.naver.com/ndb796/221226806398

4. 삽입 정렬(Insertion Sort)