[알고리즘] 정렬(Sorting)

정렬(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, +))