c언어 - 삽입 정렬 (Insertion Sort)

정렬되는 모습이 마치 삽입되는 것과 유사해 삽입 정렬로 불린다.

삽입 정렬은 이전에 봤던 순차, 버블, 선택 정렬과 큰 차이점이 있다면 최선의 경우 N번의 비교 후 정렬이 종료된다. 비교 시 자기 자신보다 작은 수가 있으면 멈추고 다음 자리로 가 비교를 시작하기 때문이다. 그러므로 더 효율적이고 자주 이용되는 정렬이다.

 

 

 

비교하는 값은 노란색

정렬후 값은 보라색

 

---

핵심 알고리즘

---

void InsertionSort(int *arr,int n, int i, int j){
    int key;
    for(i=1; i<n; i++){
        key = arr[i];
        for(j=i-1; j>=0; j--){
            if(arr[j] > key)
                arr[j+1] = arr[j];
            else
                break;
        }
        arr[j+1] = key;
    }
}

 

코드

---

#include <stdio.h>

void InsertionSort(int *arr, int n, int i, int j);
void printarr(int *arr, int n, int i, int j);
void swap(int *a,int *b);

int main(){
  int arr[] = {7,5,4,8,6};
  InsertionSort(arr,5,0,0);

  return 0;
}

void InsertionSort(int *arr,int n, int i, int j){
    int key;
    printarr(arr, n, -5, 5);
    for(i=1; i<n; i++){
        key = arr[i];
        for(j=i-1; j>=0; j--){
        printarr(arr, n, i, j);
            if(arr[j] > key)
                arr[j+1] = arr[j];
            else
                break;
        }
        arr[j+1] = key;
    }
  printarr(arr, n, n, -2);
}

void printarr(int *arr, int n, int i, int j) {
    for(int c = 0; c<n; c++) {
        if ( c == j)
            printf("\x1b[33m");
        else if ( c < i) {
            printf("\x1b[35m");
        }
        else if ( c == i) {
            printf("\x1b[33m");
        }
        else{
            printf("\x1b[37m");
        }
        printf(" %d ", arr[c]);
    }
    printf("\n");
}

void swap(int *a,int *b) {
    int t;
    t = *a;
    *a = *b;
    *b = t;
}