๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿ–ฅ Computer Science/Algorithm

[Algorithm] ํ€ต ์ •๋ ฌ(Quick Sort)๋ž€? (feat. Swift)

by Fomagran ๐Ÿ’ป 2021. 10. 25.
728x90
๋ฐ˜์‘ํ˜•

์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป  ์ž…๋‹ˆ๋‹ค!

 

์˜ค๋Š˜์€ ๋“œ๋””์–ด ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ๋ง ๊ทธ๋Œ€๋กœ ๋งค์šฐ ๋น ๋ฅธ ์ˆ˜ํ–‰์‹œ๊ฐ„์„ ๊ฐ€์ง„ ํ€ต ์ •๋ ฌ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค!

 

๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~


ํ€ต ์ •๋ ฌ(Quick Sort)์ด๋ž€? ๐Ÿง

 

ํ€ต ์ •๋ ฌ(Quicksort)์€ ์ฐฐ์Šค ์•คํ„ฐ๋‹ˆ ๋ฆฌ์ฒ˜๋“œ ํ˜ธ์–ด๊ฐ€ ๊ฐœ๋ฐœํ•œ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋‹ค๋ฅธ ์›์†Œ์™€์˜ ๋น„๊ต๋งŒ์œผ๋กœ ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๋น„๊ต ์ •๋ ฌ์— ์†ํ•œ๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ -

 

(์ฐธ๊ณ ๋กœ ๋ฆฌ์ฒ˜๋“œ ํ˜ธ์–ด๊ฐ€ ํ€ต ์ •๋ ฌ์„ ๊ฐœ๋ฐœํ–ˆ์„ ๋‹น์‹œ ๋‚˜์ด๋Š” 26์‚ด์ด๋ผ๊ณ  ํ•˜๋„ค์š”...)

 

ํ•ฉ๋ณ‘ ์ •๋ ฌ๊ณผ ๊ฐ™์ด ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์†ํ•˜๊ณ  ํ‰๊ท ์ ์œผ๋กœ ๋งค์šฐ ๋น ๋ฅธ ์ˆ˜ํ–‰์†๋„๋ฅผ ์ž๋ž‘ํ•ฉ๋‹ˆ๋‹ค.


ํ€ต ์ •๋ ฌ ๊ณผ์ • ๐Ÿ”จ

 

ํ€ต ์ •๋ ฌ์„ ํ•˜๊ธฐ ์œ„ํ•ด์„  ํ”ผ๋ด‡(Pivot)์ด ํ•ต์‹ฌ์ด ๋˜๋Š”๋ฐ์š”.

 

์—ฌ๊ธฐ์„œ ํ”ผ๋ด‡์€ ์–ด๋–ค ๊ฒƒ์ผ๊นŒ์š”?

 

ํ”ผ๋ด‡์€ ๋ฐ”๋กœ ๊ธฐ์ค€์ž…๋‹ˆ๋‹ค.

 

ํ”ผ๋ด‡์„ ๊ฐ€์žฅ ์ฒซ ๋ฒˆ์งธ ์ธ๋ฑ์Šค๋ฅผ ์„ ํƒํ•  ์ˆ˜๋„ ์žˆ๊ณ  ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ์ธ๋ฑ์Šค๋ฅผ ์„ ํƒํ•  ์ˆ˜๋„ ์žˆ๊ณ  ์ค‘๊ฐ„์— ์žˆ๋Š” ์ธ๋ฑ์Šค๋ฅผ ์„ ํƒํ•  ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค.

 

ํ”ผ๋ด‡์„ ์–ด๋–ค ๊ฒƒ์„ ์„ ํƒํ•˜๋ƒ์— ๋”ฐ๋ผ์„œ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์ด ๋‹ฌ๋ผ์ง€๋Š”๋ฐ์š”.

 

์ด๋ฒˆ ์‹œ๊ฐ„์—๋Š” ์ค‘๊ฐ„ ์ง€์ ์„ ํ”ผ๋ด‡์œผ๋กœ ์žก๋Š” ํ€ต ์ •๋ ฌ ๋ฐฉ์‹์œผ๋กœ ์ง„ํ–‰ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

์•„๋ž˜์™€ ๊ฐ™์€ ๋ฐฐ์—ด์ด ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

 

10๊ฐœ์˜ ์›์†Œ๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ ์ค‘๊ฐ„๊ฐ’์€ 5๋ฒˆ์งธ์ธ 2๊ฐ€ ๋˜๊ฒ ์ฃ ?

 

๊ฐ€์žฅ ์™ผ์ชฝ๊ณผ ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ์— ํฌ์ธํ„ฐ๋ฅผ ๋‹ฌ์•„์ค๋‹ˆ๋‹ค.

 

์™ผ์ชฝ ํฌ์ธํ„ฐ๋Š” ํ”ผ๋ด‡์˜ ๊ฐ’๋ณด๋‹ค ๋” ํฌ๊ฑฐ๋‚˜ ๊ฐ™์€ ๊ฐ’์ด ๋‚˜์˜ฌ ๋•Œ๊นŒ์ง€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ง„ํ–‰ํ•˜๊ณ 

 

์˜ค๋ฅธ์ชฝ ํฌ์ธํ„ฐ๋Š” ํ”ผ๋ด‡์˜ ๊ฐ’๋ณด๋‹ค ๋” ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ๊ฐ’์ด ๋‚˜์˜ฌ ๋•Œ๊นŒ์ง€ ์™ผ์ชฝ์œผ๋กœ ์ง„ํ–‰ํ• ๊ฑฐ์—์š”.

 

 

์™ผ์ชฝ ํฌ์ธํ„ฐ๋ฅผ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์˜ฎ๊ธฐ๋ ค๋Š”๋ฐ ์ด๋ฏธ ํ”ผ๋ด‡๊ฐ’๋ณด๋‹ค ๋” ํฐ ๊ฐ’์ด ์žˆ์ฃ ?

 

์ด ๋•Œ๋Š” ํ”ผ๋ด‡๊ณผ ํฌ์ธํ„ฐ์˜ ๊ฐ’์„ ์„œ๋กœ ๋ฐ”๊ฟ”์ค๋‹ˆ๋‹ค.

 

 

๊ทธ ๋‹ค์Œ์—” ์˜ค๋ฅธ์ชฝ ํฌ์ธํ„ฐ๋ฅผ ์™ผ์ชฝ์œผ๋กœ ์›€์ง์—ฌ์ฃผ๋ ค๋Š”๋ฐ ์ด๋ฏธ ํ”ผ๋ด‡๊ฐ’๋ณด๋‹ค ์ž‘์•„์ ธ์žˆ์ฃ ?

 

ํ”ผ๋ด‡๊ฐ’๊ณผ ์˜ค๋ฅธ์ชฝ ํฌ์ธํ„ฐ ๊ฐ’์„ ๋ฐ”๊ฟ”์ค๋‹ˆ๋‹ค.

 

 

์ด์ œ ๋˜ ๋‹ค์‹œ ์™ผ์ชฝ์— ์žˆ๋Š” ํฌ์ธํ„ฐ๋ฅผ ํ”ผ๋ด‡๊ฐ’๋ณด๋‹ค ๋” ํฌ๊ฑฐ๋‚˜ ๊ฐ™์„ ๋•Œ๊นŒ์ง€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์›€์ง์—ฌ ์ค๋‹ˆ๋‹ค.

 

ํ”ผ๋ด‡ ๊ฐ’์ด 6์ด๋ฏ€๋กœ 8์—์„œ ๋ฉˆ์ถ”๊ฒ ์ฃ ? 8๊ณผ 6์„ ์Šค์™‘ํ•ด์ค๋‹ˆ๋‹ค.

 

 

์˜ค๋ฅธ์ชฝ ํฌ์ธํ„ฐ๋ฅผ ํ”ผ๋ด‡ ๊ฐ’๋ณด๋‹ค ๋” ์ž‘์„ ๋•Œ๊นŒ์ง€ ์™ผ์ชฝ์œผ๋กœ ์›€์ง์—ฌ์ค๋‹ˆ๋‹ค.

 

๋ฐ”๋กœ ์˜†์ธ 5์—์„œ ๋ฉˆ์ถ”๊ฒ ์ฃ ? 5์™€ 8์„ ์Šค์™‘ํ•ด์ค๋‹ˆ๋‹ค.

 

 

 

์ด๋Ÿฐ ์‹์œผ๋กœ ์ง„ํ–‰ํ•ด์ฃผ๋ฉด ์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ์ด ๊ฒน์น˜๋Š” ์ˆœ๊ฐ„์ด ์˜ต๋‹ˆ๋‹ค.

 

 

์ด ๋• ๊ฒน์น˜๋Š” ์ธ๋ฑ์Šค๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋‚˜๋ˆ ์ค๋‹ˆ๋‹ค.

 

๋‚˜๋ˆ ์ง„ ์›์†Œ๋“ค์„ ์œ„์™€ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ์ง„ํ–‰ํ•ด์ค๋‹ˆ๋‹ค.

 

 

์˜ค๋ฅธ์ชฝ์˜ ๋นจ๊ฐ„๋ฐ•์Šค๋ถ€ํ„ฐ ์ง„ํ–‰ํ•ด์ฃผ๋ฉด ์•„๋ž˜์™€ ๊ฐ™์ด 7,6,9๋กœ ๋‚˜๋ˆ ์ง€๊ณ  9,10์œผ๋กœ ๋‚˜๋ˆ ์ง‘๋‹ˆ๋‹ค.

 

๋˜ 9,10์„ ํ€ต ์ •๋ ฌ ๋ฐฉ์‹์œผ๋กœ ์ง„ํ–‰ํ•˜๋ฉด 9์™€ 10์œผ๋กœ ๋‚˜๋ˆ ์ง€๊ณ  1๊ฐœ์”ฉ ์›์†Œ๊ฐ€ ๋‚จ์•˜๋‹ค๋ฉด ํ•ฉ์ณ์ค๋‹ˆ๋‹ค. (์ด๋ž˜์„œ ๋ถ„ํ• ์ •๋ณต ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค.)

 

์ด๋ฒˆ์—” ์™ผ์ชฝ์˜ ๋นจ๊ฐ„ ๋ฐ•์Šค๋ฅผ ํ€ต์ •๋ ฌ ๋ฐฉ์‹์œผ๋กœ ์ง„ํ–‰ํ•ด์ฃผ๋ฉด 6,7 ๊ทธ๋ฆฌ๊ณ  8์ด ๋‚จ๊ฒŒ๋  ๊ฒƒ ์ž…๋‹ˆ๋‹ค.

 

6๊ณผ 7์„ ํ€ต์ •๋ ฌ ๋ฐฉ์‹์œผ๋กœ ๋‚˜๋ˆ ์ฃผ๊ณ  ํ•ฉ์ณ์ค๋‹ˆ๋‹ค. 

 

๊ทธ๋ฆฌ๊ณ  ์ด๋ฏธ ํ•ฉ์ณ์ง„ ์›์†Œ๋“ค์„ ๋ชจ๋‘ ํ•ฉ์ณ์ค๋‹ˆ๋‹ค.

 

 

์ด๋ฒˆ์—” ์ž‘์€ ๊ฐ’๋“ค์ด์—ˆ๋˜ ํŒŒ๋ž€ ๋ฐ•์Šค๋ฅผ ์ง„ํ–‰ํ•˜๋ฉด

 

 

2,1,3๊ณผ 4,5๋กœ ๋‚˜๋ˆ ์ง€๊ณ 

 

 

1,2์™€ 3์œผ๋กœ ๋‚˜๋ˆ ์ง€๊ณ  4์™€ 5๊ฐ€ ํ•ฉ์ณ์ง€๊ฒ ์ฃ ?

 

 

์ด์   ์™ผ์ชฝ์— ๋ชจ๋“  ๊ฐ’์„ ํ•ฉ์ณ์ค๋‹ˆ๋‹ค.

 

 

 

๋งˆ์ง€๋ง‰์œผ๋กœ ์ „์— ํ•ฉ์ณ๋’€๋˜ ์˜ค๋ฅธ์ชฝ์˜ ๊ฐ’๋“ค๊ณผ ์™ผ์ชฝ ๊ฐ’๋“ค์„ ๋ชจ๋‘ ํ•ฉ์ณ์ค๋‹ˆ๋‹ค.

 

์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ๋ชจ๋“  ์›์†Œ๊ฐ€ ์ •๋ ฌ๋ฉ๋‹ˆ๋‹ค.

 

 

ํ€ต ์ •๋ ฌ ๊ณผ์ •์„ ์ด๋ฏธ์ง€๋กœ ๋ณด๋ฉด ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

 

์ถœ์ฒ˜: ์œ„ํ‚ค๋ฐฑ๊ณผ


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

 

ํ€ต ์ •๋ ฌ์€ ์–ด๋–ค ๊ฒƒ์„ ํ”ผ๋ด‡์œผ๋กœ ์„ ํƒํ•˜๋Š”์ง€์— ๋”ฐ๋ผ์„œ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ ๋‹ฌ๋ผ์ง‘๋‹ˆ๋‹ค.

 

๋งŒ์•ฝ 1,2,3,4,5,6,7,8,9,10์ด ์žˆ๊ณ  ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ์˜ 10์„ ํ”ผ๋ด‡์œผ๋กœ ์„ ํƒํ–ˆ๋‹ค๋ฉด ์ตœ์•…์˜ ๊ฒฝ์šฐ์ธ O(n²) ์ž…๋‹ˆ๋‹ค.

 

ํ•˜์ง€๋งŒ ํ‰๊ท ์ ์ธ ์ˆ˜ํ–‰์‹œ๊ฐ„์€ nlogn ์ž…๋‹ˆ๋‹ค.


์ฝ”๋“œ ๊ตฌํ˜„ ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป

 

๋จผ์ € ๋ถ„ํ• ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ฝ”๋“œ๋กœ ๊ตฌํ˜„ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

๋จผ์ € ํ”ผ๋ด‡,์™ผ์ชฝ,์˜ค๋ฅธ์ชฝ ์ธ๋ฑ์Šค ๊ฐ’์„ ์ •ํ•ด์ค๋‹ˆ๋‹ค.

 

๊ทธ๋ฆฌ๊ณ  ํ˜„์žฌ ์›€์ง์—ฌ์•ผํ•  ํฌ์ธํ„ฐ๊ฐ€ ์™ผ์ชฝ์ธ์ง€ ์˜ค๋ฅธ์ชฝ์ธ์ง€ ์•Œ๋ ค์ค„ ๋ณ€์ˆ˜๋„ ์ •ํ•ด์ค๋‹ˆ๋‹ค.

 

๋งŒ์•ฝ ์›์†Œ๊ฐ€ 1๊ฐœ๋งŒ ๋‚จ์•˜๋‹ค๋ฉด ์›์†Œ๋“ค์„ ๊ทธ๋Œ€๋กœ ๋ฐ˜ํ™˜ํ•ด์ค๋‹ˆ๋‹ค.

 

func divide(_ list:[Element]) -> [Element] {
        if list.count < 2 { return list }
        var newList:[Element] = list
        let pivotIndex:Int = newList.count/2-1
        var leftIndex:Int = 0
        var rightIndex:Int = newList.count-1
        var isLeft:Bool = true
        
	...

 

์œ„์—์„œ ๊ตฌํ˜„ํ–ˆ๋˜๋Œ€๋กœ ์™ผ์ชฝ ํฌ์ธํ„ฐ์™€ ์˜ค๋ฅธ์ชฝ ํฌ์ธํ„ฐ๋ž‘ ๊ฒน์น  ๋•Œ๊นŒ์ง€ ํฌ์ธํ„ฐ๋ฅผ ์›€์ง์—ฌ์ค๋‹ˆ๋‹ค.

 

์›€์ง์—ฌ์•ผํ•  ํฌ์ธํ„ฐ๊ฐ€ ์™ผ์ชฝ์ด๋ผ๋ฉด ํ”ผ๋ด‡์˜ ๊ฐ’๊ณผ ๋น„๊ตํ•ด์„œ ๋” ์ž‘๋‹ค๋ฉด ํฌ์ธํ„ฐ๋ฅผ +1 ํ•ด์ฃผ๊ณ  ๋” ํฌ๋‹ค๋ฉด ํ”ผ๋ด‡๊ฐ’๊ณผ ์™ผ์ชฝ ๊ฐ’์„ ๋ฐ”๊ฟ”์ค๋‹ˆ๋‹ค.

 

์˜ค๋ฅธ์ชฝ ํฌ์ธํ„ฐ๋ผ๋ฉด ํ”ผ๋ด‡์˜ ๊ฐ’๊ณผ ๋น„๊ตํ•ด์„œ ๋” ํฌ๋‹ค๋ฉด ํฌ์ธํ„ฐ๋ฅผ +1 ํ•ด์ฃผ๊ณ  ๋” ์ž‘๋‹ค๋ฉด ํ”ผ๋ด‡๊ฐ’๊ณผ ์˜ค๋ฅธ์ชฝ ๊ฐ’์„ ๋ฐ”๊ฟ”์ค๋‹ˆ๋‹ค.

 

๊ทธ๋ฆฌ๊ณ  ๋งˆ์ง€๋ง‰์— ์›€์ง์—ฌ์•ผํ•  ํฌ์ธํ„ฐ๋ฅผ toggle๋กœ ๋ฐ”๊ฟ”์ค๋‹ˆ๋‹ค.

 

 while leftIndex < rightIndex {
            if isLeft {
                if newList[leftIndex] < newList[pivotIndex] {
                    leftIndex += 1
                }else {
                    newList.swapAt(pivotIndex, leftIndex)
                }
            }else {
                if newList[rightIndex] > newList[pivotIndex] {
                    rightIndex -= 1
                }else {
                    newList.swapAt(pivotIndex, rightIndex)
                }
            }
            isLeft.toggle()
        }

 

๋งˆ์ง€๋ง‰์œผ๋กœ ๊ฒน์นœ ํฌ์ธํ„ฐ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋‚˜๋ˆ ์ค€ ๋’ค ์žฌ๊ท€ํ•จ์ˆ˜๋กœ ๋ฐ˜๋ณตํ•ด์ค๋‹ˆ๋‹ค.

 

  	let left:[Element] = Array(newList[0...leftIndex])
  	let right:[Element] = Array(newList[leftIndex+1..<newList.count])
  	return merge(divide(left),divide(right))
  }

 

์›์†Œ๊ฐ€ 1๊ฐœ๊ฐ€ ๋‚จ์„ ๋•Œ์ง€ ๋ชจ๋‘ ๋ถ„ํ• ํ–ˆ๋‹ค๋ฉด ์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ์„ ํ•ฉ์ณ์ค๋‹ˆ๋‹ค.

 

func merge(_ left:[Element],_ right:[Element]) -> [Element] {
        return left + right
    }

Source Code

 

728x90
๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€