์ฃผ์ด์ง ํญ๋ชฉ๋ค์ด ์ ๋ ฌ๋์ด ์์ง ์์ผ๋ฉด ์ด์ง ๊ฒ์์ ํ ์ ์์
์ ๋ ฌ(sorting)์ ํญ๋ชฉ์ ์์๋๋ก ๋ฐฐ์ดํด์ ๊ฒ์์ด ๋นจ๋ฆฌ ์คํ๋ ์ ์๋๋ก ํด์ค
์ ํ ์ ๋ ฌ(Selection Sort)์ ์์ง ์ ๋ ฌ๋์ง ์์ ํญ๋ชฉ ์ค์์ ๋ค์ ํญ๋ชฉ์ ๊ณ์ ์ ํํจ
์๊ณ ๋ฆฌ์ฆ์ ์ฐ๊ตฌํ๋ ์ปดํจํฐ๊ณผํ์๋ค์ ๋น๊ด๋ก ์๋ผ์ ์ง๋ฆ๊ธธ ์์ด ๋ชจ๋ ์์ ์ ์ํํด์ผ ํ๋ ์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ๊ฐ์ ํจ
[ํญ๋ชฉ์ ํ์ด๋ณด๋ ํ์] = [N + N-1 + N-2 + ... + 1] = [N * (N+1) / 2]
์ผ์ ์์ , ๊ณ์๋ฅผ ์ ์ธํด์ ์ต๊ณ ์ฐจํญ์ธ 2์ฐจ(quadratic)์ธ ์ฆ๊ฐ์จ์ ๋ณด์
ํต ์ ๋ ฌ(Quick Sort)์ ๋ถํ ์ ๋ณต์ ํ๋ฅญํ ์ฌ๋ก
ํญ์ ๋ฐ์ดํฐ๋ฅผ ์ ๋ ฌํ์ง๋ง ๊ทธ๋ฃน์ ๋๋ ๋๋ง๋ค ๊ฑฐ์ ๊ฐ์ ํฌ๊ธฐ์ ๋ฉ์ด๋ฆฌ๋ก ๋๋ ์ผ๋ง ํจ์จ์ []
์ ์ฐ์ฐ์ด ํ์
์ ํ๋ณด๋ค๋ ํจ์จ์ด ๋ฎ์ง๋ง ์ฌํ์ง๋ ์๊ณ , N์ด ์กฐ๊ธ์ด๋ผ๋ ํฌ๋ฉด 2์ฐจ()๋ณด๋ค ํจ์ฌ ํจ์จ์
์ ํ ์ ๋ ฌ๊ณผ ํต ์ ๋ ฌ ์๊ฐ ๋น๊ต
๊ฐ์(N) | ์ ํ ์ ๋ ฌ ์๊ฐ(์ด) | ํต ์ ๋ ฌ ์๊ฐ(์ด) |
---|---|---|
1000 | 0.047 | - |
1,0000 | 4.15 | 0.025 |
10,0000 | 771 | 0.23 |
100,0000 | - | 3.07 |
1000,0000 | - | 39.9 |
์ ํ์ ๋ ฌ์์ 10,0000๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ด 1,0000๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํ๋ ์๊ฐ์ ๋นํด 100๋ฐฐ ํด ๊ฒ์ผ๋ก ์์ํ์ง๋ง ์ค์ ๋ก๋ ๊ฑฐ์ 200๋ฐฐ์
์บ์ฑ์ ์ํฅ ์ผ์๋
๋ฐ์ดํฐ๊ฐ ์บ์์ ๋ชจ๋ ๋ค์ด๊ฐ์ง ๋ชปํ๋ฉด์ ์ ๋ ฌ์ด ๋๋ ค์ง ๊ฒ
๊ณ์ฐ ๊ณผ์ ์ ์ด๋ก ์ ์ผ๋ก ์ถ์ํํ ๊ฒ๊ณผ ํ๋ก๊ทธ๋จ์ ์ค์ ๋ก ๊ณ์ฐ์ ์ํํ๋ ์ํฉ ๊ฐ์ ์ฐจ์ด๋ฅผ ๋ณด์ฌ์ค