Doputer

์„ ํƒ ์ •๋ ฌ๐Ÿงบ

์†Œ๊ฐœ

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;
	}
}

 

์ •๋ฆฌ

์„ ํƒ ์ •๋ ฌ๊ณผ ๊ฑฐํ’ˆ ์ •๋ ฌ์€ ์–ธ๋œป ๋น„์Šทํ•ด๋ณด์ธ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ๊ฑฐํ’ˆ ์ •๋ ฌ์€ ์ตœ์•…์˜ ๊ฒฝ์šฐ ์ธ์ ‘ํ•œ ๋ชจ๋“  ์›์†Œ๋งˆ๋‹ค ์ž๋ฆฌ ๊ตํ™˜์ด ์ผ์–ด๋‚˜์ง€๋งŒ, ์„ ํƒ ์ •๋ ฌ์€ ๋น„๊ต๋งŒ ๊ฑฐํ’ˆ ์ •๋ ฌ๊ณผ ๋™์ผํ•˜๊ฒŒ ํ•  ๋ฟ ๊ตํ™˜์€ ์ˆœํšŒ ๋‹น ํ•œ ๋ฒˆ์ด๋‹ค. ์ด๋Ÿฌํ•œ ์ด์œ ๋กœ ์„ ํƒ ์ •๋ ฌ์ด ๊ฑฐํ’ˆ ์ •๋ ฌ ๋ณด๋‹ค ํ•ญ์ƒ ์šฐ์ˆ˜ํ•˜๋‹ค.

๋ฐ˜์‘ํ˜•

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

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

Doputer

#๊น€๋„ํ˜„

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