<div id="readability-page-1" class="page"><div><h2 id="삽입-정렬">삽입 정렬</h2>
삽입 정렬은 간단하면서도 효율적인 정렬 알고리즘 중 하나로, 주로 데이터 양이 적거나 거의 정렬된 경우에 적합하다. 삽입 정렬은 배열의 요소를 하나씩 순회하며, 현재 요소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작한다.
<h2 id="작동-원리">작동 원리</h2>
<ol>
<li>초기 설정: 첫 번째 요소는 이미 정렬된 상태로 간주한다.</li>
<li>반복 과정</li>
</ol>
<ul>
<li>두 번째 요소부터 시작해서 배열의 끝까지 각 요소를 순회</li>
<li>현재 요소를 그보다 앞쪽에 있는 정렬된 부분과 비교하여 올바른 위치에 삽입</li>
</ul>
<ol start="3">
<li>완료: 모든 요소를 정렬된 위치에 삽입하면 작업이 종료된다.</li>
</ol>
<img src="https://velog.velcdn.com/images/jwlee010523/post/b3ee6ef0-8d1a-4b7e-8137-72bb0421faf9/image.png">
<img src="https://velog.velcdn.com/images/jwlee010523/post/f3b017cd-2acb-402a-97b0-4398e7f0fc40/image.png">
<h2 id="전체-코드">전체 코드</h2>
<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;time.h&gt;
#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[MAX_SIZE];
int n;

void insertion_sort(int list[], int n) {
	int i, j, key;
	for (i = 1; i &lt; n; i++) {
		key = list[i];
		for (j = i - 1; j &gt;= 0 &amp;&amp; list[j] &gt; 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 &lt; n; i++) 
		list[i] = rand() % 100;

	insertion_sort(list, n);
	for (i = 0; i &lt; n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}</code></pre>
<h2 id="시간-복잡도와-공간-복잡도">시간 복잡도와 공간 복잡도</h2>
<h3 id="시간-복잡도">시간 복잡도</h3>
<ul>
<li>최선의 경우: 데이터가 이미 정렬된 경우로 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math>이다.</li>
<li>최악의 경우: 데이터가 역순으로 정렬된 경우로 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>이다.</li>
<li>평균: <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math></li>
</ul>
<h3 id="공간-복잡도">공간 복잡도</h3>
제자리 정렬로 추가적인 메모리가 거의 필요하지 않기에 O(1)이다.
<blockquote>
출처 
C언어로 쉽게 풀어쓴 자료구조 - 천인구
</blockquote></div></div>

jwlee010523.log

삽입 정렬
삽입 정렬은 간단하면서도 효율적인 정렬 알고리즘 중 하나로, 주로 데이터 양이 적거나 거의 정렬된 경우에 적합하다. 삽입 정렬은 배열의 요소를 하나씩 순회하며, 현재 요소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작한다.
작동 원리
초기 설정: 첫 번째 요소는 이미 정렬된 상태로 간주한다.
반복 과정
두 번째 요소부터 시작해서 배열의 끝까지 각 요소를 순회
현재 요소를 그보다 앞쪽에 있는 정렬된 부분과 비교하여 올바른 위치에 삽입
완료: 모든 요소를 정렬된 위치에 삽입하면 작업이 종료된다.
전체 코드
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
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");
 return 0;
}
시간 복잡도와 공간 복잡도
시간 복잡도
최선의 경우: 데이터가 이미 정렬된 경우로 $O(n)$이다.
최악의 경우: 데이터가 역순으로 정렬된 경우로 $O(n^2)$이다.
평균: $O(n^2)$
공간 복잡도
제자리 정렬로 추가적인 메모리가 거의 필요하지 않기에 O(1)이다.
출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구

삽입 정렬(Insertion Sort)

댓글