Doputer

๊ฑฐํ’ˆ ์ •๋ ฌ๐Ÿงบ

์†Œ๊ฐœ

Bubble sort(๊ฑฐํ’ˆ ์ •๋ ฌ)๋Š” ์ธ์ ‘ํ•œ ๋‘ ์›์†Œ๋ฅผ ๊ฒ€์‚ฌํ•˜์—ฌ ์ •๋ ฌํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(n^2)๋กœ ์ƒ๋‹นํžˆ ๋Š๋ฆฌ์ง€๋งŒ, ์ฝ”๋“œ๊ฐ€ ๋‹จ์ˆœํ•ด์„œ ์ž์ฃผ ์‚ฌ์šฉ๋œ๋‹ค. ์ด๋ฆ„์˜ ์œ ๋ž˜๋Š” ์›์†Œ์˜ ์ด๋™์ด ๊ฑฐํ’ˆ์ด ์ˆ˜๋ฉด์œผ๋กœ ์˜ฌ๋ผ์˜ค๋Š” ๋“ฏํ•œ ๋ชจ์Šต์„ ๋ณด์ด๊ธฐ ๋•Œ๋ฌธ์— ์ง€์–ด์กŒ๋‹ค.

 

์ •๋ ฌ ๊ณผ์ •

๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋‹ค์„ฏ ๊ฐœ์˜ ์ •์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, Bubble sort๋กœ ์˜ค๋ฆ„ ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•ด๋ณด๊ฒ ๋‹ค.

 

+-----+-----+-----+-----+-----+
|  5  |  4  |  1  |  3  |  2  |
+-----+-----+-----+-----+-----+

 

์šฐ์„  ์ธ๋ฑ์Šค 0์˜ ๊ฐ’๊ณผ ์ธ๋ฑ์Šค 1์˜ ๊ฐ’์„ ๋น„๊ตํ•˜๋ฉด, ์ธ๋ฑ์Šค 0์˜ ๊ฐ’์ด ๋” ํฌ๊ธฐ ๋•Œ๋ฌธ์— ๋‘ ๊ฐ’์ด ์„œ๋กœ ๊ต์ฒด๋œ๋‹ค.

 

+-----+-----+-----+-----+-----+
|  4  |  5  |  1  |  3  |  2  |
+-----+-----+-----+-----+-----+


์ด์–ด์„œ ์ธ๋ฑ์Šค 1์˜ ๊ฐ’๊ณผ ์ธ๋ฑ์Šค 2์˜ ๊ฐ’์„ ๋น„๊ตํ•ด์„œ ๊ต์ฒดํ•œ๋‹ค.

 

+-----+-----+-----+-----+-----+
|  4  |  1  |  5  |  3  |  2  |
+-----+-----+-----+-----+-----+

 

์ด์–ด์„œ ์ธ๋ฑ์Šค 2์˜ ๊ฐ’๊ณผ ์ธ๋ฑ์Šค 3์˜ ๊ฐ’์„ ๋น„๊ตํ•ด์„œ ๊ต์ฒดํ•œ๋‹ค.

 

+-----+-----+-----+-----+-----+
|  4  |  1  |  3  |  5  |  2  |
+-----+-----+-----+-----+-----+

 

์ด์–ด์„œ ์ธ๋ฑ์Šค 3์˜ ๊ฐ’๊ณผ ์ธ๋ฑ์Šค 4์˜ ๊ฐ’์„ ๋น„๊ตํ•ด์„œ ๊ต์ฒดํ•œ๋‹ค.

 

+-----+-----+-----+-----+-----+
|  4  |  1  |  3  |  2  |  5  |
+-----+-----+-----+-----+-----+

 

์ดˆ๊ธฐ ์ƒํƒœ์™€ ๋น„๊ตํ–ˆ์„ ๋•Œ ์ฒซ ๋ฒˆ์งธ ์›์†Œ์˜€๋˜ 5๊ฐ€ ๊ฐ€์žฅ ์šฐ์ธก์œผ๋กœ ์ด๋™ํ•œ ๊ฒƒ์„ ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

 

์ด์ œ ์›์†Œ๋“ค์„ ๋๊นŒ์ง€ ๊ฒ€์‚ฌํ–ˆ์œผ๋‹ˆ ๋‹ค์‹œ ์ฒ˜์Œ์œผ๋กœ ๋Œ์•„๊ฐ€์„œ ์ƒˆ๋กญ๊ฒŒ ๊ฒ€์‚ฌ๋ฅผ ์‹œ์ž‘ํ•œ๋‹ค. ๋‹ค๋งŒ, ๋‹ค์Œ ๊ฒ€์‚ฌ๋ถ€ํ„ฐ ๋‹ฌ๋ผ์ง€๋Š” ์ ์€ ๊ฐ€์žฅ ํฐ ์›์†Œ๊ฐ€ ๊ฐ€์žฅ ์šฐ์ธก์œผ๋กœ ์ด๋™ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์— ๋‹ค์Œ ๊ฒ€์‚ฌ๋ถ€ํ„ฐ๋Š” ํ•œ ์นธ ์ „๊นŒ์ง€๋งŒ(์ธ๋ฑ์Šค 3) ๊ฒ€์‚ฌํ•˜๋ฉด ๋œ๋‹ค.

 

์—ฐ์†ํ•ด์„œ ๊ฒ€์‚ฌ๋ฅผ ์‹œ์ž‘ํ•œ๋‹ค.

 

+-----+-----+-----+-----+-----+
|  1  |  4  |  3  |  2  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  3  |  4  |  2  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  3  |  2  |  4  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  3  |  2  |  4  |  5  |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |
+-----+-----+-----+-----+-----+

 

๋งˆ์ง€๋ง‰ ํ‘œ์—์„œ ์ธ๋ฑ์Šค 0๊ณผ ์ธ๋ฑ์Šค 1์˜ ๊ฒ€์‚ฌ๋„ ๋๋‚œ ๊ฒƒ ๊ฐ™์•„ ๋ณด์ด์ง€๋งŒ, ์šฐ๋ฆฌ๋Š” ํ˜„์žฌ ๊ฐ€์‹œ์ ์œผ๋กœ ๊ฐ’์„ ๋ณด๊ณ  ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๊ณ , ์ปดํ“จํ„ฐ๋Š” ๋งˆ์ง€๋ง‰ ๊ฒ€์‚ฌ๋ฅผ ์ˆ˜ํ–‰ํ•ด์•ผ ํ•œ๋‹ค.

 

+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |
+-----+-----+-----+-----+-----+

 

์ธ๋ฑ์Šค 0๋งŒ ๋‚จ์€ ๊ฒฝ์šฐ์—๋Š” ๋” ์ด์ƒ ๊ฒ€์‚ฌ๋ฅผ ํ•ด์ค„ ํ•„์š”๊ฐ€ ์—†๋‹ค. ์ด๋ฏธ ์•ž์„  ์ •๋ ฌ์—์„œ ์ •๋ ฌ์„ ์™„๋ฒฝํ•˜๊ฒŒ ์ˆ˜ํ–‰ํ–ˆ๋‹ค๋ฉด ๊ฐ€์žฅ ์ž‘์€ ์›์†Œ๋งŒ ๋‚จ์•„์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

 

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ถ„์„

๋น„๊ต ํšŸ์ˆ˜

๊ฑฐํ’ˆ ์ •๋ ฌ์€ ํ•œ ๋ฒˆ์˜ ๊ฒ€์‚ฌ๋งˆ๋‹ค ๋น„๊ต ๋Œ€์ƒ์ด ํ•˜๋‚˜์”ฉ ์ค„์–ด๋“ ๋‹ค. ์ „์ฒด ์›์†Œ์˜ ๊ฐœ์ˆ˜๊ฐ€ n๊ฐœ๋ฉด, ์ด (n - 1) ๋ฒˆ ๊ฒ€์‚ฌํ•˜๋ฉด ํ•œ ๋ฒˆ ์ •๋ ฌ์ด ์™„๋ฃŒ๋œ๋‹ค.

 

์•ž ์„  ์˜ˆ์ œ์—์„œ ์ด ์›์†Œ๊ฐ€ 5๊ฐœ ์ด๋ฏ€๋กœ, 4 + 3 + 2 + 1 = 10๋ฒˆ ๊ฒ€์‚ฌํ•˜๋ฉด ์ „์ฒด ์ •๋ ฌ์ด ์™„๋ฃŒ๋œ๋‹ค. ์ด๋ฅผ ์ˆ˜์‹์œผ๋กœ ์ผ๋ฐ˜ํ™”ํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

 

$$

(n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2 = \frac{n(n - 1)} {2}

$$

 

์ž๋ฆฌ ๊ตํ™˜ ํšŸ์ˆ˜

์ตœ์„ ์˜ ๊ฒฝ์šฐ(์ด๋ฏธ ์ •๋ ฌ๋œ ์›์†Œ๋“ค์ด ์ฃผ์–ด์ง€๋Š” ๊ฒฝ์šฐ), ์ž๋ฆฌ ๊ตํ™˜์ด ์ด๋ฃจ์–ด์ง€์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ์‹œ๊ฐ„ ๋ณต์žก๋„์— ์˜ํ–ฅ์ด ์—†๋‹ค.

 

๊ทธ๋Ÿฌ๋‚˜ ์ตœ์•…์˜ ๊ฒฝ์šฐ(์—ญ์ˆœ ์ •๋ ฌ๋œ ์›์†Œ๋“ค์ด ์ฃผ์–ด์ง€๋Š” ๊ฒฝ์šฐ), ๋ชจ๋“  ๊ฒ€์‚ฌ์—์„œ ์ž๋ฆฌ ๊ตํ™˜์ด ์ด๋ฃจ์–ด์ง„๋‹ค. ์ด ๊ฒฝ์šฐ ์ตœ๋Œ€ ๋น„๊ต ํšŸ์ˆ˜์ธ (n - 1) * n / 2๋ฒˆ์ด ๋œ๋‹ค.

 

๋”ฐ๋ผ์„œ ํ‰๊ท ์ ์œผ๋กœ O(n^2)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

 

๊ตฌํ˜„

์•ž ์„  ์˜ˆ์ œ๋ฅผ ์ฝ”๋“œ๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

 

void bubble_sort(int *array)
{
	int temp;

	for (int i = 0; i < SIZE - 1; i++)
	{
		for (int j = 0; j < SIZE - i - 1; j++)
		{
			if (array[j] > array[j + 1])
			{
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
}

 

์ •๋ฆฌ

๊ฑฐํ’ˆ ์ •๋ ฌ์€ ์ง๊ด€์ ์œผ๋กœ ์ดํ•ดํ•  ์ˆ˜ ์žˆ๊ณ , ์ฝ”๋“œ๋„ ๋‹จ์ˆœํ•˜๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ๋†’์€ ์‹œ๊ฐ„ ๋ณต์žก๋„ ๋•Œ๋ฌธ์— ๋ฐ์ดํ„ฐ์˜ ์–‘์ด ๋งŽ์€ ๊ฒฝ์šฐ์— ์„ฑ๋Šฅ์ด ์ €ํ•˜๋œ๋‹ค.

 

์˜ˆ์ œ์—์„œ๋Š” 5๊ฐœ์˜ ์›์†Œ๋ฅผ ์ •๋ ฌํ•˜์—ฌ 10๋ฒˆ์˜ ๊ฒ€์‚ฌ๋ฅผ ์ˆ˜ํ–‰ํ–ˆ์ง€๋งŒ, 1์–ต ๊ฐœ์˜ ์›์†Œ๋ฅผ ์ •๋ ฌํ•˜๋Š” ๊ฒฝ์šฐ์—๋Š” ์•ฝ 5์ฒœ์กฐ ๋ฒˆ ๊ฒ€์‚ฌ๋ฅผ ์ˆ˜ํ–‰ํ•ด์•ผ ํ•œ๋‹ค. ์ด๋Š” ํ€ต ์ •๋ ฌ๋ณด๋‹ค ์•ฝ ์ฒœ๋งŒ ๋ฐฐ ๋Š๋ฆฌ๋‹ค.

 

์ถ”๊ฐ€๋กœ ๊ฑฐํ’ˆ ์ •๋ ฌ์„ ๊ฐœ์„ ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ์—ฌ๋Ÿฌ ๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค.

์ตœ์„ ์˜ ๊ฒฝ์šฐ๋ฅผ ๊ฒ€์‚ฌํ•ด์„œ ์ •๋ ฌ์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š” ๋ฐฉ๋ฒ•, ๊ฑฐํ’ˆ ์ •๋ ฌ์„ ์–‘๋ฐฉํ–ฅ์œผ๋กœ ์ˆ˜ํ–‰ํ•˜๋Š” ์นตํ…Œ์ผ ์…ฐ์ด์ปค ์ •๋ ฌ(cocktail shaker sort), ํŠน์ •ํ•œ ๊ฐ์†Œ๋Ÿ‰(shrink factor)์— ์˜ํ•ด ์ฐจ์ด(gap)๋ฅผ ์ค„์—ฌ๊ฐ€๋ฉฐ ์ •๋ ฌํ•˜๋Š” ๋น—์งˆ ์ •๋ ฌ(comb sort) ๋“ฑ์ด ์žˆ๋‹ค.

๋ฐ˜์‘ํ˜•

์ด ๊ธ€์˜ ํƒœ๊ทธ

๋ธ”๋กœ๊ทธ์˜ ์ •๋ณด

Doputer

#๊น€๋„ํ˜„

ํ™œ๋™ํ•˜๊ธฐ