๐ก์์์ ๋ํ ๊ฐ์
- ์ ๋ ฅ ํฌ๊ธฐ n
- ์ ๋ ฅ ๋ฐฐ์ด A[0…. n-1]
- ์ ๋ ฅ ๋ฐ์ดํฐ : ์์ ์ ์
- ์ ๋ ฌ ๋ฐฉ์ : ์ค๋ฆ์ฐจ์ (1, 2, 3, 4,…)
2-3) ์ฝ์ ์ ๋ ฌ (Insertion sort)
- ์ฃผ์ด์ง ๋ฐ์ดํฐ๋ฅผ ํ๋์ฉ ๋ฝ์ ํ,
์ด๋ฏธ ๋์ด๋ ๋ฐ์ดํฐ๋ค์ด ํญ์ ์ ๋ ฌ๋ ์ํ๋ฅผ ๊ฐ๋๋ก ๋ฐ๋ฅธ ์์น๋ฅผ ์ฐพ์ ๋ฝ์ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ ํด์ ๋์ดํ๋ ๋ฐฉ์ - ์ ๋ ฌ ๋ถ๋ถ A[0…k-1] ๊ณผ ๋ฏธ์ ๋ ฌ ๋ถ๋ถ A[k…n-1] ์ผ๋ก ๊ตฌ๋ถํด์ ์ฒ๋ฆฌ
- ์ ๋ ฌ ๊ณผ์
- ๋ฏธ์ ๋ ฌ ๋ถ๋ถ A[k…n-1]์์ 1๋ฒ์งธ ๋ฐ์ดํฐ๋ฅผ ๋ฝ์
- ์ ๋ ฌ ๋ถ๋ถ A[0…k-1]์์ ์ฌ๋ฐ๋ฅธ ์๋ฆฌ์ ์ฝ์
์ ๋ ฅ ๋ฐ์ดํฐ A [10, 30, 40, 20, 70, 50, 60]
1๏ธโฃ. ์ ๋ ฅ๋ฐ์ดํฐ๋ฅผ ์ ๋ ฌ๋ถ๋ถ๊ณผ ๋ฏธ์ ๋ ฌ ๋ถ๋ถ์ผ๋ก ๋๋๋ค.
2๏ธโฃ. ๋ฏธ์ ๋ ฌ ๋ถ๋ถ์ ์ฒซ๋ฒ์งธ ๋ฐ์ดํฐ 20์ ๋ฝ๋๋ค.
3๏ธโฃ. ๋ฝํ ๋ฐ์ดํฐ 20์ ์ ๋ ฌ๋ถ๋ถ์ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ (=์ ๋ ฌ ๋ถ๋ถ์ ๊ฐ์ฅ ํฐ ๊ฐ, 20๊ณผ ๊ฐ์ฅ ์ธ์ ํ ์ชฝ)๋ถํฐ ๋น๊ตํ์ฌ ์ง์ ํ๋ค.
4๏ธโฃ. ๋น๊ตํ ๋ฐ์ดํฐ๊ฐ 20๋ณด๋ค ์์ผ๋ฉด ๊ตํํ์ง ์๊ณ ๋จ๊ณ๋ฅผ ์ข ๋ฃํ๋ค.
5๏ธโฃ. 2๏ธโฃ ~ 4๏ธโฃ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
3. ํน์ง
- ์ฑ๋ฅ : O(n²)
- ์ ์๋ฆฌ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ : ์ ๋ ฅ ๋ฐฐ์ด A ์ด์ธ ์์๊ฐ(i, j, val) ์ ์ ์ฅ ๊ณต๊ฐ๋ง ํ์
- ์์ ์ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ
- ์
๋ ฅ ๋ฐ์ดํฐ์ ์๋ ์์์ ๋ฏผ๊ฐ
- ์ญ์์ ๊ฒฝ์ฐ์๋ O( n²)
- ์ ์์๋๋ก ๊ฑฐ์ ์ ๋ ฌ๋์์ผ๋ฉด O(n)
[JS code]
function insertionSort(A) {
const n = A.length;
for (let i = 1; i < n; i++) { // 1, …, (n-1)๊น์ง (n-1)๋ฒ ๋ฐ๋ณต. A[0] ์ ๋ ฌ ๋ถ๋ถ์ด๋ฏ๋ก ๊ฑด๋๋
let val = A[i]; // ๋ฏธ์ ๋ ฌ ๋ถ๋ถ ์ฒซ ๋ฒ์งธ ๋ฐ์ดํฐ๋ฅผ ์ ํ. val์ ๋์
for (let j = i; j > 0 && A[j - 1] > val; j--) { // ์ ๋ ฌ๋ ๋ถ๋ถ์์ ๋น๊ต๋ฅผ ์์ํฉ
A[j] = A[j - 1]; // ์ ๋ ฌ ๋ถ๋ถ์ A[j-1]์ด val๋ณด๋ค ํฌ๋ฉด ๋ค๋ก ํ ์นธ ์ด๋
}
A[j] = val; // ์ฐพ์์ง ์์น์ ์ ํ๋ ๋ฐ์ดํฐ๋ฅผ ์ฝ์
}
return A;
}
๋ฐ์ํ
๋๊ธ