단순 삽입 정렬(straight insertion sort)
단순 삽입 정렬은 0 ~ n-1까지 n개의 배열이 있다고 가정했을 때, 1번 위치 요소부터 선택을 시작하여 현재 정렬되지 않은 부분의 첫 번째 요소를 선택하여 선택한 위치 앞 부분 요소들과 비교를 하여 정렬기준에 따라 해당 되는 위치에 삽입을 수행해나가는 정렬 알고리즘이다.
단순 삽입정렬은 셔틀 정렬(shuttle sort)라고도 부른다.
// 선택 정렬 부분
static void insertionSort(int[] a, int n){
for(int i = 1; i < n ; i++){
int j; // 변경할 위치를 찾기위한 변수
int tmp = a[i]; // 삽입할 요소 값
for(j = i ; j > 0 && a[j-1] > tmp ; j--)
a[j] = a[j-1];
a[j] = tmp;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("단순 삽입 정렬");
System.out.print("요솟수 : ");
int nx = sc.nextInt();
int[] x = new int[nx];
for(int i = 0 ; i < nx ; i++){
System.out.print("x[" + i + "] : ");
x[i] = sc.nextInt();
}
insertionSort(x,nx);
System.out.println("\n오름차순으로 정렬합니다.");
for(int i = 0 ; i < nx; i++){
System.out.println("x["+i+"] = " + x[i]);
}
}
위에 코드와 같이 1번 인덱스 위치부터 값을 선택해나가며, 정렬기준에 따른 위치에 값을 삽입해나가는 방식이다.
이때 두 가지 조건에 따라 반복적으로 비교가 이루어진다.
1.) 해당 위치에 값을 삽입하기 위해 찾아나가는 j변수 값이 0보다 크다.
2.) 현재 삽입하고자하는 위치 j에 대해서 앞 쪽 인덱스의 요소가 정렬기준에 따라 변경되어야 할 경우
-> 쉽게말해 현재 위치에 값을 선택하고 앞쪽요소와 계속 비교를 해가면 자신의 위치를 찾아나가는 것이다. 즉, 현재 위치 앞쪽에 요소가 정렬기준에 따라 현재 선택된 요소보다 뒤쪽에 위치해야할 경우라면 계속 한 칸씩 이동하다가 더 이상 비교 대상이 없거나, 이미 앞쪽 요소가 기준에 따라 앞쪽에 위치해야할 경우(정렬된 경우) 현재 위치가 선택된 요소의 정렬 위치가 되는 것이다.
'알고리즘&자료구조 > 정렬 알고리즘' 카테고리의 다른 글
퀵 정렬 (1) | 2022.10.05 |
---|---|
셸 정렬 (1) | 2022.10.03 |
단순 선택 정렬(straight selection sort) (0) | 2022.10.01 |
버블 정렬(bubble sort) (2) | 2022.09.25 |
정렬 알고리즘 (0) | 2022.09.25 |