์ด ๋๊ตฌ์ ๊ธฐ๋ฅ
ํ ์ด ์ ๋ ฌ ๋๊ตฌ๋ ๋ถ์ฌ๋ฃ์ ํ์ ํ์, ์ฌ์ฉ์๊ฐ ์ง์ ํ ํ ์ด์ ๊ธฐ์ค์ผ๋ก ๋ค์ ์ ๋ ฌํด ์ค๋๋ค. ํน์ ๊ตญ๊ฐ์ ๊ท์น์ ์ฝ๋งค์ด์ง ์๋, ์ด๋์๋ ์ธ ์ ์๋ ์์ ๋ฐ์ดํฐ ์ ํธ๋ฆฌํฐ์ ๋๋ค. ํ์ ์ ๋ ฅํ๊ฑฐ๋ ๋ถ์ฌ๋ฃ๊ณ (ํ ์ค์ ํ ํ, ์ด์ ์ผํ ๋๋ ํญ์ผ๋ก ๊ตฌ๋ถ), ๊ธฐ์ค์ด ๋ ์ด ๋ฒํธ์ ์ ๋ ฌ ์์๋ฅผ ๊ณ ๋ฅด๋ฉด, ํ์ด ์๋ก ๋ฐฐ์ด๋ ๋์ผํ ํ๋ฅผ ๋๋ ค์ค๋๋ค. ๋๋จธ์ง ์ด๋ค๋ ๊ฐ์์ ํ์ ๋ฐ๋ผ ํจ๊ป ์ด๋ํ๋ฏ๋ก ๋ฐ์ดํฐ๊ฐ ํํธ๋ฌ์ง์ง ์๊ณ ๊ทธ๋๋ก ์ ๋ ฌ๋ฉ๋๋ค.
์ฌ์ฉ ๋ฐฉ๋ฒ
ํ ์คํธ ์์์ ํ๋ฅผ ํ ์ค์ ํ ํ์ฉ ์ ๋ ฅํ์ธ์. ์ ๋ ฌ ๊ธฐ์ค ์ด ๋ฒํธ์๋ ์ ๋ ฌํ๊ณ ์ถ์ ์ด์ ๋ฒํธ๋ฅผ 1๋ถํฐ ์์ํ๋ ๊ธฐ์ค์ผ๋ก ๋ฃ์ผ๋ฉด ๋ฉ๋๋ค(์ฒซ ๋ฒ์งธ ์ด์ด 1๋ฒ). ๊ทธ๋ฆฌ๊ณ ์์ ๊ฐ โ ํฐ ๊ฐ(์ค๋ฆ์ฐจ์) ๋๋ ํฐ ๊ฐ โ ์์ ๊ฐ(๋ด๋ฆผ์ฐจ์) ์ค ํ๋๋ฅผ ์ ํํ์ธ์. ์ด ๋ฒํธ์ 0์ ์ ๋ ฅํ๋ฉด ์ ๋ ฌ์ ํ์ง ์๋ ๋์ , ๊ฐ ํ์ ์ซ์ ์ ์ ๋ชจ๋ ๋ํ ๊ฐ์ ๋ด์ ํ ํฉ๊ณ ์ด์ ๋งจ ๋์ ์ถ๊ฐํฉ๋๋ค.
$$\text{SortedTable} = \operatorname{sort}_{\;\uparrow}\Big(\text{Rows},\; \text{col} = \text{Column No.}\Big)$$ $$\text{SortedTable} = \operatorname{sort}_{\;\downarrow}\Big(\text{Rows},\; \text{col} = \text{Column No.}\Big)$$ $$\text{Total}_{\text{row }i} = \sum_{j} \text{numeric cells}_{ij}\qquad(\text{Column No.} = 0)$$๊ณ์ฐ ์๋ฆฌ
๊ฐ ํ์ ์ ๋ ฌ ํค๋ \(c - 1\) ์์น์ ์ ์ ๋๋ค(\(c\)๊ฐ 1๋ถํฐ ์์ํ๋ ๋ฒํธ์ด๊ธฐ ๋๋ฌธ์ ๋๋ค). ์ ๊ฐ์ด ์ซ์๋ก ํด์๋๋ฉด ์ซ์๋ก ๋น๊ตํ๊ณ , ๊ทธ๋ ์ง ์์ผ๋ฉด ํ ์คํธ๋ก ๋น๊ตํฉ๋๋ค. ์ซ์์ ํ ์คํธ๊ฐ ์์ธ ์ด์์๋ ์ซ์๊ฐ ํ ์คํธ๋ณด๋ค ์์ ์ต๋๋ค. ์์ ์ ๋ ฌ(stable sort)์ ์ฌ์ฉํ๋ฏ๋ก, ํค๊ฐ ๊ฐ์ ํ๋ค์ ์๋์ ์์๋ฅผ ๊ทธ๋๋ก ์ ์งํฉ๋๋ค. ๋น ์ ์ ๊ฐ์ฅ ์์ ๊ฐ์ผ๋ก ์ทจ๊ธ๋์ด ์ค๋ฆ์ฐจ์์ผ ๋ ๋งจ ์๋ก ์ฌ๋ผ์ต๋๋ค.
์์๋ก ๋ณด๊ธฐ
์ด๋ฆ, ์ ์, ๋์ด ์ธ ์ด๋ก ์ด๋ฃจ์ด์ง ๋ค์ ์ธ ํ์ด ์๋ค๊ณ ํด ๋ด
์๋ค:
Alice, 80, 30
Bob, 95, 22
Carol, 88, 41
2๋ฒ ์ด(์ ์)์ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌํ๋ฉด ํค ๊ฐ์ด \(80, 88, 95\) ์์๊ฐ ๋์ด ๊ฒฐ๊ณผ๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค:
Alice, 80, 30
Carol, 88, 41
Bob, 95, 22
๋ด๋ฆผ์ฐจ์์ผ๋ก ๋ฐ๊พธ๋ฉด ์์๊ฐ ๋ค์งํ Bob, Carol, Alice๊ฐ ๋ฉ๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
ํ ์ด์ ์ซ์์ ํ ์คํธ๊ฐ ์์ฌ ์์ผ๋ฉด ์ด๋ป๊ฒ ๋๋์? ์ซ์ ์ ์ ์ซ์๋ก ์ ๋ ฌ๋์ด ์์ชฝ์ ๋์ด๊ณ , ๊ทธ ๋ค์ ํ ์คํธ ์ ์ด ์ํ๋ฒณ ์์ผ๋ก ์ ๋ ฌ๋ฉ๋๋ค.
๋ฒ์๋ฅผ ๋ฒ์ด๋ ์ด ๋ฒํธ๋ฅผ ์ ๋ ฅํ๋ฉด ์ด๋ป๊ฒ ๋๋์? ์ด ๋ฒํธ๊ฐ ์ค์ ์ด ๊ฐ์๋ณด๋ค ํฌ๋ฉด, ํ๋ ๋ณ๊ฒฝ ์์ด ๊ทธ๋๋ก ๋ฐํ๋ฉ๋๋ค.
์ค๋ณต๋ ๊ฐ๋ ์์ ํ๊ฒ ์ฒ๋ฆฌ๋๋์? ๋ค. ์์ ์ ๋ ฌ์ ์ฌ์ฉํ๋ฏ๋ก ๊ฐ์ ํค๋ฅผ ๊ฐ์ง ํ๋ค์ ์๋ ์๋ ์์๊ฐ ๊ทธ๋๋ก ์ ์ง๋ฉ๋๋ค.