์ฑ [ํ์ด์ฌ์ผ๋ก ์ฝ๊ฒ ํ์ด์ด ์๋ฃ๊ตฌ์กฐ; ์ต์๊ท, ์ฒ์ธ๊ตญ ์ง์]์ ์ฐธ๊ณ ํ์ฌ ์์ฑํ์์ต๋๋ค. QuickSort; ํต ์ ๋ ฌํ๊ท ์ ์ผ๋ก ๋งค์ฐ ๋น ๋ฅธ ์ํ ์๋๋ณํฉ ์ ๋ ฌ๊ณผ ๊ฐ์ด ๋ถํ -์ ๋ณต๋ฒ ์ฌ์ฉํ์ง๋ง ๋ณํฉ ์ ๋ ฌ๊ณผ๋ ๋ค๋ฅด๊ฒ ๊ท ๋ฑ ๋ถํ ํ ํ์ ์๋ค๋ฆฌ์คํธ ์์ ํ ์์๋ฅผ ํผ๋ฒ(pivot), ์ฆ ๊ธฐ์ค์ ์ผ๋ก ์ผ๊ณ ์ด ๊ฐ์ ๊ธฐ์ค์ผ๋ก ์์ ์ซ์๋ ์ผ์ชฝ์ผ๋ก, ํฐ ์ซ์๋ ์ค๋ฅธ์ชฝ์ผ๋ก ์ฎ๊ธด๋ค(์ค๋ฆ์ฐจ์์ผ ๊ฒฝ์ฐ)๊ทธ๋ฐ ๋ค์ ์ํ ํธ์ถํ์ฌ ๋ถ๋ถ ๋ฆฌ์คํธ๋ค์ ์ ๋ ฌํ๋ค๋ถ์์ ์ ๋ ฌ, ๋ณ๋์ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ ํ์ํ์ง ์๋๋คcf. ์์ ์ฑ: ์ ๋ ฅ ๋ฐ์ดํฐ์ ๋์ผํ ํท๊ฐ์ ๊ฐ๋ ๋ ์ฝ๋๊ฐ ์ฌ๋ฌ ๊ฐ ์กด์ฌํ ๊ฒฝ์ฐ ์ ๋ ฌ ํ์๋ ์ด๋ค์ ์๋์ ์ธ ์์น๊ฐ ๋ฐ๋์ง ์๋ ๊ฒ- ์๊ฐ ๋ณต์ก๋์ต์ ์ ๊ฒฝ์ฐ: ๋ฆฌ์คํธ ๋ถํ ์ด ๊ฐ์ด๋ฐ์์ ์ด๋ฃจ์ด์ ธ k๋ฒ(log_2 n)์ ๋ถํ * ํ๊ท n๋ฒ์..
