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
