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

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ์ •๋ ฌ(Sorting)

by hyebin (Helia) 2022. 3. 24.
๋ฐ˜์‘ํ˜•

์ •๋ ฌ(Sorting)

๋ฐ์ดํ„ฐ๋ฅผ ํŠน์ •ํ•œ ๊ธฐ์ค€์— ๋”ฐ๋ผ ์ˆœ์„œ๋Œ€๋กœ ๋‚˜์—ดํ•˜๋Š” ๊ฒƒ์„ ๋งํ•œ๋‹ค.

 

์„ ํƒ ์ •๋ ฌ(Selection Sort)

์ •๋ ฌ๋˜์ง€ ์•Š์€ ๋ฐ์ดํ„ฐ ์ค‘์—์„œ ๊ฐ€์žฅ ์ž‘์€ ๊ฒƒ์„ ์„ ํƒํ•ด ๋งจ ์•ž์œผ๋กœ ๋ณด๋‚ธ๋‹ค.

๋‹ค๋ฅธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์— ๋น„ํ•ด ๋น„ํšจ์œจ์ ์ด๋‹ค.

→ ์‹œ๊ฐ„ ๋ณต์žก๋„: O(N^2)

 

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

๋ฐ์ดํ„ฐ๋ฅผ ํ•˜๋‹ˆ์”ฉ ํ™•์ธํ•˜๋ฉฐ, ๊ฐ ๋ฐ์ดํ„ฐ๋ฅผ ์ ์ ˆํ•œ ์œ„์น˜์— ์‚ฝ์ž…ํ•œ๋‹ค.

๋ฐ์ดํ„ฐ๊ฐ€ ๊ฑฐ์˜ ์ •๋ ฌ๋˜์–ด ์žˆ์„ ๋•Œ ํšจ์œจ์ ์ด๋‹ค.

→ ์‹œ๊ฐ„ ๋ณต์žก๋„: O(N^2) <์ตœ์„ ์˜ ๊ฒฝ์šฐ O(N)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.>

 

ํ€ต ์ •๋ ฌ(Quick Sort)

๊ธฐ์ค€ ๋ฐ์ดํ„ฐ๋ฅผ ์„ค์ •ํ•˜๊ณ , ๊ทธ ๊ธฐ์ค€๋ณด๋‹ค ํฐ ๋ฐ์ดํ„ฐ์™€ ์ž‘์€ ๋ฐ์ดํ„ฐ์˜ ์œ„์น˜๋ฅผ ๋ฐ”๊พผ๋‹ค.

  • ํ”ผ๋ฒ—(Pivot): ๊ธฐ์ค€ ๋ฐ์ดํ„ฐ

→ ํ‰๊ท  ์‹œ๊ฐ„ ๋ณต์žก๋„: O(NlogN)

 

๊ณ„์ˆ˜ ์ •๋ ฌ(Count Sort)

  • ๊ฐ€์žฅ ์ž‘์€ ๋ฐ์ดํ„ฐ๋ถ€ํ„ฐ ๊ฐ€์žฅ ํฐ ๋ฐ์ดํ„ฐ๊นŒ์ง€ ๋ชจ๋‘ ๋‹ด๊ธธ ์ˆ˜ ์žˆ๋Š”  ๋ฐฐ์—ด(๋ฆฌ์ŠคํŠธ)์„ ์„ ์–ธํ•œ๋‹ค.
  • ๋ฐ์ดํ„ฐ๋ฅผ ํ•˜๋‚˜์”ฉ ํ™•์ธํ•˜์—ฌ ๋ฐ์ดํ„ฐ์˜ ๊ฐ’๊ณผ ๋™์ผํ•œ ์ธ๋ฑ์Šค์˜ ๋ฐฐ์—ด ๊ฐ’์„ 1์”ฉ ์ฆ๊ฐ€์‹œํ‚จ๋‹ค.
  • ๋ฐฐ์—ด์—๋Š” ๊ฐ ๋ฐ์ดํ„ฐ๊ฐ€ ๋ช‡ ๋ฒˆ ๋“ฑ์žฅํ–ˆ๋Š”์ง€ ํšŸ์ˆ˜๊ฐ€ ๊ธฐ๋ก๋˜๊ณ  ๊ทธ ๊ฐ’๋งŒํผ ์ธ๋ฑ์Šค๋ฅผ ์ˆœ์ฐจ์ ์œผ๋กœ ์ถœ๋ ฅํ•œ๋‹ค.

๋ฐ์ดํ„ฐ์˜ ํฌ๊ธฐ ๋ฒ”์œ„๊ฐ€ ์ œํ•œ๋˜์–ด ์ •์ˆ˜ ํ˜•ํƒœ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์„ ๋•Œ๋งŒ ์‚ฌ์šฉ ๊ฐ€๋Šฅํ•˜๋‹ค.

๋งค์šฐ ๋น ๋ฅธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜

→ ์‹œ๊ฐ„ ๋ณต์žก๋„: O(N+K)

 

 


์ •๋ ฌ ๋ฌธ์ œ

์œ„์—์„œ ์•„๋ž˜๋กœ

ํ•˜๋‚˜์˜ ์ˆ˜์—ด์—๋Š” ๋‹ค์–‘ํ•œ ์ˆ˜๊ฐ€ ์กด์žฌํ•œ๋‹ค. ์ด๋Ÿฌํ•œ ์ˆ˜๋Š” ํฌ๊ธฐ์— ์ƒ๊ด€์—†์ด ๋‚˜์—ด๋˜์–ด ์žˆ๋‹ค.
์ด ์ˆ˜๋ฅผ ํฐ ์ˆ˜๋ถ€ํ„ฐ ์ž‘์€ ์ˆ˜์˜ ์ˆœ์„œ๋กœ ์ •๋ ฌํ•ด์•ผ ํ•œ๋‹ค. ์ˆ˜์—ด์„ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.
var n = Int(readLine()!)!
var arr = [Int]()

for _ in 0..<n{
    arr.append(Int(readLine()!)!)
}

print(arr.sorted(by: >))

์„ฑ์ ์ด ๋‚ฎ์€ ์ˆœ์„œ๋กœ ํ•™์ƒ ์ถœ๋ ฅ

N๋ช…์˜ ํ•™์ƒ ์ •๋ณด๊ฐ€ ์žˆ๋‹ค. ํ•™์ƒ ์ •๋ณด๋Š” ํ•™์ƒ์˜ ์ด๋ฆ„๊ณผ ํ•™์ƒ์˜ ์„ฑ์ ์œผ๋กœ ๊ตฌ๋ถ„๋œ๋‹ค. 
๊ฐ ํ•™์ƒ์˜ ์ด๋ฆ„๊ณผ ์„ฑ์  ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ ์„ฑ์ ์ด ๋‚ฎ์€ ์ˆœ์„œ๋Œ€๋กœ ํ•™์ƒ์˜ ์ด๋ฆ„์„ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.
var n = Int(readLine()!)!
var arr = [(String,Int)]()

for _ in 0..<n{
    let input_data = readLine()!.split(separator: " ").map{String($0)}
    arr.append((input_data[0],Int(input_data[1])!))
}

print(arr.sorted(by: { first, second in first.1 < second.1}).map{$0.0})

๋‘ ๋ฐฐ์—ด์˜ ์›์†Œ ๊ต์ฑ„

๋™๋นˆ์ด๋Š” ๋‘ ๊ฐœ์˜ ๋ฐฐ์—ด A์™€ B๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๋‘ ๋ฐฐ์—ด์€ N๊ฐœ์˜ ์›์†Œ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ์œผ๋ฉฐ, ์›์†Œ๋Š” ๋ชจ๋‘ ์ž์—ฐ์ˆ˜์ด๋‹ค.
๋™๋นˆ์ด๋Š” ์ตœ๋Œ€ K๋ฒˆ์˜ ๋ฐ”๊ฟ”์น˜๊ธฐ ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ,
๋ฐ”๊ฟ”์น˜๊ธฐ ์—ฐ์‚ฐ์ด๋ž€ ๋ฐฐ์—ด A์— ์žˆ๋Š” ์›์†Œ ํ•˜๋‚˜์™€ ๋ฐฐ์—ด B์— ์žˆ๋Š” ์›์†Œ ํ•˜๋‚˜๋ฅผ ๊ณจ๋ผ์„œ ๋‘ ์›์†Œ๋ฅผ ์„œ๋กœ ๋ฐ”๊พธ๋Š” ๊ฒƒ์ด๋‹ค. 
๋™๋นˆ์ด์˜ ์ตœ์ข… ๋ชฉํ‘œ๋Š” ๋ฐฐ์—ด A์˜ ๋ชจ๋“  ์›์†Œ์˜ ํ•ฉ์ด ์ตœ๋Œ€๊ฐ€ ๋˜๋„๋ก ํ•˜๋Š” ๊ฒƒ์ด๋‹ค.
var inputdata = readLine()!.split(separator: " ").map{Int(String($0))!}
var n = inputdata[0], k = inputdata[1]

var arr_A = readLine()!.split(separator: " ").map{Int(String($0))!}
var arr_B = readLine()!.split(separator: " ").map{Int(String($0))!}

arr_A = arr_A.sorted()
arr_B = arr_B.sorted(by: >)

for i in 0..<k{
    if arr_A[i] < arr_B[i]{
        swap(&arr_A[i], &arr_B[i]) 
    }
    else {break}
}
print(arr_A.reduce(0, +))
๋ฐ˜์‘ํ˜•