# ์‚ฝ์ž… ์ •๋ ฌ(Insertion Sort)


# Goal


  • Insertion Sort์— ๋Œ€ํ•ด ์„ค๋ช…ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Insertion Sort ๊ณผ์ •์— ๋Œ€ํ•ด ์„ค๋ช…ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Insertion Sort์„ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Insertion Sort์˜ ์‹œ๊ฐ„๋ณต์žก๋„์™€ ๊ณต๊ฐ„๋ณต์žก๋„๋ฅผ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Insertion Sort์™€ Selection Sort ์ฐจ์ด์— ๋Œ€ํ•ด ์„ค๋ช…ํ•  ์ˆ˜ ์žˆ๋‹ค.

# Abstract


์† ์•ˆ์˜ ์นด๋“œ๋ฅผ ์ •๋ ฌํ•˜๋Š” ๋ฐฉ๋ฒ•๊ณผ ์œ ์‚ฌํ•˜๋‹ค.

Insertion Sort๋Š” Selection Sort์™€ ์œ ์‚ฌํ•˜์ง€๋งŒ, ์ข€ ๋” ํšจ์œจ์ ์ธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

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

์ตœ์„ ์˜ ๊ฒฝ์šฐ O(N)์ด๋ผ๋Š” ์—„์ฒญ๋‚˜๊ฒŒ ๋น ๋ฅธ ํšจ์œจ์„ฑ์„ ๊ฐ€์ง€๊ณ  ์žˆ์–ด, ๋‹ค๋ฅธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ผ๋ถ€๋กœ ์‚ฌ์šฉ๋  ๋งŒํผ ์ข‹์€ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

# Process (Ascending)


  1. ์ •๋ ฌ์€ 2๋ฒˆ์งธ ์œ„์น˜(index)์˜ ๊ฐ’์„ temp์— ์ €์žฅํ•œ๋‹ค.
  2. temp์™€ ์ด์ „์— ์žˆ๋Š” ์›์†Œ๋“ค๊ณผ ๋น„๊ตํ•˜๋ฉฐ ์‚ฝ์ž…ํ•ด๋‚˜๊ฐ„๋‹ค.
  3. '1'๋ฒˆ์œผ๋กœ ๋Œ์•„๊ฐ€ ๋‹ค์Œ ์œ„์น˜(index)์˜ ๊ฐ’์„ temp์— ์ €์žฅํ•˜๊ณ , ๋ฐ˜๋ณตํ•œ๋‹ค.

# Java Code (Ascending)


void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){ // 1.
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {    // 2.
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           // 3.
   }
   System.out.println(Arrays.toString(arr));
}
  1. ์ฒซ ๋ฒˆ์งธ ์›์†Œ ์•ž(์™ผ์ชฝ)์—๋Š” ์–ด๋–ค ์›์†Œ๋„ ๊ฐ–๊ณ  ์žˆ์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์—, ๋‘ ๋ฒˆ์งธ ์œ„์น˜(index)๋ถ€ํ„ฐ ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•œ๋‹ค. temp์— ์ž„์‹œ๋กœ ํ•ด๋‹น ์œ„์น˜(index) ๊ฐ’์„ ์ €์žฅํ•˜๊ณ , prev์—๋Š” ํ•ด๋‹น ์œ„์น˜(index)์˜ ์ด์ „ ์œ„์น˜(index)๋ฅผ ์ €์žฅํ•œ๋‹ค.

  2. ์ด์ „ ์œ„์น˜(index)๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” prev๊ฐ€ ์Œ์ˆ˜๊ฐ€ ๋˜์ง€ ์•Š๊ณ , ์ด์ „ ์œ„์น˜(index)์˜ ๊ฐ’์ด '1'๋ฒˆ์—์„œ ์„ ํƒํ•œ ๊ฐ’๋ณด๋‹ค ํฌ๋‹ค๋ฉด, ์„œ๋กœ ๊ฐ’์„ ๊ตํ™˜ํ•ด์ฃผ๊ณ  prev๋ฅผ ๋” ์ด์ „ ์œ„์น˜(index)๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋„๋ก ํ•œ๋‹ค.

  3. '2'๋ฒˆ์—์„œ ๋ฐ˜๋ณต๋ฌธ์ด ๋๋‚˜๊ณ  ๋‚œ ๋’ค, prev์—๋Š” ํ˜„์žฌ temp ๊ฐ’๋ณด๋‹ค ์ž‘์€ ๊ฐ’๋“ค ์ค‘ ์ œ์ผ ํฐ ๊ฐ’์˜ ์œ„์น˜(index) ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ฒŒ ๋œ๋‹ค. ๋”ฐ๋ผ์„œ, (prev+1)์— temp ๊ฐ’์„ ์‚ฝ์ž…ํ•ด์ค€๋‹ค.


# GIF๋กœ ์ดํ•ดํ•˜๋Š” Insertion Sort


img (opens new window)


# ์‹œ๊ฐ„๋ณต์žก๋„


์ตœ์•…์˜ ๊ฒฝ์šฐ(์—ญ์œผ๋กœ ์ •๋ ฌ๋˜์–ด ์žˆ์„ ๊ฒฝ์šฐ) Selection Sort์™€ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 ์ฆ‰, O(n^2) ์ด๋‹ค.

ํ•˜์ง€๋งŒ, ๋ชจ๋‘ ์ •๋ ฌ์ด ๋˜์–ด์žˆ๋Š” ๊ฒฝ์šฐ(Optimal)ํ•œ ๊ฒฝ์šฐ, ํ•œ๋ฒˆ์”ฉ ๋ฐ–์— ๋น„๊ต๋ฅผ ์•ˆํ•˜๋ฏ€๋กœ O(n) ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค. ๋˜ํ•œ, ์ด๋ฏธ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๋ฐฐ์—ด์— ์ž๋ฃŒ๋ฅผ ํ•˜๋‚˜์”ฉ ์‚ฝ์ž…/์ œ๊ฑฐํ•˜๋Š” ๊ฒฝ์šฐ์—๋Š”, ํ˜„์‹ค์ ์œผ๋กœ ์ตœ๊ณ ์˜ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋˜๋Š”๋ฐ, ํƒ์ƒ‰์„ ์ œ์™ธํ•œ ์˜ค๋ฒ„ํ—ค๋“œ๊ฐ€ ๋งค์šฐ ์ ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

์ตœ์„ ์˜ ๊ฒฝ์šฐ๋Š” O(n) ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ–๊ณ , ํ‰๊ท ๊ณผ ์ตœ์•…์˜ ๊ฒฝ์šฐ O(n^2) ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ–๊ฒŒ ๋œ๋‹ค.


# ๊ณต๊ฐ„๋ณต์žก๋„


์ฃผ์–ด์ง„ ๋ฐฐ์—ด ์•ˆ์—์„œ ๊ตํ™˜(swap)์„ ํ†ตํ•ด, ์ •๋ ฌ์ด ์ˆ˜ํ–‰๋˜๋ฏ€๋กœ O(n) ์ด๋‹ค.


# ์žฅ์ 


  • ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋‹จ์ˆœํ•˜๋‹ค.

  • ๋Œ€๋ถ€๋ถ„์˜ ์›์†Œ๊ฐ€ ์ด๋ฏธ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ฒฝ์šฐ, ๋งค์šฐ ํšจ์œจ์ ์ผ ์ˆ˜ ์žˆ๋‹ค.

  • ์ •๋ ฌํ•˜๊ณ ์ž ํ•˜๋Š” ๋ฐฐ์—ด ์•ˆ์—์„œ ๊ตํ™˜ํ•˜๋Š” ๋ฐฉ์‹์ด๋ฏ€๋กœ, ๋‹ค๋ฅธ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ํ•„์š”๋กœ ํ•˜์ง€ ์•Š๋Š”๋‹ค. => ์ œ์ž๋ฆฌ ์ •๋ ฌ(in-place sorting)

  • ์•ˆ์ • ์ •๋ ฌ(Stable Sort) ์ด๋‹ค.

  • Selection Sort๋‚˜ Bubble Sort๊ณผ ๊ฐ™์€ O(n^2) ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋น„๊ตํ•˜์—ฌ ์ƒ๋Œ€์ ์œผ๋กœ ๋น ๋ฅด๋‹ค.


# ๋‹จ์ 


  • ํ‰๊ท ๊ณผ ์ตœ์•…์˜ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(n^2)์œผ๋กœ ๋น„ํšจ์œจ์ ์ด๋‹ค.

  • Bubble Sort์™€ Selection Sort์™€ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ, ๋ฐฐ์—ด์˜ ๊ธธ์ด๊ฐ€ ๊ธธ์–ด์งˆ์ˆ˜๋ก ๋น„ํšจ์œจ์ ์ด๋‹ค.


# Conclusion


Selection Sort์™€ Insertion Sort๋Š” k๋ฒˆ์งธ ๋ฐ˜๋ณต ์ดํ›„, ์ฒซ๋ฒˆ์งธ k ์š”์†Œ๊ฐ€ ์ •๋ ฌ๋œ ์ˆœ์„œ๋กœ ์˜จ๋‹ค๋Š” ์ ์—์„œ ์œ ์‚ฌํ•˜๋‹ค. ํ•˜์ง€๋งŒ, Selection Sort๋Š” k+1๋ฒˆ์งธ ์š”์†Œ๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด ๋‚˜๋จธ์ง€ ๋ชจ๋“  ์š”์†Œ๋“ค์„ ํƒ์ƒ‰ํ•˜์ง€๋งŒ Insertion Sort๋Š” k+1๋ฒˆ์งธ ์š”์†Œ๋ฅผ ๋ฐฐ์น˜ํ•˜๋Š” ๋ฐ ํ•„์š”ํ•œ ๋งŒํผ์˜ ์š”์†Œ๋งŒ ํƒ์ƒ‰ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํ›จ์”ฌ ํšจ์œจ์ ์œผ๋กœ ์‹คํ–‰๋œ๋‹ค๋Š” ์ฐจ์ด๊ฐ€ ์žˆ๋‹ค.


# [์ฐธ๊ณ  ์ž๋ฃŒ]

์ตœ์ข… ์ˆ˜์ • : 11/15/2021, 1:31:19 PM