정렬

정렬이란?

- 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
- 공식처럼 사용 (이진 탐색의 전처리 과정 등)

선택 : O(N^2), 거의 사용 X
삽입 : O(N) ~ O(N^2), 정렬이 거의 된 경우 가장 빠름
퀵 :  O(NlogN) ~ O(N^2), 이미 정렬이 된 최악의 경우가 N^2
계수 : O(N+K), N: 개수 K: 최대값
파이썬 기본 정렬 라이브러리: O(NlogN) 보장

 

1. 단순히 정렬 기법을 아는지 묻는 문제 (정렬 라이브러리 사용 시 가능)

2. 정렬 알고리즘의 원리를 묻는 문제 

3. 빠른 알고리즘이 필요한 문제 (기존의 알고리즘에 구조적인 개선을 거쳐야함)

 

tip. 별도의 요구사항이 있는 경우(데이터 한정, 동작 시간 단축), 계수 정렬 사용이 유리

---

1. ex) 위에서 아래로

    입력
        N (1 ≤ 공포도≤ N) 수열에 속해있는 수의 개수 
        N개의 수 ↓ (1 ≤ 자연수≤ 100,000) 

    출력
        주어진 수열이 내림차순으로 정렬된 결과(공백으로 구분)

    모든 수의 개수가 500개 이하로 적음, 기본 정렬 라이브러리 사용 가능

n = int(input())

array = [int(input()) for i in range(n)]
array.sort(reverse = True)

for a in array:
    print(a, end = ' ')

 

2. ex) 성적이 낮은 순서로 학생 출력하기

    입력
        N (1 ≤ N≤ 100,000) 학생 수
        이름, 학생 성적 N줄 (1 ≤이름 길이, 성적≤ 100)  공백으로 구분

    출력
        성적이 낮은 순으로 학생 이름 출력

    모든 수의 개수가 100,000개, O(NlogN)을 보장하는 알고리즘이나 O(N) 계수정렬 사용 가능

n = int(input())
grade = [input().split() for _ in range(n)]

grade.sort(key = lambda x: (int(x[1])))

for name in grade:
    print(name[0])

 

3. ex) 두 배열의 원소 교체

    입력
        N, K (1 ≤ N≤ 100,000)(0 ≤ K ≤ N) 공백으로 구분
        배열 A의 원소 N개 (1 ≤ 원소 ≤ 10,000,000)  공백으로 구분
        배열 B의 원소 N개 (1≤ 원소 ≤ 10,000,000) 공백으로 구분

    출력
        최대 K번 배열 B의 원소와 바꿔 만들 수 있는 배열 A의 최대 총합

    K가 최대 100,000번, O(NlogN)을 보장하는 정렬 알고리즘 사용

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
a.sort(reverse=True)

for i in range(k):
    
    if a[i] < b[i]:
        a[i] = b[i]
    else:
        break
    
print(sum(a))

 

---

이것이 코딩 테스트다 - 나동빈
정리하긔