Sep 10, 2019 โ€ข2 min read โ˜•

๐Ÿ’ป Stable Sort, inplace algorithm์ด๋ž€? ์™œ ์ค‘์š”ํ•œ๊ฐ€?

Stable Sort


Stable sort๋ž€ ์ค‘๋ณต๋œ ํ‚ค๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ •๋ ฌํ•˜๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์„ ์ง€์นญํ•œ๋‹ค. ์ฆ‰, ๊ฐ™์€ ๊ฐ’์ด 2๊ฐœ ์ด์ƒ ๋ฆฌ์ŠคํŠธ์— ๋“ฑ์žฅํ•  ๋•Œ ๊ธฐ์กด ๋ฆฌ์ŠคํŠธ์— ์žˆ๋˜ ์ˆœ์„œ๋Œ€๋กœ ์ค‘๋ณต๋œ ํ‚ค๋“ค์ด ์ •๋ ฌ๋œ ๋‹ค๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ๋‹ค์Œ๊ณผ ๊ฐ™์€ list๊ฐ€ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋ณด์ž.

numbers = [9, 3, 12, 1, 6, 2, 1]

์ด ๋ฆฌ์ŠคํŠธ์—์„œ 1 ์ด๋ผ๋Š” ๊ฐ’์ด ์ค‘๋ณต์ด ๋œ๋‹ค. ์ด๋•Œ ์ค‘๋ณต๋˜๋Š” 1์˜ ๊ฐ’๋“ค์„ ๊ตฌ๋ถ„ํ•ด์„œ ์ž‘์„ฑํ•ด๋ณด๋ ค๊ณ  ํ•œ๋‹ค.

numbers = [9, 3, 12, 1(1๋ฒˆ์งธ), 6, 2, 1(2๋ฒˆ์งธ)]

๋งŒ์•ฝ ์ด ๋ฆฌ์ŠคํŠธ๋ฅผ stable sort ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ์ •๋ ฌ์„ ํ•œ๋‹ค๋ฉด ๊ฒฐ๊ณผ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์„ ๊ฒƒ์ด๋‹ค.

[1(1๋ฒˆ์งธ), 1(2๋ฒˆ์งธ), 2, 3, 6, 9, 12]

์ด์ฒ˜๋Ÿผ ๊ธฐ์กด ๋ฆฌ์ŠคํŠธ์—์„œ ์ค‘๋ณต๋œ ๊ฐ’๋“ค์—๊ฒŒ ์ˆœ์„œ๊ฐ€ ๋งค๊ฒจ์กŒ๋Š”๋ฐ, ๊ทธ ์ˆœ์„œ๋Œ€๋กœ ์ •๋ ฌ์ด ๋ฌ์„ ๋•Œ ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ stable sort๋ผ๊ณ  ๋ถ€๋ฅผ ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์ด๋‹ค.

Why Stable Sort?

๊ทธ๋ ‡๋‹ค๋ฉด ์™œ stable sort๊ฐ€ ์ค‘์š”ํ•œ์ง€ ๊ถ๊ธˆํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ ์ด์œ ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

  • stable sort๋กœ ์ •๋ ฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์˜ ์ˆœ์„œ๋Š” ํ•ญ์ƒ ๋˜‘๊ฐ™๊ธฐ์— ํ•ญ์ƒ ๊ฒฐ๊ณผ๊ฐ€ ๊ฐ™์Œ์„ ๋ณด์žฅํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ์ˆซ์ž๋ฅผ sortingํ•  ๋•Œ๋Š” stability๊ฐ€ ์ค‘์š”ํ•˜์ง€ ์•Š์„ ์ˆ˜ ์žˆ์ง€๋งŒ, ์ฒซ ๋ฌธ์ž๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ฌธ์ž์—ด์„ ์ •๋ ฌํ•˜๋Š” ๊ฒฝ์šฐ์—์„œ๋Š” ํ•ญ์ƒ ์•ˆ์ •์ ์œผ๋กœ ๊ฐ™์€ ๋ฆฌ์ŠคํŠธ๊ฐ€ ๋ฆฌํ„ด๋˜๋Š” ๊ฒƒ์ด ๋ฐ”๋žŒ์งํ•  ๊ฒƒ์ด๋‹ค. (์™œ๋ƒํ•˜๋ฉด ์ •๋ ฌํ•  ๋•Œ๋งˆ๋‹ค ์ˆœ์„œ๊ฐ€ ๋‹ค๋ฅด๋ฉด ํ˜ผ๋ž€์Šค๋Ÿฌ์šธ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค)

Stable Sorting ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

  • Insertion Sort
  • Merge Sort
  • Bubble Sort
  • Counting Sort

Unstable Sorting ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

  • Heap Sort
  • Selection sort
  • Shell sort
  • Quick Sort

Inplace algrithm

Inplace ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€ ์ถ”๊ฐ€์ ์ธ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ๋งŽ์ด ํ•„์š”๋กœ ํ•˜์ง€ ์•Š๋Š” ํ˜น์€ ์ „ํ˜€ ํ•„์š”ํ•˜์ง€ ์•Š๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์˜๋ฏธํ•œ๋‹ค. ํ†ต์ƒ์ ์œผ๋กœ, ๊ณต๊ฐ„์€ O(logn)์ด๊ณ  O(n)์ด ๋  ๋•Œ๋„ ์žˆ๋‹ค.

์ฆ‰, n ๊ธธ์ด์˜ ๋ฆฌ์ŠคํŠธ๊ฐ€ ์žˆ๊ณ , ์ด ๋ฆฌ์ŠคํŠธ๋ฅผ ์ •๋ ฌํ•  ๋•Œ ์ถ”๊ฐ€์ ์œผ๋กœ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ํ• ๋‹นํ•˜์ง€ ์•Š์•„๋„ ์ •๋ ฌ์ด ์ด๋ค„์ง„๋‹ค๋ฉด in-place ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ๊ณ  ๋ถˆ๋ฆด ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์ด๋‹ค.

inplace

In-placeํ•˜์ง€ ์•Š์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ n ๊ธธ์ด์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ •๋ ฌํ•  ๋•Œ n ๋งŒํผ์˜ ๋ฉ”๋ชจ๋ฆฌ๋ณด๋‹ค ๋” ๋งŽ์€ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ํ• ๋‹นํ•œ๋‹ค. ์ฆ‰, ์ด๋Ÿฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์€ space complexity๊ฐ€ ๋†’๋‹ค.

notinplace
ยฉ 2021 Dojin Kim, Built with Gatsby