[정렬] 삽입 정렬

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

 

삽입 정렬(Insertion Sort)

Insert Sort

1. 배열의 두번째 부터 끝까지 2~4을 반복한다.
2. 선택된 값(Key)과 이전 배열들의 값을 비교한다.
3. Key값이 작으면 한칸씩 오른쪽으로 쉬프트 해준다.
4. Key값이 크면 다음 배열에 Key값을 넣어준다.

 

시간 복잡도 : O(n^2)

 

---

 

소스코드

#define __main

#ifdef __main

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10

void Init(int arr[]) {
	srand(time(NULL));
	for (int i = 0; i < MAX_SIZE; i++) {
		// 임의의 정수 입력
		arr[i] = rand() % 10000;
	}
}

void Insertion_Sort(int arr[]) {
	int key = 0;
	int p = 0;

	for (int i = 1; i < MAX_SIZE; i++) {
		key = arr[i];
		p = i;
		for (int j = i - 1; j >= 0; j--) {
			if (key < arr[j]) {
				arr[j + 1] = arr[j];
				p = j;
			}
			else break;
		}
		arr[p] = key;
	}
}

void Print(int arr[]) {
	for (int i = 0; i < MAX_SIZE; i++) {
		printf("[%d] -> %d\n", i, arr[i]);
	}
	printf("\n--------------------\n\n");
}

int main() {
	int arr[MAX_SIZE];

	Init(arr);

	Print(arr);

	Insertion_Sort(arr);

	Print(arr);

	return 0;
}

#endif