Contents
삽입 정렬(insertion sort)삽입 정렬(insertion sort)
목표 : 오름 차순
원본 데이터 (5, 8, 2, 4, 3) N
알고리즘 작성 해보기
1회전(1바퀴) k = arr[1]
8, 5 비교 변함없음
2회전(2바퀴) k = arr[2]
2, 8 비교 작음
2, 5 비교 작음 (2, 5, 8, 4, 3)
3회전(3바퀴)
4, 8 비교 작음
4, 5 비교 작음
4, 2 비교 큼 (2, 4, 5, 8, 3)
4회전(4바퀴)
3, 8 비교 작음
3, 5 비교 작음
3, 4 비교 작음
3, 2 비교 큼 (2, 3, 4, 5, 8)
회전수 : N-1
n회전 비교 횟수 : N-n
알고리즘 그대로 코드 작성 해보기
package ex03.test; import java.util.Arrays; public class InsertSort01 { public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; int temp; // 1회전 if(arr[1]<arr[0]){ //스왑 temp = arr[1]; arr[1] = arr[0]; arr[0] = temp; } System.out.println(Arrays.toString(arr)); // 2회전 if(arr[2]<arr[1]){ if(arr[2]<arr[0]){ // 스왑 temp = arr[2]; arr[2] = arr[1]; arr[1] = arr[0]; arr[0] = temp; }else{ // arr[2]>arr[0] temp = arr[2]; arr[2] = arr[1]; arr[1] = temp; } } System.out.println(Arrays.toString(arr)); // 3회전 if(arr[3]<arr[2]){ if(arr[3]<arr[1]){ if(arr[3]<arr[0]){ temp = arr[3]; arr[3] = arr[2]; arr[2] = arr[1]; arr[1] = arr[0]; arr[0] = temp; }else{ temp = arr[3]; arr[3] = arr[2]; arr[2] = arr[1]; arr[1] = temp; } }else{ temp = arr[3]; arr[3] = arr[2]; arr[2] = temp; } } System.out.println(Arrays.toString(arr)); // 4회전 if(arr[4]<arr[3]){ if(arr[4]<arr[2]){ if(arr[4]<arr[1]){ if(arr[4]<arr[0]){ temp = arr[4]; arr[4] = arr[3]; arr[3] = arr[2]; arr[2] = arr[1]; arr[1] = arr[0]; arr[0] = temp; }else{ temp = arr[4]; arr[4] = arr[3]; arr[3] = arr[2]; arr[2] = arr[1]; arr[1] = temp; } }else{ temp = arr[4]; arr[4] = arr[3]; arr[3] = arr[2]; arr[2] = temp; } }else{ temp = arr[4]; arr[4] = arr[3]; arr[3] = temp; } } System.out.println(Arrays.toString(arr)); } }
모듈화를 통해 간단한 코드 만들기
package ex03.test; import java.util.Arrays; public class InsertSort01 { public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; for(int i = 1; i < arr.length; i++) { int temp = arr[i]; int j; for(j = i - 1; j >= 0 && arr[j] > temp; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = temp; System.out.println(Arrays.toString(arr)); } } }
Share article