-
[Algorithm] ๋ฒ๋ธ ์ ๋ ฌ(Bubble Sort)๐ปProgramming/Algorithm 2024. 3. 27. 17:37
๋ฒ๋ธ ์ ๋ ฌ์ด๋?
์ ํ ์ ๋ ฌ๊ณผ ์ ์ฌํ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์๋ก ์ธ์ ํ ๋ ์์์ ๋์๋ฅผ ๋น๊ตํ๊ณ , ์กฐ๊ฑด์ ๋ง์ง ์๋ค๋ฉด ์๋ฆฌ๋ฅผ ๊ตํํ๋ฉฐ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์ด๋ฆ์ ์ ๋๋ก๋ ์ ๋ ฌ ๊ณผ์ ์์ ์์์ ์ด๋์ด ๊ฑฐํ์ด ์๋ฉด์ผ๋ก ์ฌ๋ผ์ค๋ ๋ฏํ ๋ชจ์ต์ ๋ณด์ด๊ธฐ ๋๋ฌธ์ ์ง์ด์ก๋ค๊ณ ํ๋ค.
๊ณผ์
1. ์ฒซ ๋ฒ์งธ ๋ฐ๋ณต๋ฌธ์์ ์ฒซ๋ฒ์งธ ์์์ ๋ ๋ฒ์งธ ์์๋ฅผ ๋น๊ตํ๋ค. ๋ง์ฝ ์ฒซ ๋ฒ์งธ ์์๊ฐ ๋ ํฌ๋ฉด ๊ตํ. ๋ ๋ฒ์งธ ์์์ ์ธ ๋ฒ์งธ ์์๋ฅผ ๋น๊ตํ ๋๋ฒ์งธ๊ฐ ํฌ๋ฉด ๊ตํ. ์ด๋ ๊ฒ ํด์ n-1๋ฒ์ฌ ์์๊น์ง ๋น๊ตํ๋ฉด ๊ฐ์ฅ ํฐ ์๋ n์ ๊ฐ์๊ฒ๋๋ค.
2. ๊ทธ๋ผ n์ ๊ฐ์ฅ ํฐ ์์ด๋๊น, ๋ค์ n-2์์๊น์ง ๋น๊ต๋ฅผ ๋ฐ๋ณต. ๊ทธ๋ผ ๋ ๋ฒ์งธ๋ก ํฐ ์๊ฐ n-1๋ฒ์ ๊ฐ๊ฒ ๋๋ค.
์ด๋ ๊ฒ ๋ฐ๋ณตํ๋ฉด ๋ชจ๋ ์๊ฐ ์ ๋ ฌ๋๋ค.
๊ตฌํ ์ฝ๋(Java)
import java.util.Scanner; public class Main { private int[] solution(int n, int[] list) { for(int i = 0; i < n - 1; i++) { for(int j = 0; j < n - i - 1; j++) { if(list[j] > list[j+1]) { int tmp = list[j]; list[j] = list[j+1]; list[j + 1] = tmp; } } } return list; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); Main T = new Main(); int n = scanner.nextInt(); int[] list = new int[n]; for(int i = 0; i < n; i++) list[i] = scanner.nextInt(); for(int i : T.solution(n, list)) System.out.print(i + " "); } }
์๊ฐ๋ณต์ก๋
(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2
-> O(n^2)
๋ฒ๋ธ ์ ๋ ฌ์ ์ ๋ ฌ์ด ๋์ด์๋์ง ์๋๋์ง 2๊ฐ์ ์์๋ฅผ ๋ฌด์กฐ๊ฑด ๋น๊ตํด์ผํ๋ฏ๋ก, ์ต์ /ํ๊ท /์ต์ ์ ๊ฒฝ์ฐ ๋ชจ๋ ์๊ฐ๋ณต์ก๋๊ฐ O(n^2)๋ก ๋์ผํ๋ค๋ ๋จ์ ์ด์๋ค.
References
https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html
'๐ปProgramming > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Algorithm] ์ด์งํ์(Binary Search) (0) 2024.04.09 [Algorithm] ์ฝ์ ์ ๋ ฌ(Insertion Sort) (0) 2024.03.28 [Algorithm] ์ ํ์ ๋ ฌ(Selection Sort) (0) 2024.03.26 [Algorithm] ์ฐ์ ๋ถ๋ถ์์ด (0) 2024.03.05 [Algorithm] Sliding Window ์๊ณ ๋ฆฌ์ฆ (0) 2024.03.03