์ ํ ์ ๋ ฌ๐งบ
์๊ฐ
Selection sort(์ ํ ์ ๋ ฌ)๋ ์ ์๋ฆฌ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ํ๋๋ก ๊ฐ์ฅ ์์(ํน์ ๊ฐ์ฅ ํฐ) ์์๋ฅผ ์ฐพ์์ ๊ต์ฒดํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ง ๊ทธ๋๋ก ์์๋ฅผ ์ ํํด์ ์ ๋ ฌํ๋ค.
์ ๋ ฌ ๊ณผ์
๋ค์๊ณผ ๊ฐ์ด ๋ค์ฏ ๊ฐ์ ์ ์๊ฐ ์ฃผ์ด์ก์ ๋, Selection sort๋ก ์ค๋ฆ ์ฐจ์์ผ๋ก ์ ๋ ฌํด๋ณด๊ฒ ๋ค.
+-----+-----+-----+-----+-----+
| 5 | 4 | 1 | 3 | 2 |
+-----+-----+-----+-----+-----+
์ฐ์ ์ธ๋ฑ์ค 0์ ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง ์ธ๋ฑ์ค๋ผ๊ณ ๊ฐ์ ํ๊ณ , ์ธ๋ฑ์ค 1๋ถํฐ ์์ ๋๊น์ง ์ํํ๋ฉด์ ๊ฐ์ฅ ์์ ์์๋ฅผ ์ฐพ๋๋ค. ๊ทธ๋ฆฌ๊ณ ์ฐพ์ ์์๋ฅผ ๊ฐ์ฅ ์ฒ์ ์์์ ๊ต์ฒดํ๋ค.
+-----+-----+-----+-----+-----+
| 1 | 4 | 5 | 3 | 2 |
+-----+-----+-----+-----+-----+
๊ฐ์ฅ ์์ ์์๊ฐ ์ฒ์ ์์์ ๊ต์ฒด๋๊ธฐ ๋๋ฌธ์ ๋ค์ ๋จ๊ณ๋ถํฐ๋ ์ธ๋ฑ์ค 1์ ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง ์ธ๋ฑ์ค๋ผ๊ณ ๊ฐ์ ํ๊ณ , ์ธ๋ฑ์ค 2๋ถํฐ ์์ ๋๊น์ง ์ํํ๋ฉด์ ๊ฐ์ฅ ์์ ์์๋ฅผ ์ธ๋ฑ์ค 1์ ์์์ ๊ต์ฒดํ๋ค.
+-----+-----+-----+-----+-----+
| 1 | 2 | 5 | 3 | 4 |
+-----+-----+-----+-----+-----+
์ด์ด์ ๋์ผํ ๋ฐฉ๋ฒ์ผ๋ก ์์ ์์น๋ฅผ ํ ์นธ์ฉ ์ฆ๊ฐ์ํค๋ฉด์ ๊ฐ์ฅ ์์ ์์์ ๊ต์ฒดํด์ฃผ๋ฉด ๋๋ค.
+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 5 | 4 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 |
+-----+-----+-----+-----+-----+
์๊ณ ๋ฆฌ์ฆ ๋ถ์
๋น๊ต ํ์
์ ํ ์ ๋ ฌ์ ํ ๋ฒ์ ์ํ๊ฐ ๋๋๋ฉด ๋ค์ ์ํ๋ ๋น๊ต ๋์์ด ํ๋์ฉ ์ค์ด๋ ๋ค. ์ ์ฒด ์์์ ๊ฐ์๊ฐ n๊ฐ๋ฉด, ์ด (n - 1) ๋ฒ ๊ฒ์ฌ๋ฅผ ํ์ ๋ ํ ๋ฒ ์ ๋ ฌ์ด ์๋ฃ๋๋ค.
์ ์ ์์ ์์ ์ด ์์๊ฐ 5๊ฐ ์ด๋ฏ๋ก, 4 + 3 + 2 + 1 = 10๋ฒ ๊ฒ์ฌํ๋ฉด ์ ์ฒด ์ ๋ ฌ์ด ์๋ฃ๋๋ค. ์ด๋ฅผ ์์์ผ๋ก ์ผ๋ฐํํ๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
$$
(n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2 = \frac{n(n - 1)}{2}
$$
์๋ฆฌ ๊ตํ ํ์
์ต์ ์ ๊ฒฝ์ฐ(์ด๋ฏธ ์ ๋ ฌ๋ ์์๋ค์ด ์ฃผ์ด์ง๋ ๊ฒฝ์ฐ), ์๋ฆฌ ๊ตํ์ด ์ผ์ด๋์ง ์์์ ์๊ฐ ๋ณต์ก๋์ ์ํฅ์ด ์๋ค.
๊ทธ๋ฌ๋ ์ต์ ์ ๊ฒฝ์ฐ(์ญ์ ์ ๋ ฌ๋ ์์๋ค์ด ์ฃผ์ด์ง๋ ๊ฒฝ์ฐ), ์ํ ํ์ ๋งํผ ์๋ฆฌ ๊ตํ์ด ์ผ์ด๋๋ค.
๊ตฌํ
void selection_sort(int *array)
{
int temp, minIndex;
for (int i = 0; i < SIZE - 1; i++)
{
minIndex = i;
for (int j = i + 1; j < SIZE; j++)
{
if (array[minIndex] > array[j])
minIndex = j;
print_array(array);
}
temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
์ ๋ฆฌ
์ ํ ์ ๋ ฌ๊ณผ ๊ฑฐํ ์ ๋ ฌ์ ์ธ๋ป ๋น์ทํด๋ณด์ธ๋ค. ๊ทธ๋ฌ๋ ๊ฑฐํ ์ ๋ ฌ์ ์ต์ ์ ๊ฒฝ์ฐ ์ธ์ ํ ๋ชจ๋ ์์๋ง๋ค ์๋ฆฌ ๊ตํ์ด ์ผ์ด๋์ง๋ง, ์ ํ ์ ๋ ฌ์ ๋น๊ต๋ง ๊ฑฐํ ์ ๋ ฌ๊ณผ ๋์ผํ๊ฒ ํ ๋ฟ ๊ตํ์ ์ํ ๋น ํ ๋ฒ์ด๋ค. ์ด๋ฌํ ์ด์ ๋ก ์ ํ ์ ๋ ฌ์ด ๊ฑฐํ ์ ๋ ฌ ๋ณด๋ค ํญ์ ์ฐ์ํ๋ค.
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์ ํ ์ ๋ ฌ vs ์ฝ์ ์ ๋ ฌ ๋น๊ตโฑ (0) | 2020.10.13 |
---|---|
๋ฉ๋ชจ์ด์ ์ด์ ์ด๋?๐ (0) | 2020.10.07 |
์๊ฐ ๋ณต์ก๋ ๊ฐ์์ ์ผ๋ก ํ์ธํด๋ณด๊ธฐ๐ (0) | 2020.10.01 |
์นตํ ์ผ ์ ฐ์ด์ปค ์ ๋ ฌ๐งบ (0) | 2020.09.30 |
๊ฑฐํ ์ ๋ ฌ๐งบ (0) | 2020.09.30 |
๋ธ๋ก๊ทธ์ ์ ๋ณด
Doputer
#๊น๋ํ
๋๊ธ
์์ฑ ํ๋