๊ฑฐํ ์ ๋ ฌ๐งบ
์๊ฐ
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) ๋ฑ์ด ์๋ค.
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์ ํ ์ ๋ ฌ vs ์ฝ์ ์ ๋ ฌ ๋น๊ตโฑ (0) | 2020.10.13 |
---|---|
๋ฉ๋ชจ์ด์ ์ด์ ์ด๋?๐ (0) | 2020.10.07 |
์๊ฐ ๋ณต์ก๋ ๊ฐ์์ ์ผ๋ก ํ์ธํด๋ณด๊ธฐ๐ (0) | 2020.10.01 |
์ ํ ์ ๋ ฌ๐งบ (0) | 2020.10.01 |
์นตํ ์ผ ์ ฐ์ด์ปค ์ ๋ ฌ๐งบ (0) | 2020.09.30 |
๋ธ๋ก๊ทธ์ ์ ๋ณด
Doputer
#๊น๋ํ
๋๊ธ
์์ฑ ํ๋