자료구조_정렬 ③ 삽입정렬

 

[1] 삽입정렬

---

(1) 삽입정렬 개념

카드정렬

insertion 정렬

기존의 정렬된 데이터에 새로운 데이터가 삽입될때 정렬된 데이터들과 삽입할 데이터를 비교하여 데이터가 삽입될 위치를 찾아서 정렬하는 방식

(2) 삽입정렬 과정 

 

주어진 정렬을 오름차순으로 정렬한다 . 삽입정렬 방법을 사용한다 

 

 

 

 

첫번째 쓰루패스에서 정렬에서 삭제하고 임시공간으로 이동한다 

8과 임의공간 4 를 비교했을때 

8이 더 크면 

8을 빈공간으로 오른쪽으로 시프트 한다

 

임의공간에 있는 4를 빈공간을 삽입한다

 

두번째 쓰루패스에서 인덱스 2를 삭제하고 임의공간으로 이동한다 

8과 임의공간에 있는 2를 비교했을때 8이 더 크면 8을 빈공간으로 오른쪽으로 시프트하고

빈공간의 옆인 4가 임의공간의 2를 비교시 더 크면 4를 빈공간으로 오른쪽으로 시프트한다

 

임의공간 2를 빈공간에 넣는다 

 

다시 반복하여 정렬한다 

 

(3) 시간복잡도 O(N⌒2)

임시공간에 넣기 위해 target 변수에 담는다 

target 변수 -1 인덱스 위치가 빈공간의 왼쪽 공간이다 

빈공간의 왼쪽공간 j 과 임시공간인 target을 비교한다 

 

반복문( 왼쪽공간 j 가  빈공간인 j+1 에 넣는다 . 왼쪽공간 j 의 값을 -1 한다 ) 

 

j+1 위치에 임의공간 값을 넣는다 

 

public class Insertion_Sort {
 
	public static void insertion_sort(int[] a) {
		insertion_sort(a, a.length);
	}
	
	private static void insertion_sort(int[] a, int size) {
		
		
		for(int i = 1; i < size; i++) {
			
            int target = a[i];
			
			int j = i - 1;
			
			while(j >= 0 && target < a[j]) {
				a[j + 1] = a[j];	
				j--;
			}
            
			a[j + 1] = target;	
		}
	}
}

 

 

비교 N 과 시프트 N = N⌒2

삭제 N-1 

삽입 N-1 

총 빅오 표기법 N⌒2 + 2N-2 = N⌒2 

 

 

빅오표기법 기준으로 삽입정렬 > 선택정렬 > 버블정렬 으로 같은  N⌒2 이지만 연산결과 차이는 있다 

 

	최선의 시나리오	평균 시나리오	최악의 시나리오
선택정렬	N⌒2 /2	N⌒2 /2	N⌒2 /2
삽입정렬	N	N⌒2 /2	N⌒2

최선과 최악의 데이터를 가진 확률은 많지 않다 

데이터를 알수 없다면 평균 시나리오로 거의 동일한 수치를 얻는다 

하지만 데이터에 따라 최선의 시나리오라면 삽입정렬이 나을수 있다. 

데이터에 따라 달라질수 있다.