JAVA - 삽입정렬(Insertion Sort)
✅ 삽입정렬 ( Insertion Sort )
삽입정렬은 버블 정렬의 비효율성을 개선하기위한 방법으로
데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 정렬방식이다.
한 데이터씩 비교해 적절한 위치에 들어가기 이전에, 해당 데이터의 앞에 있는 데이터들은
이미 정렬되었다고 가정하며 그렇게 정렬되어있는 데이터리스트에서 적절한 위치를 찾고 해당위치에 삽입된다.
마찬가지로 데이터외의 추가공간을 필요로 하지않기때문에 '제자리정렬' 이기도 하다.
📌 정렬과정
1. 초기데이터배열이 주어진다.
2. 현재 타겟의 값과 이전위치들의 원소들을 비교한다 ( 첫 타겟은 두번째 원소부터 시작한다 )
3. 타겟의 값이 이전위치의 원소보다 작다면 위치를 교환한다.
4. 이전위치의 원소가 타겟보다 작을때까지 혹은 더이상 비교할대상이 없을때까지 반복한다.
초기데이터배열이 주어진다.
1. 첫 타겟은 두번째원소부터 시작하며 이전인덱스들은 정렬되었다고 판단한다.
2. 즉 타겟 5는 8이 정렬되었다고보며 8을 기준으로 왼쪽으로 갈지 오른쪽으로갈지 판단한다.
3. 5가 8보다 작으므로 왼쪽으로 보낸다.
1. 두번째 타겟인 9를 이전인덱스인 8과 비교한다.
2. 8보다 작지않으므로 현재위치를 유지한다.
1. 타겟인 2를 9과 비교해 2가 9보다 작으니 교환한다.
2. 2가 8보다 작으니 교환한다.
3. 2가 5보다 작으니 교환한다.
4. 더이상 비교대상이 없으니 해당반복 끝
1. 타겟인 4와 9를 비교해 4가 9보다 작으니 교환한다.
2. 4가 8보다 작으니 교환한다.
3. 4가 5보다 작으니 교환한다.
4. 4는 2보다 작지 않으므로 교환하지않고 현재위치로 정렬된다.
1. 타겟을 더이상 비교할 앞인덱스가 없거나 타겟보다 앞인덱스가 작을때까지 반복한다.
🚩 위의 그림을 보면 알겠지만 회색배경을 갖고있는 삽입정렬이 이루어진 원소는 항상 오름차순을 유지한다.
회색배경의 인덱스들은 정렬된 상태라는것이고 그렇기때문에 타겟과 비교할 이전인덱스가 더 작다면
이전인덱스 앞의 원소들은 지금 비교하는 인덱스보다 작을것이므로 더이상비교하지않고 해당위치에 정렬되는것이다
📌 코드구현
package sort;
public class InsertionSort {
public static void main(String[] args) {
int[] data = {8,5,9,2,4,1};
for(int i=1;i<data.length;i++) {
for(int j=i;j>0;j--) {
if(data[j]<data[j-1]) {
int temp = data[j];
data[j]=data[j-1];
data[j-1]=temp;
}else {
break;
}
}
// 사이클별 정렬확인용
System.out.print(i+"cycle : ");
for(int x=0;x<data.length;x++) {
System.out.print(data[x]+" ");
}
System.out.println();
}
}
}
🚩 해당인덱스와 이전인덱스를 비교하며 temp를 사용해 한칸씩 뒤로 밀어낸다.
else인경우 즉, 이전인덱스가 더 작다면 그 앞쪽까지는 볼필요없이 해당위치에서 정렬될것이므로 break를 수행하면된다.
출력결과
📌 삽입정렬 정리
삽입정렬의 경우 거의 정렬된 상태의 배열에서 좋은 성능을 보이기때문에실제로 병합정렬과 삽입정렬을 혼합한 Tim Sort(팀정렬)이 있다.또 삽입정렬을 변형해 만든 Shell Sort(셸정렬)도 있다. 즉 이곳저곳에 적용이 많이되어있으므로 기본이되는 삽입정렬에대한 메커니즘은 확실히 이해하고있어야한다.
🟢 장점
- 추가메모리 소비가 작다.
- 거의 정렬된 경우 매우효율적으로, 최선의경우라면 O(N)의 시간복잡도를 가진다.
- 안정정렬이 가능하다.
🔴 단점
- 역순에 가까울수록 매우 비효율적으로, 최악의 경우 O(N^2)의 시간복잡도를 가진다.
- 데이터의 상태에따라 성능편하가 매우크다.
-출처
https://st-lab.tistory.com/179?category=892973
https://scshim.tistory.com/267