TIL/Python
[TIL] 퀵 정렬 Quick Sort 추가 공부
아람2
2024. 9. 9. 20:41
반응형
09/10 TUE 퀴즈를 대비한 퀵 정렬 추가 공부
퀵 정렬 Quick Sort
분할 정복 알고리즘의 대표 예시
Pivot 값을 중심으로 작은 값/ 큰 값을 계속 나누기 때문에 재귀 함수임
방식
1) 르모토 - 월 같은 걸 추가한다 (이건 나중에 추가 공부하고 해주신대)
2) 호어 Hoare - Pivot 으로 판단한다 << DO IT 책에 있는 내용
(Left + Right) // 2 를 Pivot 으로 설정하고,
Pivot 기준으로 왼쪽은 작은 값, 오른쪽 큰 값 비교하여 서로 반대인 경우 Swap
첫번째 비교가 완료되면 Pivot 기준 왼쪽/ 오른쪽으로 또 쪼개서 Pivot 만들어
정렬을 완료한다
+ Pivot 을 arr[0] 에 줘도 되고, 어디에 주던 본인 마음임
+ while 문 안에서 Pivot 의 위치는 바뀔 수 있지만 Pivot 자체는 바뀌지 않음
* Mutable Sequence
- Mutable ; 변경 가능한 (<-> Immutable 변경 불가한)
- Sequence ; 요소를 수정 가능한 자료형 (List, Tuple, Range, String 등)
Quick Sort 를 Python 으로 구현해 보기!
1번 방법 DO IT 알고리즘입문 CH06
준비 과정
# Quick Sort - 분할 정복 알고리즘의 대표적인 예시
# (left+right)//2 로 Pivot 을 설정하고
# pl+1, pr-1 을 Pivot 과 비교하여 정렬한다
# QuickSort 함수에 array 와 left, right 설정
# pivot 을 설정하고, left 부터 pivot 까지/ right 부터 Pivot 까지 비교한다
# pl 이 x 보다 작은 경우 pl+1 하며 찾고 pr 이 x 보다 큰 경우 pr-1 하며 찾다가 멈추면 pl 과 pr 을 변경해 준다
# Pivot 을 기준으로 정렬이 완료되면 왼쪽/ 오른쪽 나눠서 또 진행
# 만약 Pivot 의 위치가 변경될 경우 Pivot 의 위치는 바뀌지만 Pivot 은 그대로
# MutableSequence 변경 가능한 시퀀스 (요소 수정 가능)
# Sequence ; List, Tuple, Range, String, etc
Qsort 함수
def qSort(a: MutableSequence, left: int, right: int) -> None:
pl = left # 제일 왼쪽의 요소
pr = right # 제일 오른쪽의 요소
x = a[(left+right)//2] # Pivot 설정
# pl 이 pr 보다 작을 때 while 문이 돌아간다
while pl <= pr:
# pl 이 가리키는 값이 Pivot 보다 작을 때 pl 을 뒤로 한 칸
while a[pl] < x: pl += 1
# pr 이 가리키는 값이 Pivot 보다 클 때 pr 을 앞으로 한 칸
while a[pr] > x: pr -= 1
# pl 과 pr 의 움직임이 멈추고 pl 이 pr 보다 앞에 있을 때
# pl 이 가리키는 값과 pr 이 가리키는 값을 swap 하고
# pl 뒤로 한 칸, pr 앞으로 한 칸 옮겨준다
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
# pl 이 pr 보다 작은 경우 다시 while 문을 돈다
# pl 이 pr 보다 큰 경우 while 문을 종료하고
# left < pr/ pl < right 의 조건을 충족할 때
# 기존 Pivot 기준으로 앞부분과 뒷부분으로 나눠 다시 qSort 진행
if left < pr: qSort(a, left, pr)
if pl < right: qSort(a, pl, right)
Quick_Sort 함수
# MutableSequence 는 리스트와 같이 변경 가능한 시퀀스를 나타내는 타입 힌트
# qSort 라는 재귀적 함수를 호출하여 리스트 a 를 정렬
# 리스트 a, 정렬을 시작할 인덱스 0, 끝 인덱스 len(a)-1 를 인자로 전달
def Quick_Sort(a: MutableSequence) -> None:
qSort(a, 0, len(a)-1)
Main
if __name__ == '__main__':
print(" 배열 입력 받기 ")
num = int(input())
x = [None] * num # 배열 개수 입력 받고 None 으로 초기화하기
for i in range(num): # 배열 하나씩 입력 받기
x[i] = int(input(f'[x{i}]: '))
Quick_Sort(x) # Quick Sort 진행
print(" 정렬 완료 ")
for i in range(num): # 정렬 완료 후 차례로 Print
print(f'[x{i}]: = {x[i]}')
전체 코드
from typing import MutableSequence
def qSort(a: MutableSequence, left: int, right: int) -> None:
pl = left # 제일 왼쪽의 요소
pr = right # 제일 오른쪽의 요소
x = a[(left+right)//2] # Pivot 설정
# pl 이 pr 보다 작을 때 while 문이 돌아간다
while pl <= pr:
# pl 이 가리키는 값이 Pivot 보다 작을 때 pl 을 뒤로 한 칸
while a[pl] < x: pl += 1
# pr 이 가리키는 값이 Pivot 보다 클 때 pr 을 뒤로 한 칸
while a[pr] > x: pr -= 1
# pl 과 pr 의 움직임이 멈추고 pl 이 pr 보다 앞에 있을 때
# pl 이 가리키는 값과 pr 이 가리키는 값을 swap 하고
# pl 뒤로 한 칸, pr 앞으로 한 칸 옮겨준다
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
# pl 이 pr 보다 작은 경우 다시 while 문을 돈다
# pl 이 pr 보다 큰 경우 while 문을 종료하고
# left < pr/ pl < right 의 조건을 충족할 때
# 기존 Pivot 기준으로 앞부분과 뒷부분으로 나눠 다시 qSort 진행
if left < pr: qSort(a, left, pr)
if pl < right: qSort(a, pl, right)
def Quick_Sort(a: MutableSequence) -> None:
qSort(a, 0, len(a)-1)
if __name__ == '__main__':
print(" 배열 입력 받기 ")
num = int(input())
x = [None] * num # 배열 개수 입력 받고 None 으로 초기화하기
for i in range(num): # 배열 하나씩 엔터로 입력 받기
x[i] = int(input(f'[x{i}]: '))
Quick_Sort(x) # Quick Sort 진행
print(" 정렬 완료 ")
for i in range(num): # 정렬 완료 후 차례로 Print
print(f'[x{i}]: = {x[i]}')
정렬 결과
배열 입력 받기
5
[x0]: 3
[x1]: 2
[x2]: 4
[x3]: 5
[x4]: 1
정렬 완료
[x0]: = 1
[x1]: = 2
[x2]: = 3
[x3]: = 4
[x4]: = 5
2번 방법은 1번을 함수 하나만 사용하기 + 한 줄로 입출력
from typing import MutableSequence
def qSort(a: MutableSequence, left: int, right: int) -> None:
if left >= right: # 재귀 종료 조건
return
pl = left
pr = right
x = a[(left+right)//2] # Pivot 설정
while pl <= pr:
while a[pl] < x: pl += 1
while a[pr] > x: pr -= 1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl] # pl pr Swap
pl += 1
pr -= 1
if left < pr: qSort(a, left, pr) # 왼쪽 부분 정렬
if pl < right: qSort(a, pl, right) # 오른쪽 부분 정렬
if __name__ == '__main__':
num = int(input()) # 입력할 숫자
arr = list(map(int, input().split())) # 숫자 배열 한 줄로 입력 받기
qSort(arr, 0, num-1) # Quick Sort 실행
print("정렬 완료", ' '.join(map(str, arr))) # 숫자 배열 한 줄로 출력정렬 결과
4
3 2 4 6
정렬 완료 2 3 4 63번 방법 파이썬 컴프리헨션과 배열 이용하기1
qSort 부분
def qSort(a: MutableSequence) -> None:
# len(a) 가 1 이하인 경우 정렬 완료로 간주
if len(a) <= 1:
return a
# Pivot 을 맨 앞으로 선언
pivot = a[0]
# Pivot 을 제외한 a 에서 pivot 와 비교하여 작은 수는 less 에 넣기
less_than_pivot = [x for x in a[1:] if x <= pivot]
# Pivot 을 제외한 a 에서 pivot 과 비교하여 큰 수는 greater 에 넣기
greater_than_pivot = [x for x in a[1:] if x > pivot]
# 정렬한 less 와 greater, pivot 을 하나로 묶어서 return
# less 와 greater 가 각각 정렬이 끝날 때까지 재귀 실행
return qSort(less_than_pivot) + [pivot] + qSort(greater_than_pivot)
Main
if __name__ == '__main__':
# 공백으로 구분하여 문자열 입력 받기
num_list = list(map(int, input().split()))
sorted_list = qSort(num_list)
print(f" 정렬 완료 : {sorted_list}")
전체 코드
# Quick Search
from typing import MutableSequence
def qSort(a: MutableSequence) -> None:
# len(a) 가 1 이하인 경우 정렬 완료로 간주
if len(a) <= 1:
return a
# Pivot 을 맨 앞으로 선언
pivot = a[0]
# Pivot 을 제외한 a 에서 pivot 와 비교하여 작은 수는 less 에 넣기
less_than_pivot = [x for x in a[1:] if x <= pivot]
# Pivot 을 제외한 a 에서 pivot 과 비교하여 큰 수는 greater 에 넣기
greater_than_pivot = [x for x in a[1:] if x > pivot]
# 정렬한 less 와 greater, pivot 을 하나로 묶어서 return
# less 와 greater 가 각각 정렬이 끝날 때까지 재귀 실행
return qSort(less_than_pivot) + [pivot] + qSort(greater_than_pivot)
if __name__ == '__main__':
# 공백으로 구분하여 문자열 입력 받기
num_list = list(map(int, input().split()))
sorted_list = qSort(num_list)
print(f" 정렬 완료 : {sorted_list}")
4번 방법 파이썬 컴프리헨션과 배열 이용하기2
def quick_sort(arr):
if len(arr) <= 1: # 배열의 길이가 1 이하인 경우 종료
return arr
pivot = arr[len(arr) // 2] # 피벗 선택 (중간 값)
left = [x for x in arr if x < pivot] # 피벗보다 작은 값들
middle = [x for x in arr if x == pivot] # 피벗과 같은 값들
right = [x for x in arr if x > pivot] # 피벗보다 큰 값들
return quick_sort(left) + middle + quick_sort(right) # 재귀적으로 호출하여 병합
반응형