[알고리즘 개념] Insertion Sort

Insertion Sort란?

• Selection Sort처럼 정렬 중간 과정에 데이터가 두 부분으로 나눠 집니다.
• Stable하며 In-place한 정렬입니다.
• 왼쪽에는 정렬이 된 데이터입니다.
• 오른쪽은 정렬이 되지 않은 데이터입니다.
  • 오른쪽 데이터의 제일 앞 숫자를 그 왼쪽의 정렬된 데이터의 제 위치에 삽입합니다.
  • 중간의 모든 데이터는 오른쪽으로 한 칸씩 이동합니다.

Insertion Sort sorting 과정

Insertion Sort 코드

#include <stdio.h>
using namespace std;
#define MAX_SIZE 1000
void insertionSort(int a[], int n);
int main()
{
    int numTestCases;
    scanf("%d", &numTestCases);
    for (int i = 0; i < numTestCases; ++i)
    {
        int num;
        int a[MAX_SIZE];
        scanf("%d", &num);
        for (int j = 0; j < num; j++)
            scanf("%d", &a[j]);
        insertionSort(a, num);
        printf("\n");
    }
    return 0;
}

/* Insertion Sort 함수 */
void insertionSort(int a[], int n)
{
    int countCmpOps = 0; // 비교 연산자 실행 횟수 int countSwaps = 0; // swap 함수 실행 횟수
    int countSwaps = 0;
    int i,j;
    // insertion sort 알고리즘 구현
    for(i=1; i<n; i++){
        int tmp = a[i];
        
        for(j =i-1 ;j>=0 && a[j]>tmp;j--){
            a[j+1] = a[j];
            countSwaps ++;
            countCmpOps ++;
        }
        a[j+1] = tmp;
        if (j >= 0){
            countCmpOps ++ ;
        }


    }
    printf("%d %d ", countCmpOps, countSwaps);
}