์ฝ์ ์ ๋ ฌ
์ฝ์ ์ ๋ ฌ์ ๋ ๋ฒ์งธ ์์๋ถํฐ ์์ํ์ฌ ๊ทธ ์์ ์์๋ค๊ณผ ๋น๊ตํ์ฌ ์ฝ์ ํ ์์น๋ฅผ ์ง์ ํ ํ, ์์๋ฅผ ๋ค๋ก ์ฎ๊ธฐ๊ณ ์ง์ ๋ ์๋ฆฌ์ ์๋ฃ๋ฅผ ์ฝ์ ํ์ฌ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์์ ๊ฐ์ ๋ฐฐ์ด์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ค๊ณ ํ์.
๋๋ฒ ์งธ ์์์ธ 5๋ถํฐ ์์ํ์ฌ ๊ทธ ์์ ์์๋ค๊ณผ ๋น๊ต๋ฅผ ์์ํ๋ค.
5์ 7์ ๋น๊ตํด 5๊ฐ ๋ ์์ผ๋ฏ๋ก 7์ ํ์นธ ๋ค๋ก ์ฎ๊ธฐ๊ณ ๊ทธ ์๋ฆฌ์ 5๋ฅผ ์ฝ์ ํ๋ค.
์ธ ๋ฒ์งธ ์์์ธ 1๊ณผ ๊ทธ ์์ ์์ 7์ ๋น๊ตํด 1์ด ๋ ์์ผ๋ฏ๋ก 7์ ํ ์นธ ๋ค๋ก ๋ฏผ๋ค.
๊ทธ ์์ ์์ 5์ 1์ ๋น๊ตํด 1์ด ๋ ์์ผ๋ฏ๋ก 5๋ฅผ ํ ์นธ ๋ค๋ก ๋ฐ๊ณ 1์ ๊ทธ ์๋ฆฌ์ ์ฝ์ ํ๋ค.
๋ค ๋ฒ์งธ ์์์ธ 4์ ๊ทธ ์์ ์์ 7์ ๋น๊ตํด 4๊ฐ ๋ ์์ผ๋ฏ๋ก 7์ ํ ์นธ ๋ค๋ก ๋ฏผ๋ค.
๊ทธ ์์ ์์ 5์ 4๋ฅผ๋น๊ตํด 4๊ฐ ๋ ์์ผ๋ฏ๋ก 5๋ฅผ ํ ์นธ ๋ค๋ก ๋ฏผ๋ค.
๊ทธ ์์ ์์ 1๊ณผ 4๋ฅผ ๋น๊ตํด 4๊ฐ ๋ ํฌ๋ฏ๋ก 1๋ค์ 4๋ฅผ ์ฝ์ ํ๋ค.
๋ค์ฏ ๋ฒ์งธ ์์์ธ 3๊ณผ ๊ทธ ์์ ์์ 7๋ฅผ ๋น๊ตํด 3์ด ๋ ์์ผ๋ฏ๋ก 7์ ํ ์นธ ๋ค๋ก ๋ฏผ๋ค.
๊ทธ ์์ ์์ 5์ 3์ ๋น๊ตํด 3์ด ๋ ์์ผ๋ฏ๋ก 5๋ฅผ ํ์นธ ๋ค๋ก ๋ฏผ๋ค.
๊ทธ ์์ ์์ 4์ 3๋ฅผ ๋น๊ตํด 3์ด ๋ ์์ผ๋ฏ๋ก 4๋ฅผ ํ ์นธ ๋ค๋ก ๋ฏผ๋ค.
๊ทธ ์์ ์์ 1๊ณผ 3์ ๋น๊ตํด 3์ด ๋ ํฌ๋ฏ๋ก 1๋ค์ 3์ ์ฝ์ ํ๋ค.
์ฝ์ ์ ๋ ฌ์ ํน์ง
- ๋ฐฐ์ด๋ด์์ ๊ตํํ๋ ๋ฐฉ์์ด๋ฏ๋ก ๊ณต๊ฐ๋ณต์ก๋๋ O(1)์ด๋ค.
- ๋ผ๊ปํด์ผ ์์๋ฅผ ๊ตํํ ๋ ์ฐ์ผ ์์๋ณ์ ์ ๋์ ์ถ๊ฐ๊ณต๊ฐ๋ง ํ์ํ๋ฏ๋ก IN-PLACE์ ๋ ฌ์ด๋ค.
- ํ๊ท ๊ณผ ์ต์ ์ ์๊ฐ๋ณต์ก๋๋ O(N^2)์ด๋ค.
- ์ฝ์ ์ ๋ ฌ์ ์ค๋ณต๋ ํค ๊ฐ์ ์์๊ฐ ์ ๋ ฌ ํ์๋ ์ ์ง๋๋ฏ๋ก STABLE์ ๋ ฌ์ด๋ค.
- ์ ํ์ ๋ ฌ์ด๋ ๋ฒ๋ธ์ ๋ ฌ์ ๋นํด ์๋์ ์ผ๋ก ๋น ๋ฅด๋ค.
์ ์ฒด ์ฝ๋
# include <stdio.h>
# define LEN 5
void insertionSort(int* arr){
int i, j, key;
for(i=1; i< LEN; i++){
key = arr[i]; // ํ์ฌ ์ฝ์
๋ ์ซ์์ธ i๋ฒ์งธ ์ ์๋ฅผ key ๋ณ์๋ก ๋ณต์ฌ
for(j=i-1; j>=0 && arr[j]>key; j--){ // key๊ฐ ๋ ํฐ ๊ฐ์ผ ๋๊น์ง
arr[j+1] = arr[j]; // ํ ์นธ ๋ค๋ก ์ด๋
}
arr[j+1] = key; // ์๋ง์ ์์น์ key ์ฝ์
}
}
int main(){
int arr[LEN] = {7,5,1,4,3};
int i;
printf("์ ๋ ฌ ์ : ");
for(i=0; i<5; i++){
printf("%d ", arr[i]);
}
printf("\n");
insertionSort(arr);
printf("์ ๋ ฌ ํ : ");
for(i=0; i<5; i++){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
์ถ์ฒ: https://code-lab1.tistory.com/22?category=1213003 [code_lab]
์คํ๊ฒฐ๊ณผ