정렬
- 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
- 정렬 알고리즘으로 정렬 시 이진 탐색이 가능
- 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬
선택 정렬
- 맨 앞의 데이터와 나머지 데이터 비교해서 작은 것을 맨앞으로 교체 반복, 그 다음 데이터들도 같은 작업 반복
- 가장 원시적
- O(N^2) , 2중 반복문으로 탐색 시 대략 O(N^2)
삽입 정렬
- 첫 원소는 정렬되었다고 판단하고 그 다음 원소부터 검사, 정렬된 원소들과 비교해서 위치를 찾아 삽입
- 중간과정에도 정렬 되어있음
- O(N^2), 2중 반복문
- BEST CASE 에서는 O(N)
퀵 정렬
- 기준 데이터(피벗)를 정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸자
- 1. 첫번째 데이터가 피봇, 피봇 제외하고 왼쪽부터 피벗보다 큰 값 찾고 오른쪽부터 피봇보다 작은 값 찾아서 위치 바꿈
- 2. 큰 값과 작은 값이 엇갈리면 피봇과 작은 값의 위치를 바꿈
- 3. 그 피봇을 중심으로 분할해서 왼쪽 부분과 오른쪽 부분을 1,2 과정 반복 (이진트리처럼 계속 갈라지듯이)
- 가장 많이 사용됨
- O(NlogN)
- WORST CASE 에서는 O(N^2)
계수 정렬
- 선택 정렬, 삽입 정렬, 퀵 정렬 같이 데이터를 비교하며 위치를 변경하는 정렬 알고리즘이 아님
- 데이터의 크기가 제한되어 정수 형태로 표현할 수 있는 경우에만 사용 가능
- ex) 0~9까지 데이터가 있는 경우 크기 10의 리스트 생성, 각 인덱스에 해당하는 값이 몇개있는지 리스트에 등록하여 인덱스 순서대로 리스트값만큼 인덱스 출력
- 시간복잡도, 공간복잡도 : O(N+K) (K : 데이터 중 최대값의 크기)
- 가장 작은 데이터와 큰 데이터의 차이가 1,000,000 이하일때 효과적이다.
파이썬 sorted()
- WORST CASE 에서도 O(NlogN)
- 직접 퀵정렬 구현하는 것 보다 좋음
코딩테스트에서 직접 정렬 알고리즘을 구현하는 경우
- 정렬 알고리즘의 원리에 대해서 물어보는 문제
- 더 빠른 정렬이 필요한 문제 : 계수 정렬 등 다른 정렬 알고리즘을 이용하거나 기존 알고리즘의 구조적인 개선을 거쳐 풀어야함
문제 2 : 성적이 낮은 순서로 학생 출력하기
N = int(input())
data = []
for i in range(N):
name, score = input().split()
data.append((name, int(score)))
data = sorted(data, key= lambda x: x[1])
for i in data:
print(i[0],end=' ')
문제 3 : 두 배열의 원소 교체
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
for i in range(K):
A = sorted(A)
B = sorted(B)
if A[0] < B[-1]:
A[0],B[-1] = B[-1], A[0]
print(sum(A))이렇게 풀면 데이터 수가 많아질 경우 굉장히 비효율적일 수 있음
책에서는 정렬은 한번만 하고 원소간 크기 비교하여 더 이상 교체해도 B의 원소가 A원소보다 커질 수 없을 때 break 로 나머지 루프 안돌고 경제적으로 종료시킴