๐Ÿงช ์ปดํ“จํ„ฐ๊ณผํ•™ : CS

[Alogrithm] ์‚ฝ์ž… ์ •๋ ฌ (Injection Sort)

๊ฐœ๋ฐœ์ž HOON 2022. 9. 3. 14:13

์‚ฝ์ž… ์ •๋ ฌ (Injection Sort)

 ์‚ฝ์ž… ์ •๋ ฌ์€, ํ•œ ๋ฐฐ์—ด์„ '์•ž ๋ฐฐ์—ด'๊ณผ '๋’ท ๋ฐฐ์—ด'๋กœ ์ชผ๊ฐœ์–ด '๋’ท ๋ฐฐ์—ด'์˜ ์š”์†Œ๋ฅผ ์ •๋ ฌ๋œ '์•ž ๋ฐฐ์—ด'์— ๋“ค์–ด๊ฐˆ ์˜ฌ๋ฐ”๋ฅธ ์œ„์น˜๋ฅผ ์ฐพ์•„ ์‚ฝ์ž…ํ•˜๋Š” ์ •๋ ฌ์ด๋‹ค. ์ž˜ ์ดํ•ด๊ฐ€ ๋˜์ง€ ์•Š์„ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ํ•˜๋‚˜์”ฉ ์„ค๋ช…์„ ํ•ด๋ณด๊ฒ ๋‹ค.

 

๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์ด ์žˆ๋‹ค๊ณ  ํ•˜์ž.

array = [3, 4, 5, 2, 1, 6, 7]
3 4 5 2 1 6 7

์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ „, ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์„ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋นจ๊ฐ„ ๋ถ€๋ถ„๊ณผ ํŒŒ๋ž€ ๋ถ€๋ถ„์œผ๋กœ ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

๋นจ๊ฐ„ ๋ถ€๋ถ„์€ ์ด๋ฏธ ์ •๋ ฌ์ด ๋œ '์•ž ๋ฐฐ์—ด',

ํŒŒ๋ž€ ๋ถ€๋ถ„์€ '์•ž ๋ฐฐ์—ด'์— ์‚ฝ์ž…์ด ๋˜๊ธฐ ์œ„ํ•ด ๋Œ€๊ธฐํ•˜๊ณ  ์žˆ๋Š” '๋’ท ๋ฐฐ์—ด'๋กœ ์ดํ•ดํ•˜๋ฉด ์ข‹๋‹ค.

 

์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ '๋’ท ๋ฐฐ์—ด'์— ๋“ค์–ด์žˆ๋Š” ์ฒซ ๋ฒˆ์งธ ์›์†Œ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋ฏ€๋กœ, ์ „์ฒด ๋ฐฐ์—ด๋กœ ์ƒ๊ฐํ•˜๋ฉด ๋‘ ๋ฒˆ์งธ ์š”์†Œ๋ถ€ํ„ฐ ์ •๋ ฌ ๋Œ€์ƒ์ด ๋œ๋‹ค.

๋‘ ๋ฒˆ์งธ ์›์†Œ '4'๋Š” '์•ž ๋ฐฐ์—ด'์˜ ์ œ์ผ ๋งˆ์ง€๋ง‰ ์›์†Œ์ธ '3'๋ณด๋‹ค ํฌ๋ฏ€๋กœ, ์ด๋™ํ•˜์ง€ ์•Š๊ณ  ์ž๋ฆฌ๊ฐ€ ๊ฒฐ์ •๋œ๋‹ค.

3 4 5 2 1 6 7

์„ธ ๋ฒˆ์งธ ์›์†Œ '5'๋Š” '์•ž ๋ฐฐ์—ด'์˜ ์ œ์ผ ๋งˆ์ง€๋ง‰ ์›์†Œ์ธ '4'๋ณด๋‹ค ํฌ๋ฏ€๋กœ, ์ด๋™ํ•˜์ง€ ์•Š๊ณ  ์ž๋ฆฌ๊ฐ€ ๊ฒฐ์ •๋œ๋‹ค.

3 4 5 2 1 6 7

๋„ค ๋ฒˆ์งธ ์›์†Œ๋ฅผ ๋ณด์ž. '2'๋Š” '์•ž ๋ฐฐ์—ด'์˜ ์ œ์ผ ๋งˆ์ง€๋ง‰ ์›์†Œ์ธ '5'๋ณด๋‹ค ์ž‘์œผ๋ฏ€๋กœ ์•ž์œผ๋กœ ํ•œ ์นธ ์ด๋™ํ•œ๋‹ค.

'2'๋Š” ๊ทธ ์•ž์ธ '4'๋ณด๋‹ค ์ž‘์œผ๋ฏ€๋กœ ์•ž์œผ๋กœ ํ•œ ์นธ ๋” ์ด๋™ํ•˜๊ณ ,

๊ทธ ์•ž์ธ '3'๋ณด๋‹ค ์ž‘์œผ๋ฏ€๋กœ ์•ž์œผ๋กœ ํ•œ ์นธ ๋” ์ด๋™ํ•œ๋‹ค.

๋”ฐ๋ผ์„œ ์•ž์— ์•„๋ฌด๊ฒƒ๋„ ์—†๊ฑฐ๋‚˜, ์•ž์˜ ์›์†Œ๋ณด๋‹ค '2'๊ฐ€ ๋” ํฌ๋‹ค๋ฉด ์ด๋™์„ ๋ฉˆ์ถ”๊ณ  ์ž๋ฆฌ๋ฅผ ๊ฒฐ์ •ํ•œ๋‹ค. 

3 4 2 5 1 6 7
3 2 4 5 1 6 7
2 3 4 5 1 6 7
2 3 4 5 1 6 7

 

์ด์™€ ๊ฐ™์€ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜๋ฉด, ์‚ฝ์ž… ์ •๋ ฌ์ด ์™„๋ฃŒ๋œ๋‹ค. ์ฝ”๋“œ๋ฅผ ์‚ดํŽด๋ณด์ž.

 

์‚ฝ์ž… ์ •๋ ฌ ํŒŒ์ด์ฌ ์ฝ”๋“œ

 

 

์‚ฝ์ž… ์ •๋ ฌ ์ž๋ฐ” ์ฝ”๋“œ

 

 

 

์‚ฝ์ž… ์ •๋ ฌ ์žฅ๋‹จ์ 

 

- ์‚ฝ์ž…์ •๋ ฌ์˜ ์žฅ์ 

Best case์˜ ๊ฒฝ์šฐ, O(N)์ด๋ผ๋Š” ์ข‹์€ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.

๋น„๊ตํšŸ์ˆ˜๋ฅผ ๋ฒ„๋ธ”์ •๋ ฌ์— ๋น„ํ•ด ํ™•์—ฐํžˆ ์ค„์˜€๋‹ค.

์ด๋ฏธ ์ •๋ ฌ๋œ ๋ฐฐ์—ด, ํฌ๊ธฐ๊ฐ€ ์ž‘์€ ๋ฐฐ์—ด์— ์œ ์šฉํ•˜๋‹ค.

 

- ์‚ฝ์ž…์ •๋ ฌ์˜ ๋‹จ์ 

Worst case์˜ ๊ฒฝ์šฐ O(n^2)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

๋ฐ์ดํ„ฐ์˜ ์ƒํƒœ์™€ ํฌ๊ธฐ์— ๋”ฐ๋ผ ์„ฑ๋Šฅ์˜ ํŽธ์ฐจ๊ฐ€ ์‹ฌํ•˜๋‹ค.