๋ฒ๋ธ ์ ๋ ฌ (Bubble Sort)
๋ฒ๋ธ ์ ๋ ฌ์, ์ด์ํ ๋ ์ซ์๋ฅผ ๊ณ์ํด์ ๋น๊ตํ๋ฉฐ ์ ํด์ง ๊ท์น์ ๋ฐ๋ผ ์๋ฆฌ๋ฅผ ์ค์์นญํ๋ ์ ๋ ฌ์ด๋ค. ์๋ฅผ ๋ค์ด, ์ค๋ฆ์ฐจ์์ด๋ผ๋ฉด ์ด์ํ ๋ ์ซ์ ์ค ๋ ํฐ ์ซ์๊ฐ ๋ท ์๋ฆฌ๋ก ์ด๋ํ๋๋ก ์๋ก ๋ฐ๊ฟ์ค๋ค๋ ๊ฒ์ด๋ค. ๋ฒ๋ธ ์ ๋ ฌ์ด๋ผ๋ ์ด๋ฆ์ด ๋ถ์ ์ด์ ๋ ๊ฐ์ฅ ๊ฐ๋ฒผ์ด ๊ฒ์ด ์๋ก ์ฌ๋ผ๊ฐ๋ ๊ฑฐํ์ ์์ง์์ ๋น๋์ด ๋ถ์ฌ์ง ์ด๋ฆ์ด๋ผ ํ๋ค. (๊ทธ๋ ๊ฒ ๊ณต๊ฐ์ด ๊ฐ์ง ์๋๋ค)
์ ๊ทธ๋ฆผ์ ๋ฒ๋ธ ์ ๋ ฌ์ switching ํ๋ ๊ณผ์ ์ ๋ณด์ฌ์ฃผ๋ ๊ทธ๋ฆผ์ด๋ค.
์ฐ์๋ ๋ ์ด์์ ๊ฐ์ ๋น๊ตํด ๋ ๋์ ๊ฐ์ ๋ท์๋ฆฌ๋ก ์ค์์นญํ๊ฒ ๋๋ค.
ํน์ง์, ํ loop๊ฐ ๋ ๋๋ง๋ค, ์ ์ผ ๋ง์ง๋ง ์๋ฆฌ์ ์ซ์๊ฐ ๊ฒฐ์ ๋๋ค๋ ๊ฒ์ด๋ค.
๋ค์ loop๋ n-1๋ฒ์งธ ์๋ฆฌ์ ์ซ์๊ฐ, ๊ทธ ๋ค์์ n-2๋ฒ์งธ ์๋ฆฌ์ ์ซ์๊ฐ ๊ฒฐ์ ๋๋ค๋ ํน์ง์ ์๊ฒ ๋๋ค๋ฉด, ์ฝ๊ฒ ๊ตฌํํ ์ ์๋ค.
๋ชจ๋ ์๋ฆฌ์ ์ซ์๋ฅผ ๊ฒฐ์ ํด์ผ ํ๊ณ (O(n)), n๋ฒ์งธ ์๋ฆฌ์ ์ซ์๋ฅผ ๊ฒฐ์ ํ ๋ ๋ง๋ค n-1๋ฒ์ ๋น๊ต๊ฐ ์ด๋ค์ง๋ค. (O(n))
๋ฐ๋ผ์ ๋ฒ๋ธ ์ ๋ ฌ์ ์๊ฐ ๋ณต์ก๋๋ O(n^2)์ ํด๋นํ๋ค.
๋ฒ๋ธ ์ ๋ ฌ ํ์ด์ฌ ์ฝ๋
๋ฒ๋ธ ์ ๋ ฌ ์๋ฐ ์ฝ๋
๋ฒ๋ธ ์ ๋ ฌ ์ฅ๋จ์
- ๋ฒ๋ธ ์ ๋ ฌ์ ์ฅ์
๊ตฌํ์ด ๊ฐ๋จํ๋ฏ๋ก, ๊ฐ๋ฐ์ ๋๋ ์๊ฐ์ ์ค์ผ ์ ์๋ค.
์ฝ๋๋ง ๋ณด๊ณ ๋ ๋๊ตฌ๋ ์ดํดํ๊ธฐ ์ฌ์ด ์ง๊ด์ ์ธ ์ฝ๋์ด๋ค.
๊ณต๊ฐ ๋ณต์ก๋๊ฐ O(N)์ผ๋ก, ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์๋ ์ ์๋ค.
- ๋ฒ๋ธ ์ ๋ ฌ์ ๋จ์
๋ฐ์ดํฐ๋ฅผ ํ๋์ฉ ๋น๊ตํ๊ธฐ ๋๋ฌธ์ ๋น๊ตํ์๊ฐ ๋ง์์ง๋ฏ๋ก, ์๊ฐ์ด ์ค๋ ๊ฑธ๋ฆฐ๋ค.
'๐งช ์ปดํจํฐ๊ณผํ : CS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๋ฃ๊ตฌ์กฐ] Array์ LinkedList์ ์ฐจ์ด (์ธํฐ๋ทฐ ๋๋น) (0) | 2022.10.23 |
---|---|
[๊ฐ๋ฐ๊ณตํต] Call by value์ Call by reference (Java, Python, C/C++) (0) | 2022.10.11 |
[Algorithm] ํ ์ ๋ ฌ (Heap Sort) (0) | 2022.09.03 |
[Alogrithm] ์ฝ์ ์ ๋ ฌ (Injection Sort) (0) | 2022.09.03 |
[Algorithm] ์ ํ ์ ๋ ฌ (Selection Sort) (0) | 2022.09.03 |