๐ฉ ์๋ฃ ๋ฐฐ์ด์ ๋ชจ๋ ์์๋ฅผ ์์์๋ถํฐ ์ฐจ๋ก๋๋ก ์ด๋ฏธ ์ ๋ ฌ๋ ๋ฐฐ์ด ๋ถ๋ถ๊ณผ ๋น๊ตํ์ฌ, ์์ ์ ์์น๋ฅผ ์ฐพ์ ์ฝ์ ํจ์ผ๋ก์จ ์ ๋ ฌ์ ์์ฑํ๋ ์๊ณ ๋ฆฌ์ฆ
๋งค ์์๋ง๋ค ํด๋น ์์๋ฅผ ์ฝ์ ํ ์ ์๋ ์์น๋ฅผ ์ฐพ์ ํด๋น ์์น์ ์ฝ์
์ผ์ชฝ์๋ ์ ๋ ฌ์ด ๋๋ ์๊ฐ ์ค๊ฒ๋๊ณ , ์ค๋ฅธ์ชฝ์๋ ์์ง ํ์ธํ์ง ์์ ์ซ์๊ฐ ๋จ๊ฒ ๋๋๋ฐ, ์ค๋ฅธ์ชฝ ๋ฏธํ์ ์์ญ์์ ์ซ์๋ฅผ ํ๋ ๊บผ๋ด์ด ์ ๋ ฌ์ด ๋๋ ์์ญ์ ์ ์ ํ ์์น์ ์ฝ์ ํด ๋๊ฐ๋ ๋ฐฉ์
์ด๋ฏธ ์ ๋ ฌ์ด ๋์ด์๋ค๋ฉด ํ์์์ด ์ข ๋ฃํ๋ค.
InsertionSort(A[ ], n) {
for (i=1; i< n; i++) { // A[0] ์ ๋ ฌ ๋ถ๋ถ; 1, โฏ, (n-1)๊น์ง (n-1)๋ฒ ๋ฐ๋ณต
val= A[i]; // ๋ฏธ์ ๋ ฌ ๋ถ๋ถ A[i..n-1]์ ์ฒซ ๋ฒ์งธ ๋ฐ์ดํฐ ์ ํ
for (j=i; j > 0 && A[j-1] > val; j--) // ์ฝ์
ํ ์์น ์ฐพ๊ธฐ
A[j] = A[j-1]; // ์ ๋ ฌ ๋ถ๋ถ์ A[j-1]์ด ํฌ๋ฉด ๋ค๋ก ํ ์นธ ์ด๋
A[j] = val; // ์ฐพ์์ง ์์น์ ์ ํ๋ ๋ฐ์ดํฐ ์ฝ์
}
return (A);
}
๐ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ ๊ฒฝ์ฐ ๋ด๋ถ ๋ฐ๋ณต๋ฌธ์ ์กฐ๊ฑด์ ์๋์ ๊ฐ์ด ๋ณ๊ฒฝํ๋ค.
for(j=i; j > 0 && A[j-1] < val; j--)
๐ฉ ์๊ฐ ๋ณต์ก๋
๋ฐ๊นฅ ๋ฃจํ i | 1 | 2 | 3 | ... | n-1 |
๋ฃจํ j์ ๋น๊ต ํ์ | 1 | 2 | 3 | ... | n-1 |
์ด ๋น๊ต ํ์ = 1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2
๐ O(n^2)
cf. ์ด๋ฏธ ์ ๋ ฌ๋ ์ํ์ธ ๊ฒฝ์ฐ O(n)
'๐ฉโ๐ป ํ๋ก๊ทธ๋๋ฐ > ๐ ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํต ์ ๋ ฌ(Quick Sort) (0) | 2024.04.12 |
---|---|
์ ธ ์ ๋ ฌ(Shell Sort) (0) | 2024.04.12 |
๋ฒ๋ธ ์ ๋ ฌ(Bubble Sort) (0) | 2024.04.12 |
์ ํ ์ ๋ ฌ(Selection Sort) (0) | 2024.04.12 |
์ฌ๊ท(์ํ) ์๊ณ ๋ฆฌ์ฆ (0) | 2024.03.27 |