이번에는 힙 정렬에 대해서 정리해보려고한다.

힙 정렬이란?

• 퀵 정렬은 불안정 정렬로 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 방법이다.

코드 (Java)

for(int i = 1; i < number; i++){
    int tmp = numArr[i], j;
    for(j = i-1; j >= 0; j--){
        if(numArr[j] > tmp){
            numArr[j+1] = numArr[j];
        }else{
            break;
        }
    }
    numArr[j+1] = tmp;
}

• 코드에서도 볼 수 있다싶이 두 번째 자료부터 시작해서 이전의 정렬되어있는 자료들과 비교하는 로직으로 짜여있다.
• 추가로 j를 상위해서 선언하여 위치를 기억하고 값을 변경하는 구조로 되어있다.

시간복잡도

• 삽입 정렬의 시간복잡도는 평균적으로는 **O(n^2)**으로 이루어진다.
• 최선의 상황에서는 비교만 이루어지고 교환은 이루어지지 않아 O(n)의 시간복잡도를 가진다.
• 최악의 상황(역순으로 되어있는 경우)에서는 for문을 통해 전체를 탐색하고 2중 for문을 통해 전체를 비교하고 교환하게 되면서 **O(n^2)**이 되게 된다.

참고 -

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html