23. 7. 16

# 삽입정렬
현재 비교하고자 하는 타겟과 그 이전의 원소들과 비교하며 자리를 교환하는 정렬 방법이다.
첫 번째 타겟은 두 번째 원소부터.

비교정렬, 제자리 정렬(임시변수쓰긴함), 안정 정렬.

for(int i=0;i<N;i++){
	int target = a[i];
    
    int j = i - 1;
    
    while(j>=0 && target < a[j]) {
    	a[j+1] = a[j]l
        j--;
    }
    
    a[j+1] = target;
}

장점
 - 추가적인 메모리 소비가 작다.
 - 거의 정렬 된 경우 매우 효율적이다. 즉, 최선의 경우 O(N)의 시간복잡도를 갖는다.
 - 안정정렬이 가능하다.
 
단점
 - 역순에 가까울 경우 매우 비효율적이다. 즉, 최악의 경우 O(N^2)의 시간 복잡도를 갖는다.
 - 데이터의 상태에 따라서 성능 편차가 매우 크다.
 
버블정렬이나 선택정렬과 이론상 같은 시간복잡도를 갖지만 O(N^2)
횟수에 대한 기대값이 상대적으로 적기 때문에 평균 시간복잡도가 O(N^2)인 정렬 알고리즘 중에는 빠른편에 속하는 알고리즘이다.


# 쉘 정렬
간격을 정해 각각 삽입정렬을 수행 후 간격을 좁히면서 정렬 완성.
일정 간격만큼 패스하면서 '거의 정렬 된 상태'로 만들고 최종적으로 간격이 '1'인 삽입정렬을 시도.

간격이 너무 적으면 건너 뛰는 간격이 적어 pass 속도가 느려지고, 또 너무 넓으면 오버헤드가 발생.
그래서 많은 사람들이 평균적으로 좋은 간격 갭 시퀸스, Gap Sequences를 찾아냄.
{1, 4, 10, 23, 57, 132, 301, 701, 1750} 이 이상은 2.25를 곱해서 확장.

삽입정렬의 장점은 살리면서 단점을 최소화. (정렬 거의 되었으면 빠르지만 역방향일 경우 매우 느린..)
비교정렬, 제자리 정렬, 불안정정렬.




장점
 - 멀리 있는 원소들끼리 빠르게 비교 및 교환이 이루어진다.
 - 삽입정렬, 버블정렬에 비해 정렬 속도가 빠르다.
 
단점
 - 일반적인 삽입정렬에 비해 구현이 까다롭다.
 - gap sequence에 영향을 많이 받으며 적절한 시퀀스를 선택해야 한다.
 - 일정 간격을 두고 원소의 교환이 이루어지기 때문에 안정정렬이 아니다.
 
 
 
 
 
 
 
 # 원시타입, 참조타입
 원시타입, Primitive type
 총 8개의 기본형 타입을 미리 정의하여 제공. boolean, byte, short, int, long, float, double, char
 기본값이 있기 때문에 Null이 존재하지 않는다. 만약 기본형에 Null을 넣고 싶으면 래퍼클래스.
 실제 값을 저장하는 공간으로 스택 메모리에 저장된다.
 
 참조형 타입, Reference type
 기본형 타입 제외한 모든 타입.
 빈 객체를 의미하는 Null이 존재.
 값이 저장되어 있는 곳의 주소값을 저장하는 공간으로 Heap 메모리에 저장.
 문법 상으로는 에러가 없지만 실행때 에러가 나는 런타임 에러가 발생.