반응형
1. 삽입정렬이란?
삽입정렬은 정렬 안된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해가면서 정렬을 진행하는 것이다.
전체적인 원리는 처음 5는 정렬되어있다고 생각하고 3부터 2,4,1을 차례대로 정렬을 진행한다.
이를 위한 구체적인 다른 예시를 봐보자
아래와 같이 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾는것이다.
2. 삽입정렬 구현
구현설명은 코드 주석을 봐보자
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | public class InsertionSort { public static void main(String[] args) { int[] arr = {3, 2, 4, 1}; SelSort(arr, arr.length); for(int i=0; i<arr.length; i++) System.out.print(arr[i]); } static void SelSort(int[] arr, int n) { int i, j; int temp; for(i=1; i<n; i++)//i는 1부터시작 맨첫번째 값은 정렬완료된거로 하자. { temp = arr[i]; // 정렬 대상을 temp에 저장 for(j=i-1; j>=0 ; j--) { if(arr[j] > temp)//데이터간 비교 연산 arr[j+1] = arr[j]; //데이터간 이동 연산 , 비교 대상 한 칸씩 계속 뒤로 밀기 else break; // 삽입 위치 찾았으니 탈출! } arr[j+1] = temp; // 찾은 위치에 정렬 대상 삽입! } } } | cs |
3. 성능 평가
비교횟수는 다음 반복문 안에 위치한 if문의 실행 횟수를 기준으로 계산할 수 있다.
if(arr[j] > temp)
arr[j+1] = arr[j];
4개의 데이터를 3단계에 걸쳐서 정렬하였다. 최악의경우 비교의 횟수를 더한 결과는 1+2+3 이었다.
이렇듯 버블 정렬의 데이터의 수가 n개일때 진행되는 비교의 횟수는 다음과 같다.
1 + 2+...+(n-2) + (n-1)
그리고 이 역시 등차수열의 합에 해당하므로 앞서본 선택정렬,버블정렬과 마찬가지로
빅-오는 O(n^2) 이다.
반응형