목표
- 삽입 정렬을 이해한다.
- 삽입 정렬을 구현할 수 있다.
- 삽입 정렬의 시간 복잡도
- 삽입 정렬에서 장점으로부터 착안된 쉘 정렬을 이해한다.
- 셸 정렬을 구현할 수 있다.
- 셸 정렬의 gap sequence에 대해서 이해한다.
- 셸 정렬의 시간 복잡도
셸 정렬은 삽입 정렬이 어느 정도 정렬된 상태에서 상당히 빠른 정렬 속도를 보인다는 점에서 착안하여 삽입 정렬을 수행하기 전에 어느 정도를 정렬한 상태에서 삽입 정렬을 하면 좋은 시간 복잡도를 기대할 수 있다는 생각에 만들어진 알고리즘이다.
그렇기 때문에 삽입 정렬에 대한 기본적인 이론을 익힌 이후 추가적으로 셸 정렬까지 공부해본다.
삽입 정렬
삽입 정렬은 현재 비교하고자 하는 target과 그 이전의 원소들과 비교하여 자리를 swap 하는 정렬 알고리즘이다.
삽입 정렬은 데이터를 이웃한 이전 원소의 데이터를 비교하면서 swap이 이루어지기 때문에 비교 정렬이라고 부르며, 정렬의 대상이 되는 데이터 외의 추가적인 공간을 소비하지 않기 때문에 제자리 정렬(in-place-sort)라고도 한다.
또한 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 이후에도 변하지 않는 안정 정렬입니다.
삽입 정렬의 전체적인 과정은 다음과 같다.
1. 현재 원소의 값과 원소의 이전 위치에 있는 원소들과 비교한다. ( 첫 번 개원 소는 비교할 원소가 존재하지 않기 때문에 두 번째 원소부터 시작한다.)
2. 현재 원소의 값을 가지고 이전의 원소들의 값을 비교하면서 자신의 자리에 삽입한다. 이 과정에서 이전의 원소들은 뒤로 한 칸씩 밀린다.
3. 다음 원소의 인덱스에서 1,2번 과정을 반복한다.
package com.company;
import java.util.Arrays;
public class Main{
private static int[] arr = {10,2,43,54,12,12,8,7,93,0,3,11,13,50,20};
public static void main(String[] args) {
//2번째 원소부터 시작
for(int i = 1; i < arr.length; i++){
//이전 원소를 표현할 변수가 하나 필요하다.
int j = i-1;
//현재 target의 값을 임시 저장.
int targetValue = arr[i];
while(j >= 0 && targetValue < arr[j]){
//현재 타깃의 값이 이전 원소보다 작을 때 이전 원소를 뒤로 계속 민다.
//타깃의 값을 저장하고 반복문을 빠져나갈때 해당 타깃의 값을 i+1위치에 삽입 해주어야하고
//j의 범위는 처음 인덱스 까지 비교해야하기 때문에 0보다 커야한다.
arr[j+1] = arr[j];
j--;
}
//반복문을 나올때는 arr[j]값이 target 보다 작다는 것을 의미하기 때문에 j+1자리에 target 값을 넣는다.
arr[j+1] = targetValue;
}
System.out.println(Arrays.toString(arr));
}
}
장점
- 추가적인 메모리 소비가 적다.
- 거의 정렬된 경우에 매우 효율적이다. 최선의 경우 O(N)의 시간 복잡도를 가진다.
- 안정 정렬이다.
단점
- 역순서에 가까울 경우 시간 복잡도가 O(N²)될 수 있다.
- 데이터의 상태에 따라 편차가 매우 커 일관적인 성능을 보장할 수 없다.
이제 삽입 정렬에 대해 간단히 알아봤으니 셸 정렬에 대해서 알아보자
셸 정렬
삽입 정렬의 단점은 오름차순 기준으로 타깃 원소가 이전의 원소보다 작을 경우 이전 원소들 모두 교환(swap)을 한다는 것이다.
삽입 정렬의 장점은 거의 정렬된 경우 매우 효율적이라는 것이다. 어떻게 개선될 수 있을 까?
즉 이전의 원소를 모두 비교하여, 교환하는 것이 아니라 GAP을 주기로 부분 리스트를 만들고 해당 GAP을 가진 부분 리스트들을 삽입 정렬을 먼저 수행하여 원소들의 위치를 대략적으로 잡아아 주고 마지막에 삽입 정렬을 하는 것이다.
정렬 기준에 가깝게 만든 후 삽입 정렬을 이용한다면 어느 정도의 속도를 일정하게 기대할 수 있기 때문이다.
셸 정렬의 전체적인 과정은 다음과 같다.
1. gap을 설정한다.
2. 각 간격 별로 분류된 부분 리스트들을 삽입 정렬을 한다.
3. 각 부분 리스트의 정렬이 끝나면 gap을 줄인다.
4. 간격이 1이 되면 마지막 삽입 정렬을 수행하고 마무리한다.
셸 정렬은 gap에 따라 정렬 속도가 달라질 수 있다.
여기선 간단하게 배열의 길이의 절반으로 설정하고 진행한다.
package com.company;
import java.lang.reflect.Array;
import java.util.Arrays;
public class Main{
private static int[] arr = {10,2,43,54,12,12,8,7,93,0,3,11,13,50,20};
public static void main(String[] args) {
int gap = arr.length/2; //gap을 구한다.
for(int i = gap; gap >0; gap /=2 ){ //gap을 반씩 줄이면서 1이 될때까지 반복한다.
for(int j =0; j < gap; j++){ //gap만큼 부분리스트가 생기기 때문에 부분리스트 만큼 반복을 돌린다.
//배열과, gap을 사용할 시작인덱스, 배열의 길이, 현재의 gap을 넘겨준다.
insert_sort(arr,j,arr.length,gap);
}
}
System.out.println(Arrays.toString(arr));
}
//각 부분리스트의 두번째 원소부터 배열의 size까지 돌아야하며, gap 값만큼 건너 뛰어야한다. 또한 각 부분리스트의 첫번 째원소의 값을 알아야 한다.
public static void insert_sort(int[] arr, int start, int size, int gap){
//부분리스트에서 i는 2번째 원소부터 시작하며, i를 인덱스그대로 사용하기 때문에 배열사이즈-1로 배열의 끝까지 범위를 지정한다.
//그리고 gap만큼 건너 뛰면서 부분 리스트를 삽입정렬 해야한다.
for(int i = start+gap; i <= size-1; i+=gap){
int targetValue = arr[i]; // 2번 째 인자의 값을 비교를 위해 저장한ㄷ.
int j = i-gap; // gap 차이만큼의 다음 원소인덱스를 가지고 있는다.
while (j >= start && targetValue < arr[j]){ //j는 첫번째 원소의 인덱스보다 커야하고, target의 값이 이전 gap차이나는 원소값보다 작을 때 loop를 탄다.
arr[j+gap] = arr[j]; //현재 타겟의 값에 이전 타겟의 값을 넣는다.
j -= gap; //다음비교를 위해 gap만큼 빼준다.
}
//루프를 나왔을 경우에는 타겟의 값이 j의 값보다 크기 때문에 밀려진 위치에 타겟의 값을 넣는다.
arr[j+gap] = targetValue;
}
}
}
셸 정렬의 장점과 단점
장점
1. 멀리 있는 원소들끼리 빠르게 비교 및 교환이 이루어진다.
2. 삽입 정렬(Insertion Sort), 거품 정렬(Bubble Sort)에 비해 정렬 속도가 빠르다.
3. gap 시퀀스가 좋을 경우 O(nlogn) 정도로 좋은 속도를 보장할 수 있다.
단점
1. 일반적인 삽입 정렬에 비해 구현이 까다롭다.
2. gap sequence에 영향을 많이 받으며 적절한 시퀀스를 선택해야 한다.
3. 일정 간격을 두고 원소의 교환이 이루어지기 때문에 안정 정렬이 아니다.
댓글