정렬알고리즘_삽입정렬 [3/8]

[ 삽입 정렬이란? ]

• 정렬 기준에 맞도록 배열의 중간에 끼워넣는 방식
• 앞쪽부터 계속 데이터 정렬을 수행하기 때문에 뒤로 갈 수록 수행 횟수가 줄어듦
• 일반 배열의 경우 값을 중간에 삽입하면 다른 데이터들을 뒤로 밀어줘야하기 때문에 비효율적
• 시간 복잡도 또한 O(n^2)로 비효율적인 구조에 속함 (최악정렬, 역순으로 정렬돼있을 경우)
• 선택정렬과 버블 정렬에 대비 수행횟수가 줄어들어 효율적인 편

---

 

 

삽입 정렬은 역순으로 정렬되어 있을 경우 매우 비효율적이며, 반대로 거의 정렬이 완성돼 있는 경우에는 매우 효율적인 구조가 됩니다.

​

랜덤하게 정렬돼 있는 경우 또는 지속적으로 정렬을 해줘야하는 상황이라면 데이터가 많을 수록 배열의 이동이 많아지기 때문에 비효율적이 됩니다. 따라서 데이터 정렬이 항상 필요한 경우는 일반 배열(리스트)보다 연결리스트를 사용하는 것이 바람직합니다.

 

#include <stdio.h>
#define SIZE 10

void main()
{
	int arr[SIZE] = { 5,4,9,3,6,7,8,1,2,10 };

	for (int i = 1; i < SIZE; ++i)
	{
		int j = i - 1;
		while (j >= 0 && arr[j] > arr[i])
			j--;

		// 반복문을 빠져나오면 arr[j]는 arr[i]보다 작은 숫자인 상태
		// arr[j+1]에 arr[i]를 삽입해주고 나머지는 한칸씩 뒤로 밀어주면 됨
		
		if (j != i - 1)	// 반복문을 아예 들어가지 않았다면 바로 이전 숫자가 더 작은 것을 의미
		{
			int temp = arr[i];
			for (int w = i - 1; w > j; --w)
				arr[w + 1] = arr[w];  // j + 1 부터 i - 1까지 한칸씩 뒤로 밀어줌
			arr[j + 1] = temp;  // j + 1에는 임시저장한 값을 부여해줌			
		}

	}

	for (int i = 0; i < SIZE; ++i)
		printf("%d ", arr[i]);
}