코딩 테스트 - 04. Sort (Python3)
선택 정렬
- 가장 작은 것을 선택해서 앞으로 보내는 과정을 더 이상 반복할 수 없을 때까지 반복하는 정렬
- 가장 작은 데이터를 앞으로 보내는 과정을 N - 1번 반복하면 정렬이 완료
- 시간 복잡도 : (N**2 + N ) / 2 => O(N**2)
| 데이터의 개수 (N) | 선택 정렬 | 퀵 정렬 | 기본 정렬 라이브러리 |
|---|---|---|---|
| N=100 | 0.0123초 | 0.00156초 | 0.00000753초 |
| N=1,000 | 0.354초 | 0.00343초 | 0.0000365초 |
| N=10,000 | 15.475초 | 0.0312초 | 0.000248초 |
- 위 표에서 알 수 있듯이 다른 정렬 알고리즘에 비해서 매우 비효율적
- 하지만 특정 리스트에서 가장 작은 데이터를 찾는 경우 활용하기 좋다
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index=j
array[i], array[min_index] = array[min_index], array[i] # 스와프
print(array)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
스와프 코드
- 두 변수의 위치를 변경하는 코드
- 파이썬에선 간단하게 구현 가능
# 파이썬
array = [3, 5]
array[0], array[1] = array[1], array[0]
# 다른 언어
a = array[0] # 5
b = array[1] # 3
print(a, b)
temp = a
a = b
b = temp
print(a, b)
5 3
3 5
삽입 정렬
- 특정한 데이터를 적절한 위치에 삽입하여 정렬
- 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정
- 단계별로 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다
- 즉, 특정한 데이터보다 왼쪽에 있는 데이터들은 이미 정렬된 상태
=> 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요가 없이 그 자리에 삽입
- 즉, 특정한 데이터보다 왼쪽에 있는 데이터들은 이미 정렬된 상태
- 데이터가 거의 정렬되어 있을 때 매우 효율적 => 이 경우, 퀵 정렬보다 더 강력함
- 시간 복잡도 : O(N**2) (단, 최선의 경우 O(N))
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1): # 인덱스를 감소해가며 정렬함
if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1], array[j]
else: # 자신보다 작은 데이터를 만나면 반복 종료
break
print(array)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
퀵 정렬
- 가장 많이 사용되는 알고리즘
- 병합 정렬만큼 빠름
- 대부분의 프로그래밍 언어 정렬 라이브러리의 근간이 되는 알고리즘
- 기준을 선정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작
- 이때 기준을 ‘피벗‘이라고 하며, 피벗을 설정하는 방식에 따라 퀵 정렬을 구분
- 여기선 리스트에서 첫 번째 데이터를 피벗으로 설정하는 호어 분할 방식을 사용함
- 1차적으로 분할이 완료되면 피벗의 왼쪽엔 피벗보다 작은 데이터가, 오른쪽엔 큰 데이터가 위치한다 => 파티션
- 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트 각각에 피벗을 설정하여 동일한 방식으로 정렬을 수행한다
- 재귀 함수 형태로 작성하면 구현이 매우 간결해짐
- 종료 조건 : 현재 리스트의 데이터 개수가 1개인 경우
- 시간 복잡도 : O(NlongN)
- 선택 정렬, 삽입 정렬에 비해 매우 빠른 알고리즘
- 단, 최악의 경우 시간 복잡도는 O(N*2) => 이미 정렬되어 있는 경우
가장 널리 사용되고 있는 직관적인 형태의 퀵 정렬 소스코드
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
# 원소가 1개인 경우 종료
if start >= end:
return
#피벗은 첫 번째 원소로 설정 (호어 분할 방식)
pivot = start
# 피벗을 제외하고 맨 왼쪽 요소와 오른쪽 끝 요소를 선택
left = start + 1
right = end
while left <= right:
# 피벗보다 큰 데이터를 찾을 때까지 반복
while left <= end and array[left] <= array[pivot]:
left += 1
# 피벗보다 작은 데이터를 찾을 때까지 반복
while right > start and array[right] >= array[pivot]:
right -= 1
# 두 값이 엇갈리면 작은 데이터와 피벗을 교체
if left > right:
# right가 계속 작은 값을 찾아가므로 right가 작은 데이터
array[right], array[pivot] = array[pivot], array[right]
# 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
else:
array[left], array[right] = array[right], array[left]
# 분할 이후 왼쪽 리스트와 오른쪽 리스트에서 각각 정렬 수행 => 재귀적 호출
quick_sort(array, start, right-1)
quick_sort(array, right+1, end)
quick_sort(array, 0, len(array)-1)
print(array)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
파이썬의 장점을 살린 퀵 정렬 소스코드
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort_py(array):
# 리스트가 하나 이하의 원소만을 담도 있다면 종료
if len(array) <= 1:
return array
pivot = array[0]
# 피벗을 제외한 리스트
tail = array[1:]
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트 반환
return quick_sort_py(left_side) + [pivot] + quick_sort_py(right_side)
print(quick_sort_py(array))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
계수 정렬
- 특정 조건이 부합할 때만 사용할 수 있으나 매우 빠른 정렬 알고리즘
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능
- 가장 큰 데이터 - 가장 작은 데이터 < 1000000 일 때 효과적
- 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문
- 시간 복잡도 : O(N + K)
- N : 데이터의 개수, K : 최댓값의 크기
- 동일한 값을 가지는 데이터가 여러개 등장할 때 적합 => 데이터의 특성을 파악하기 쉬워야함
- 공간 복잡도 : O(N + K)
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1) # max값보다 1만큼 커야 max값에 해당하는 인덱스까지 담을 수 있음
for i in range(len(array)):
# 각 데이터에 해당하는 인덱스의 값 증가
count[array[i]] += 1
#리스트에 기록된 정렬 정보 확인
for i in range(len(count)):
for j in range(count[i]):
print(i, end= ' ')
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
파이썬 기본 정렬 라이브러리
- 병합 정렬 + 삽입 정렬 => 하이브리드 방식
- 퀵 정렬보다 느리지만 최악의 경우에도 O(NlogN)을 보장
- sorted()
- 리스트, 딕셔너리 자료형을 입력받아서 정렬된 결과를 출력 => return 값이 존재
- sort()
- 리스트 객체의 내장 함수
- 정렬된 리스트가 반환되는 것이 아니라 리스트 자체 내부 원소가 바로 정렬됨
- 위 두 함수 모두 reverse, key 매개변수를 입력받을 수 있음
- key : 하나의 함수가 들어가야 하며, 이는 정렬의 기준이 됨
- reverse : 내림차순 정렬 (default : False)
sorted()
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
result = sorted(array)
print(result)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sort()
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
array.sort()
print(array)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
key parameter 활용
array = [('바나나', 2), ('사과', 5), ('당근', 3)]
def setting(data):
return data[1]
# 여기서 data = array, tuple[1] => 2, 5, 3 이므로 이 숫자를 기준으로 정렬한 값을 출력
result = sorted(array, key=setting)
print(result)
[('바나나', 2), ('당근', 3), ('사과', 5)]
문제
1. 위에서 아래로
- 수열을 내림차순으로 정렬하는 프로그램을 작성
n = int(input())
list_ = []
for i in range(n):
list_.append(int(input()))
list_.sort(reverse=True)
for i in list_:
print(i, end= ' ')
3
15
27
12
27 15 12
2. 성적이 낮은 순서로 학생 출력하기
- 학생의 이름과 학생의 성적을 입력 받고 성적이 낮은 순서대로 이름을 출력하는 프로그램 작성
n = int(input())
student_list = []
for i in range(n):
st = input().split()
student_list.append([st[0], int(st[1])])
# key를 이용하여 2번째 인덱스인 점수를 기준으로 정렬
student_list.sort(key = lambda s : (s[1], s[0]))
for s in student_list:
print(s[0], end = ' ')
3
박박박 92
김김김 93
크크크 23
크크크 박박박 김김김
3. 두 배열의 원소 교체
- n개의 요소로 구성된 두 배열 A, B를 K번 원소들을 바꿔치기 연산해서 A의 원소 합의 최댓값을 출력
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# a의 원소가 최대가 되게 바꿔치기를 하려면 a는 오름차순, b는 내림차순 정렬한 후
# k번 만큼 앞에서부터 원소를 바꿔주면 된다
a.sort()
b.sort(reverse=True)
for i in range(k):
if a[i] < b[i]:
a[i], b[i] = b[i], a[i]
else:
# a, b 모두 정렬을 했기 때문에 a[i] > b[i]이면 a[i+1] > b[i+1]이기 때문에 이후의 반복을 하지 않는다
break
print(sum(a))
5 3
1 2 5 4 3
5 5 6 6 5
26
댓글남기기