정렬 알고리즘 개요
💡이전에 적었던 정렬 알고리즘 글입니다┏ (゜ω゜)=☞
이번 글은 파이썬 코드 위주로 적을 것
정렬 알고리즘 개념, 장점, 단점 요약글
아래의 코드는 오름차순 정렬을 기준으로 작성했다.
내림차순 정렬은 오름차순 정렬을 수행하는 알고리즘을 반대로 수행하면 된다. 또한 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드를 제공한다. 리스트를 뒤집는 연산은 O(N)의 시간복잡도를 가진다.
✨선택 정렬
입력 중 최솟값을 찾아 맨 앞에 있는 데이터와 바꾸고 그 다음으로 작은 값을 찾아 두 번째 데이터와 바꾸는 과정을 반복
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(arr)):
min_index = i #가장 작은 원소의 인덱스
for j in range(i + 1, len(arr)):
if arr[min_index] > arr[j]: #더 작은 원소 발견 시
min_index = j #j를 최솟값 인덱스로
arr[i], arr[min_index] = arr[min_index], arr[i] #swap
print(arr)👉 가장 작은 데이터를 앞으로 보내는 과정을 n-1번 반복하면 정렬이 완료
✨삽입 정렬
정렬된 부분과 정렬되지 않은 부분을 나누어 본다. 특정한 데이터가 정렬된 부분 중 적절한 위치를 찾는 과정을 반복.
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(arr)):
for j in range(i, 0, -1):
if arr[j] < arr[j - 1]: #정렬된 리스트에서 왼쪽으로 이동
arr[j], arr[j - 1] = arr[j - 1], arr[j] #swap = 왼쪽 이동
else: #본인 자리에서 멈추기
break
print(arr)👉 이미 정렬된 상태의 리스트 안에서 데이터가 이동하므로 자기보다 작은 데이터를 만난다면 더이상 이동할 필요가 없으므로 그 자리에 삽입
✨퀵 정렬
기준값인 피벗을 설정한 후 큰 수와 작은 수를 비교 교환한 후 리스트를 반으로 나누는 즉 정렬 -> 나누기 -> 정렬 -> 나누기 과정을 반복하는 알고리즘이다. 병합정렬과 달리 추가적인 임시 리스트를 필요로 하지 않는다.
퀵 정렬 소스코드 1_비교 교환 횟수 중점
arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(arr, start, end):
if start >= end: # 원소가 1개인 경우 리턴(재귀 함수 종료 조건)
return arr
pivot = start
left = start + 1
right = end
while left <= right:
# 피벗보다 큰 값을 찾을 때까지
while left <= end and arr[left] <= arr[pivot]:
left += 1 # left 이동
# 피벗보다 작은 값을 찾을 때까지
while right > start and arr[right] >= arr[pivot]:
right -= 1 # right 이동
if left > right: # 엇갈렸다면 작은 값을 피벗과 교체
arr[right], arr[pivot] = arr[pivot], arr[right]
else: # 엇갈리지 않았다면 큰 값과 작은 값 교체
arr[left], arr[right] = arr[right], arr[left]
# 분할 이후 재귀 호출로 피벗 기준 왼, 오 리스트 정렬
quick_sort(arr, start, right - 1)
quick_sort(arr, right + 1, end)
quick_sort(arr, 0, len(arr) - 1)
print(arr)퀵 정렬 소스코드 2_파이썬의 장점을 살린 코드(직관적)
arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(arr):
if len(arr) <= 1: #원소가 하나 남았다면 리턴
return arr
pivot = arr[0] #피벗은 첫 번째 원소
tail = arr[1:] #피벗을 제외한 리스트
#조건에 맞게 나누며 정렬
left_side = [x for x in tail if x <= pivot] #분할된 왼쪽 부분 리스트
rigjt_side = [x for x in tail if x > pivot] #분할된 오른쪽 부분 리스트
# 재귀 호출
return quick_sort(left_side) + [pivot] + quick_sort(rigjt_side)
print(quick_sort(arr))👉 left, right 처럼 따로 인덱스 값을 이동하며 비교하지 않고 반복문을 이용하며 두 부분 리스트로 나눠 정렬
✨계수 정렬
#모든 원소는 0 혹은 양의 정수라고 가정
arr = [5, 7, 9, 0, 2, 5, 0, 3, 1, 6, 2, 4, 8, 8, 8, 6]
#모든 범위를 표현하는 리스트 선언(모든 값은 0으로 초기화)
cnt = [0] * (max(arr)+1) #0이 있을 수 있으므로 가장 큰 수+1
for i in range(len(arr)):
cnt[arr[i]] += 1 #각 데이터에 해당하는 인덱스 값 1 증가
for i in range(len(cnt)): #인덱스이 데이터 수 만큼 출력
for j in range(cnt[i]):
print(i, end='')👉 계수 정렬은 0, 999999 두 수만 있는 경우 심각한 비효율성을 초래한다. 즉 항상 사용할 수 있는 정렬 방법은 아니고 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.
데이터의 크기가 한정, 데이터가 많이 중복인 상태일수록 유리
실전 문제
💻 위에서 아래로
n = int(input())
num_list = []
for _ in range(n):
num_list.append(int(input()))
num_list.sort(reverse=True)
for i in num_list:
print(i, end=' ')파이썬 기본 정렬 라이브러리를 사용
💻 성적이 낮은 순서로 학생 출력하기
n = int(input())
arr = []
for _ in range(n):
input_data = input().split() #이름, 점수 입력 받기
arr.append(input_data[0], int(input_data[1])) #점수 데이터 형 변환
arr = sorted(arr, key=lambda student: student[1]) #key(점수) 기준으로 정렬
for student in arr: #이름 출력
print(student[0], end=' ')👉 학생 정보를 (이름, 점수)로 묶은 뒤 점수 데이터를 key로 오름차순 정렬
💻 두 배열의 원소 교체
n, k = map(int(input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort() #오름차순 정렬
b.sort(reverse=True) #내림차순 정렬
for i in range(k):
if[i] < b[i]: #b가 더 크다면 교환
a[i], b[i] = b[i], a[i]
else: #a의 원소가 더 크거나 같다면 탈출
break
print(sum(a)) #a의 합 출력👉a, b를 가각 오름차순, 내림차순으로 정렬하고 조건에 맞다면 k번 교환
