[알고리즘][정렬] 삽입 정렬

삽입 정렬

정의

출처- https://visualgo.net/ko

• 기존에 정렬된 부분 집합에 정렬할 자료의 위치를 찾아 삽입하는 정렬 방식

각 숫자를 적절한 위치에 삽입한다

빨간색이 현재 키 정렬하려는 키 값이 된다. 앞에 있는 주황색들은 이미 정렬이 된 상태이다. 그래서 정렬된 부분을 초록색이 순회하면서 빨간색보다 키 값이 작으면 멈추고 그 자리에 삽입한다.

구현1

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
void printArray(int value[], int count) {
	int i = 0;
	for (i = 0; i < count; i++) {
		printf("%d ", value[i]);
	}
	printf("\n");
}

void insertionSort(int value[], int count) {
	int i = 0, j = 0;
	int temp = 0;
	for (i = 1; i < count; i++) {
		temp = value[i];//정렬할 키 값
		j = i;//삽입할 위치 찾기
		while (j > 0 && value[j - 1] > temp) {//오름차순 정렬되어있으므로 맨 뒤에서부터 첫째 자료까지 temp값보다 작은 자료를 찾을 때까지 반복
			value[j] = value[j - 1];//오른쪽으로 자료 이동
			j = j - 1;//앞으로 이동
		}
		value[j] = temp;//해당 위치에 삽입

		printf("Step-%d ", i);
		printArray(value, count);
	}
}

int main() {
	int values[] = { 80,50,70,10,60,20,40,30 };
	printf("Before Sort\n");
	printArray(values, 8);

	insertionSort(values, 8);

	printf("After Sort\n");
	printArray(values, 8);
}

구현2

#include <stdio.h>
#pragma warning(disable:4996)
int main(void) {
	int array[10] = { 1,10,5,8,7,6,4,3,2,9 };
	int i, j, temp;
	for (i = 0; i < 9; i++) {
		j = i;//현재 정렬할 원소
		while (array[j] > array[j + 1]) {
			temp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = temp;
			j--;
		}
	}
	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
}

구현3

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
#define MAX_SIZE 10
int list[MAX_SIZE];
int n;
void insertion_sort(int list[], int n) {
	int i, j, key;
	for (i = 1; i < n; i++) {
		key = list[i];
		for (j = i - 1; j >= 0 && list[j] > key; j--) {
			list[j + 1] = list[j];
		}
		list[j + 1] = key;
	}
}
int main(void) {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i < n; i++) {
		list[i] = rand() % 100;
	}
	insertion_sort(list, n);
	for (i = 0; i < n; i++) {
		printf("%d ", list[i]);
	}
	printf("\n");
}

특성

• 최선: O($n$)
• 평균, 최악: O($n^2$)
• 효율성이 좋진 않음 but 정렬 전 상태에 따라 효율성 차이가 있음
• 정렬의 안정성 유지