์๋ ํ์ธ์ ์ฃผ์ธ์ฅ H์ ๋๋ค. ์ค๋์ ํต์ ๋ ฌ์ ๋ํด ์์๋ณด๊ฒ ์ต๋๋ค. ์ง๊ธ๊น์ง ๋ฐฐ์ด ์ ๋ ฌ์ ์๊ฐ๋ณต์ก๋ O(N^2)๋ฅผ ๊ฐ์ง ์๊ณ ๋ฆฌ์ฆ ์ด์์ต๋๋ค. ์ฒ๋ฆฌํ ๋ฐ์ดํฐ๊ฐ ๋ง๋ค๋ฉด ์ฌ์ฉํ๊ธฐ์ ๋ถ๋ด์ด ๋๊ฒ ์ง์. ๊ทธ๋ ๊ธฐ์ ๋ํ์ ์ธ ๋น ๋ฅธ ์๊ณ ๋ฆฌ์ฆ์ด ๋ฐ๋ก ํต์ ๋ ฌ์ ๋๋ค. ํต์ ๋ ฌ์ ๋ํ์ ์ธ ๋ถํ ์ ๋ณต ์๊ณ ๋ฆฌ์ฆ์ผ๋ก์ ํ๊ท ์๋๊ฐ O(N*log N)์ ๋๋ค. 1~10๊น์ง์ ๋ฌด์ง์ํ ์ซ์๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ฆฌํ๋ค๊ณ ํ ๋, ํต ์ ๋ ฌ์ ํ๋์ ํฐ ๋ฌธ์ ๋ฅผ ๋ ๊ฐ์ ์์ ๋ฌธ์ ๋ก ๋ถํ ํ๋ ์์ผ๋ก ๋น ๋ฅด๊ฒ ์ ๋ ฌํฉ๋๋ค. ํน์ ํ ๊ฐ(ํผ๋ฒpivot)์ ๊ธฐ์ค์ผ๋ก ํฐ ์ซ์์ ์์ ์ซ์๋ฅผ ์๋ก ๊ตํํ ๋ค์ ๋ฐฐ์ด์ ๋ฐ์ผ๋ก ๋๋๋๋ค. ์๋ฅผ๋ค์ด (1) 10 5 8 7 6 4 3 2 9 ๋ผ๋ ์ซ์๊ฐ ์๋ค๊ณ ๊ฐ์ ํฉ๋๋ค. ์ด ๊ฒฝ์ฐ 1๋ณด๋ค ํฐ ์ซ์๋ฅผ ์ผ์ชฝ์์, 1๋ณด๋ค ํฐ ์ซ์๋ฅผ..