Day08_array_Test14 : 삽입 정렬 (★★★)

(Q) 삽입 정렬 (Insertion Sort)

다음 규칙에 따라 정렬을 구현하세요.
30, 10, 20, 50, 40을 저장할 배열을 만듭니다.
배열의 위치를 변경하여 10, 20, 30, 40, 50 순으로 저장될 수 있도록 만든 뒤 출력합니다

** 다음 사이트를 참고하여 구현하세요

1. 상단 메뉴에서 정렬 방식을 `INS`(버블 정렬, INSORTION SORT)로 지정합니다
2. 하단 `Create(A)` 버튼을 눌러 데이터 입력란에 `30, 10, 20, 50, 40`을 입력하고 Go를 누릅니다
3. 하단 `Sort` 버튼을 누르면 정렬되는 과정을 시각적으로 확인할 수 있습니다 

https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

 

package day08;

public class Day08_array_Test14 {

	public static void main(String[] args) {
		
		// 배열의 생성
		int[] array = new int[] {30, 10, 20, 50, 40};
						
		// 정렬 전 출력
		for(int i = 0 ; i < array.length ; i ++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
		
		// 삽입 정렬
		for(int nowIndex = 0 ; nowIndex < array.length ; nowIndex ++) {
			
			int backup = array[nowIndex];		// 현재 위치의 데이터를 백업에 저장
			int lastOverwrite = nowIndex;		// 마지막 덮어쓰기 위치를 마지막 백업 인덱스로 지정
			
			for(int previousIndex = 0 ; previousIndex < nowIndex ; previousIndex ++) {
				
				// 이전 인덱스의 배열값이 현재 인덱스의 배열 값보다 크면
				if(array[nowIndex] < array[previousIndex]) {
 					// 현재 인덱스 배열값을 그 인덱스의 배열값으로 바꾸고
					array[nowIndex] = array[previousIndex];		
					// 마지막 덮어쓰기 위치를 그 인덱스로 바꾼다
					lastOverwrite = previousIndex;
				}
			}
			
			array[lastOverwrite] = backup;		// 마지막 덮어쓰기 위치에 백업 데이터를 대입
		}

		// 정렬 후 출력
		for(int i = 0 ; i < array.length ; i ++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
}

 

 

** 삽입 정렬 (Insertion sort)

1) 배열의 0번째 위치부터 진행하며 i번째 값과 0부터 (i-1)번째 값을 비교한다

2) 만약 i번째 값보다 크면 한 칸씩 오른쪽으로 민다 (덮어쓰기)

    만약 i번째 값보다 작으면 그냥 놔둔다

3) i번째 값은 가장 마지막에 덮어쓰기를 한 위치에 들어간다

4) 위 과정을 배열의 0번째 위치부터 (array.length - 1)번째 까지 반복한다