1. ์ ์ ๐งต
์ฝ์
์ ๋ ฌ์ ์์์๋ถํฐ ์ฐจ๋ก๋๋ก ์ด๋ฏธ ์ ๋ ฌ๋ ๋ฐฐ์ด ๋ถ๋ถ๊ณผ ๋น๊ตํ์ฌ, ์์ ์ ์์น๋ฅผ ์ฐพ์ ์ฝ์
ํจ์ผ๋ก์จ ์ ๋ ฌ์ ์์ฑํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์นด๋ ์์๋ฅผ ์ดํด๋ณด๋ฉด ์ฝ๊ฒ ์ดํดํ ์ ์์ ๊ฒ์ด๋ค. '4, 2, 3, 1, 5'๋ผ๋ ์ซ์ ์ ํ 5์ฅ์ ์นด๋๊ฐ ์์๋๋ก ์๋ค๊ณ ํ์. ์์์๋ถํฐ ์์๋๋ก ์นด๋๋ฅผ ๋ฝ์ผ๋ฉด์ ์์ ์ฅ๋ค๊ณ ์๊ฐํ์. ๋ฝํ ์นด๋๋ ์ด๋ฏธ ์์ ์ฅ์ด์ง ์นด๋๋ค ์ฌ์ด์ ์์น๋ฅผ ์ฐพ์๋ค์ด๊ฐ๋ค.
์ด๋ฏธ ์์ ์ฅ์ด์ ธ ์๋ ์นด๋๋ค | ๋ฝ์ ์นด๋ | ์์ ์ ์์น๋ฅผ ์ฐพ์๋ค์ด๊ฐ ๋ชจ์ต |
4 | 4 | |
4 | 2 | 2 4 |
2 4 | 3 | 2 3 4 |
2 3 4 | 1 | 1 2 3 4 |
1 2 3 4 | 5 | 1 2 3 4 5 |
1๋ฒ ์ซ์๊ฐ ์ ํ ์นด๋๊ฐ ์์ ์ ์์น๋ฅผ ์ฐพ์๊ฐ๋ ๊ฒ์ ๋ค์ ํ๋ฒ ์ดํด๋ณด์. 1๋ฒ ์นด๋๋ 4๋ฒ๊ณผ ๋น๊ตํ๊ณ , 3๋ฒ๊ณผ ๋น๊ตํ๊ณ , 2๋ฒ๊ณผ ๋น๊ตํ์ฌ ์์ ์ ์์น์ ๋๋ฌํ๊ฒ ๋๋ค. ๊ทธ๋ฌ๋ฉด 1๋ฒ๊ณผ ๋น๊ตํ์ฌ ๋ ํฐ ๊ฐ์ ๊ฐ์ง ์นด๋๋ค์ ํ ์นธ์ฉ ๋ค๋ก ๋ฐ๋ฆฌ๊ฒ ๋๋ค. ์ด์ ๊ฐ์ ๋ฐฉ์์ผ๋ก ๋๋จธ์ง ์นด๋๋ค๋ ์์ ์ ์์น๋ฅผ ์ฐพ์๋ค์ด๊ฐ๊ฒ ๋๋ค.
2. ๋์ ๋ฐฉ์ ๐งถ
์์ ์นด๋ ์์๋ฅผ ์ ์ดํดํ๋ค๋ฉด ๋์ ๋ฐฉ์์ ๋งค์ฐ ๊ฐ๋จํ๋ค.
- ์๋ฆฌ๋ฅผ ์ฐพ์๊ฐ์ผ ํ๋ i๋ฒ์งธ ์์๋ฅผ ์ง์ ํ๋ค.
- (i - 1) ๋ฒ์งธ ์์๋ถํฐ i๋ฒ์งธ ์์์ ๋น๊ต๋ฅผ ์์ํ๋ค.
- i๋ฒ์งธ ์์๋ณด๋ค ํฐ ๊ฒฝ์ฐ์๋ ์์ ์ ์๋ฆฌ์์ ํ ์๋ฆฌ์ฉ ๋ค๋ก ๋ฐ๋ฆฌ๊ฒ ๋๋ค.
- ๋น๊ต๋๋ ์์๊ฐ i๋ฒ์งธ ์์๋ณด๋ค ์์ ๊ฒฝ์ฐ์ ๋น๊ต๋ฅผ ๋ฉ์ถ๋ค.
- ๋ฐ๋ฆฌ์ง ์์ ์์๋ค๊ณผ ๋ฐ๋ฆฐ ์์๋ค์ ์ฌ์ด์ i๋ฒ์งธ ์์๊ฐ ์์นํ๊ฒ ๋๋ค.
3. ๊ตฌํ(JAVA) ๐งฃ
void insertionSort(int[] arr) {
for(int idx = 1; idx < arr.length; idx++) {
int temp = arr[idx];
int compareIdx = idx - 1;
while((compareIdx >= 0) && (temp < arr[compareIdx])) {
arr[compareIdx + 1] = arr[compareIdx];
compareIdx--;
}
// ๋ฐ๋ฆฌ์ง ์์ ์์๋ค๊ณผ ๋ฐ๋ฆฐ ์์๋ค ์ฌ์ด์ ํด๋น ์์๊ฐ ์์นํ๋ค.
arr[compareIdx + 1] = temp;
}
}
4. ์๊ฐ๋ณต์ก๋ & ๊ณต๊ฐ๋ณต์ก๋ ๐
1. ์๊ฐ๋ณต์ก๋
์ญ์ผ๋ก ์ ๋ ฌ์ด ๋์ด ์๋ ๊ฒฝ์ฐ(์ต์ ์ ๊ฒฝ์ฐ) i๋ฒ์งธ ์์๋ง๋ค (i - 1) ๋ฒ ๋น๊ต๋ฅผ ํด์ผ ํ๋ค. ์์๊ฐ N๊ฐ๊ฐ ์๋ ๊ฒฝ์ฐ ์๋์ ๊ฐ์ ์ฐ์ฐ์ด ์ํ๋๋ค.
1 + 2 + ... + (N - 2) + (N - 1) = N * (N - 1) / 2
๋ฐ๋ผ์, ์ต์ ์ ๊ฒฝ์ฐ ์๊ฐ๋ณต์ก๋๋ O(N ^ 2)์ด๋ค.
๋ง์ฝ ์ ๋ ฌ์ด ๋์ด ์๋ ๊ฒฝ์ฐ(์ต์ ์ ๊ฒฝ์ฐ)์๋ i๋ฒ์งธ ์์๋ง๋ค 1๋ฒ๋ง ์ฐ์ฐ์ ์ํํ๋ฉด ๋๋ฏ๋ก O(N)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
์ต์ (BEST) | ํ๊ท (AVERAGE) | ์ต์ (WORST) | |
์๊ฐ๋ณต์ก๋ | O(N) | O(N^2) | O(N^2) |
2. ๊ณต๊ฐ๋ณต์ก๋
๊ณต๊ฐ๋ณต์ก๋์ ๊ฒฝ์ฐ ์ถ๊ฐ์ ์ธ ๋ฐฐ์ด์ ๋ง๋ค์ง ์๊ณ ํด๋น ๋ฐฐ์ด์์ ๊ตํ์ด ์ด๋ฃจ์ด์ง๋ฏ๋ก O(N)์ด๋ค.
5. ์ฅ์ & ๋จ์ ๐ก
1. ์ฅ์
- ์ฝ๋๊ฐ ๋งค์ฐ ๋จ์ํ๋ค.
- ๋ค๋ฅธ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ํ์๋ก ํ์ง ์๋๋ค.
- ์ ๋ ฌ์ด ๋์ด ์๋ ๊ฒฝ์ฐ ๋งค์ฐ ํจ๊ณผ์ ์ด๋ค. - O(N)์ ์๊ฐ๋ณต์ก๋
- ์์์ ์ดํด๋ณธ ๋ฒ๋ธ ์ ๋ ฌ๊ณผ ์ ํ ์ ๋ ฌ์ ๋นํด ์๋์ ์ผ๋ก ๋น ๋ฅด๋ค.
2. ๋จ์
- ์ต์ ์ ๊ฒฝ์ฐ ์๊ฐ๋ณต์ก๋๊ฐ O(N^2)์ด๋ฏ๋ก ์๋นํ ๋นํจ์จ์ ์ด๋ค.
- ๋ฐฐ์ด์ ๊ธธ์ด๊ฐ ๊ธด ๊ฒฝ์ฐ ๋นํจ์จ์ ์ด๋ค.
ํด๋น ๊ธ์ Gyoogle๋์ ์ฝ์ ์ ๋ ฌ(Insertion Sort)์ ์ฐธ๊ณ ํ์์ต๋๋ค.
'๐ ์๋ฃ๊ตฌ์กฐ > ์ ๋ ฌ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ ์ ๋ ฌ (Heap Sort) (0) | 2023.03.12 |
---|---|
์์ ์ ๋ ฌ(Topology Sort) (2) | 2023.03.07 |
๋ณํฉ ์ ๋ ฌ(Merge Sort) (0) | 2023.03.07 |
์ ํ ์ ๋ ฌ(Selection Sort) (2) | 2023.03.04 |
๋ฒ๋ธ ์ ๋ ฌ(Bubble Sort) (0) | 2023.03.04 |