์‚ฝ์ž…์ •๋ ฌ(InsertionSort)์ด๋ž€?

2021. 12. 21. 17:46ยท๐Ÿ“š ์ž๋ฃŒ๊ตฌ์กฐ ๋ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜/์ •๋ ฌ ๋ฐ ํƒ์ƒ‰
728x90

์‚ฝ์ž…์ •๋ ฌ

์‚ฝ์ž…์ •๋ ฌ์€ ๋‘ ๋ฒˆ์งธ ์›์†Œ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ๊ทธ ์•ž์˜ ์›์†Œ๋“ค๊ณผ ๋น„๊ตํ•˜์—ฌ ์‚ฝ์ž…ํ•  ์œ„์น˜๋ฅผ ์ง€์ •ํ•œ ํ›„, ์›์†Œ๋ฅผ ๋’ค๋กœ ์˜ฎ๊ธฐ๊ณ  ์ง€์ •๋œ ์ž๋ฆฌ์— ์ž๋ฃŒ๋ฅผ ์‚ฝ์ž…ํ•˜์—ฌ ์ •๋ ฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

์œ„์™€ ๊ฐ™์€ ๋ฐฐ์—ด์„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค๊ณ  ํ•˜์ž.

๋‘๋ฒˆ ์งธ ์›์†Œ์ธ 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]

์‹คํ–‰๊ฒฐ๊ณผ

 

728x90
'๐Ÿ“š ์ž๋ฃŒ๊ตฌ์กฐ ๋ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜/์ •๋ ฌ ๋ฐ ํƒ์ƒ‰' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • ์ •๋ ฌ(Sort Algorithm)์ด๋ž€?
  • ํ€ต์ •๋ ฌ(QuickSort)์ด๋ž€?
  • ์„ ํƒ์ •๋ ฌ(Selection Sort)์ด๋ž€?
  • ๋ฒ„๋ธ”์ •๋ ฌ(BubbleSort)์ด๋ž€?
juno1105
juno1105
๊ณต๋ถ€ํ•˜๋Š” ๊ฒธ ํฌํด ๋ธ”๋กœ๊ทธ
  • juno1105
    @juno1105
    juno1105
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (89)
      • ๐Ÿ’ฌ ์ž์œ  (3)
      • ๐Ÿ“– ์–ดํ•™ ๊ณต๋ถ€ (0)
      • ๐Ÿ“” ๊ฐœ๋ฐœ ํ”„๋กœ์ ํŠธ (4)
      • ๐Ÿ›  ํ”„๋กœ๊ทธ๋žจ ์˜ค๋ฅ˜ ํ•ด๊ฒฐ๋ฒ• (1)
      • ๐Ÿ“š ์ž๋ฃŒ๊ตฌ์กฐ ๋ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (53)
        • ์Šคํƒ (4)
        • ํ (4)
        • ์ •๋ ฌ ๋ฐ ํƒ์ƒ‰ (17)
        • ๋ฆฌ์ŠคํŠธ (5)
        • ํ•ด์‹œ (1)
        • ํŠธ๋ฆฌ (8)
        • ํž™ (2)
        • ๊ทธ๋ž˜ํ”„ (12)
      • ๐Ÿ’ป ์ปดํ“จํ„ฐ ๊ตฌ์กฐ (0)
      • ๐Ÿšฅ ๋…ผ๋ฆฌํšŒ๋กœ (8)
      • ๐Ÿ”ฐ ๋ฐฑ์ค€ (20)
        • ํ, ์Šคํƒ, ๋ฑ (0)
        • DFS ์™€ BFS (3)
        • ๊ทธ๋ฆฌ๋”” (0)
        • ๋™์ ๊ณ„ํš๋ฒ• 1 (16)
        • ๋™์ ๊ณ„ํš๋ฒ• 2 (0)
        • ์ตœ๋‹จ ๊ฒฝ๋กœ (0)
        • ํŠธ๋ฆฌ (0)
        • ๋ฐฑํŠธ๋ž˜ํ‚น (0)
        • ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ (0)
        • ์ง‘ํ•ฉ๊ณผ ๋งต (1)
      • ๐ŸŒˆ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค (0)
      • ๐Ÿ“ฑ ์•ˆ๋“œ๋กœ์ด๋“œ ์•ฑ (0)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ํ™ˆ
    • ํƒœ๊ทธ
    • ๋ฐฉ๋ช…๋ก
  • ๋งํฌ

  • ๊ณต์ง€์‚ฌํ•ญ

    • โœจ์ž๋ฃŒ๊ตฌ์กฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ปค๋ฆฌํ˜๋Ÿผโœจ
  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

    ํ† ์ต 950์ 
    ํ† ์ต
    ํ† ์ต 900์ ๋Œ€
    ๋น…์˜คํ‘œ๊ธฐ๋ฒ•
    ๊ทธ๋ž˜ํ”„ํƒ์ƒ‰
    ํ† ์ต 900
    ํ† ์ต 920์ 
    ์ตœ๋‹จ๊ฒฝ๋กœ
    ์ •๋ ฌ ์ตœ์•…์˜ ๊ฒฝ์šฐ
    ํ† ์ต 900์ 
    ์‹œ๊ฐ„๋ณต์žก๋„
    ์•Œ๊ณ ๋ฆฌ์ฆ˜
    ์ •๋ ฌ ์ตœ์„ ์˜ ๊ฒฝ์šฐ
    ์ •๋ ฌ
    ํ† ์ต 910์ 
  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • ์ตœ๊ทผ ๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
juno1105
์‚ฝ์ž…์ •๋ ฌ(InsertionSort)์ด๋ž€?
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”