<div id="readability-page-1" class="page"><div><h2 id="버블-정렬">버블 정렬</h2>
버블 정렬은 정렬 알고리즘 중 가장 기본적인 형태로, 서로 인접한 두 요소를 비교하여 정렬하는 방식이다. 간단하지만, 효율성 측면에서는 다른 정렬 알고리즘에 비해 떨어진다.
<h2 id="작동-원리">작동 원리</h2>
<ol>
<li>배열의 처음부터 시작하여 인접한 두 요소를 비교한다.</li>
<li>두 요소의 순서가 잘못된 경우, 서로 교환한다.</li>
<li>배열의 끝까지 한 번 순회하면 가장 큰 값이 맨 끝으로 이동한다.</li>
<li>정렬되지 않은 부분만 다시 순회하며 이 과정을 반복한다.</li>
<li>5 모든 요소가 정렬될 때까지 위의 과정을 계속한다.</li>
</ol>
<img src="https://velog.velcdn.com/images/jwlee010523/post/b1f7dfbf-8a9e-435d-aac7-5f6482be7ad7/image.png">
<img src="https://velog.velcdn.com/images/jwlee010523/post/485d542f-6e52-4cd0-93d1-83b1eb1ef9d2/image.png">
<h2 id="시간-복잡도와-공간-복잡도">시간 복잡도와 공간 복잡도</h2>
<h3 id="시간-복잡도">시간 복잡도</h3>
<ul>
<li>최선의 경우: 데이터가 이미 정렬된 경우 교환 없이 확인만 진행하면 되므로 O(n)이다.</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>
<ul>
<li>O(1): 제자리 정렬이므로, 추가 메모리 사용 없음</li>
</ul>
<h2 id="장점과-단점">장점과 단점</h2>
<h3 id="장점">장점</h3>
<ul>
<li>구현이 매우 간단함</li>
<li>배열의 크기가 작거나 데이터가 거의 정렬된 경우 사용할 수 있음</li>
</ul>
<h3 id="단점">단점</h3>
<ul>
<li>비효율적이며, 데이터가 큰 경우 잘 사용하지 않음</li>
<li>일반적으로 자료의 교환 작업이 자료의 이동 작업보다 더 복잡함</li>
</ul>
<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 bubble_sort(int list[], int n) {
	int i, j, temp;
	for (i = n - 1; i &gt; 0; i--) {
		for (j = 0; j &lt; i; j++)
			if (list[j] &gt; list[j + 1])
				SWAP(list[j], list[j + 1], temp);
	}
}

int main(void) {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i &lt; n; i++) 
		list[i] = rand() % 100;

	bubble_sort(list, n);
	for (i = 0; i &lt; n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}</code></pre>
<blockquote>
출처 
C언어로 쉽게 풀어쓴 자료구조 - 천인구
</blockquote></div></div>

jwlee010523.log

버블 정렬
버블 정렬은 정렬 알고리즘 중 가장 기본적인 형태로, 서로 인접한 두 요소를 비교하여 정렬하는 방식이다. 간단하지만, 효율성 측면에서는 다른 정렬 알고리즘에 비해 떨어진다.
작동 원리
배열의 처음부터 시작하여 인접한 두 요소를 비교한다.
두 요소의 순서가 잘못된 경우, 서로 교환한다.
배열의 끝까지 한 번 순회하면 가장 큰 값이 맨 끝으로 이동한다.
정렬되지 않은 부분만 다시 순회하며 이 과정을 반복한다.
5 모든 요소가 정렬될 때까지 위의 과정을 계속한다.
시간 복잡도와 공간 복잡도
시간 복잡도
최선의 경우: 데이터가 이미 정렬된 경우 교환 없이 확인만 진행하면 되므로 O(n)이다.
최악의 경우: 데이터가 역순으로 정렬된 경우로 $O(n^2)$이다.
평균: $O(n^2)$
공간 복잡도
O(1): 제자리 정렬이므로, 추가 메모리 사용 없음
장점과 단점
장점
구현이 매우 간단함
배열의 크기가 작거나 데이터가 거의 정렬된 경우 사용할 수 있음
단점
비효율적이며, 데이터가 큰 경우 잘 사용하지 않음
일반적으로 자료의 교환 작업이 자료의 이동 작업보다 더 복잡함
전체 코드
#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 bubble_sort(int list[], int n) {
 int i, j, temp;
 for (i = n - 1; i > 0; i--) {
 for (j = 0; j < i; j++)
 if (list[j] > list[j + 1])
 SWAP(list[j], list[j + 1], temp);
 }
}
int main(void) {
 int i;
 n = MAX_SIZE;
 srand(time(NULL));
 for (i = 0; i < n; i++) 
 list[i] = rand() % 100;
 bubble_sort(list, n);
 for (i = 0; i < n; i++)
 printf("%d ", list[i]);
 printf("\n");
 return 0;
}
출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구

버블 정렬(Bubble Sort)

댓글