현재 중앙대학교 컴퓨터예술학부 재학중
들어가기 전) 배열 개념정리
정렬은 기본적으로 배열과 같은 데이터 구조를 가진다
배열은 순서가 있고 첨자(index)가 있다.
이 첨자를 통해서 각각의 데이터 원소에 접근하게 되고
그 데이터 원소를 키(key)로 여기고 정렬하게 된다.
첨자(index)가 어떻게 변하는지
비교연산자(<,>,≤,≥)는 무엇을 써야할지
오름차순 정렬을 원칙을 한다.
01_왜 퀵 정렬인가?
퀵 정렬(quick sort)은 찰스 앤터니 리처드 호어가 개발한
정렬 알고리즘이다.
이름에서 알 수 있듯이 일반적인 경우 퀵 정렬은
다른 O(n log n) 알고리즘에 비해 빠르게 동작한다.
이렇게 빠른 이유는 참조의 지역성에 의한 캐시 히트율이
높기 때문이다.
구체적으로는 퀵 소트의 동작방식이
한정적인 배열에서 피봇을 중심으로 데이터들이
움직여 정렬하는 것이기 때문이다.
02_퀵 정렬 알고리즘의 특징
- 피봇 위치에 따른 다양한 퀵소트 종류와 그 속도
의 속도를 보여줄 여지가 있다.- 불안정 정렬
정렬의 안정성은 정렬 전 같은 데이터를 가진 원소의 순서가 정렬 후에도 유지되는지 따지는 것이다.
유지되면 안정 정렬이고, 달라질 수 있다면 불안정 정렬이다.
- 재귀함수를 활용한 코드 (but 일반 for루프문에 비해 느린 속도)
03_퀵 정렬 알고리즘의 구현코드(Python)
def quick_sort(arr):
n=len(arr)
if n<=1:
return arr
else:
pivot=arr[0] # 피봇 선정 - 첫항으로 고정 (기준을 자유롭게 정할 수 있습니다)
less=[x for x in arr[1:] if x<=pivot]
greater=[x for x in arr[1:] if x>pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
arr=[5,9,4,3,7]
quick_sort(arr)개선의 필요성
재귀 호출 때마다 새로운 리스트를 생성하고 병합하기 때문에
메모리 소모량이 크고 병합에 필요한 연산이 요구된다.
즉, 시간 복잡도와 공간 복잡도가 높다.
-> 리스트를 생성하지 않는 코드를 작성한다.
from typing import Any, List
def partition(arr: List[Any], pl: int, pr: int) -> int:
pivot = arr[(pl+pr)//2]
print("pivot :", pivot)
while pl <= pr:
while arr[pl] < pivot:
pl += 1
while arr[pr] > pivot:
pr -= 1
if pl <= pr:
arr[pl], arr[pr] = arr[pr], arr[pl]
pl += 1
pr -= 1
return pl
def quick_sort(arr: List[Any], pl: int, pr: int) -> None:
if pr <= pl:
return
div = partition(arr, pl, pr)
quick_sort(arr, pl, div-1)
quick_sort(arr, div, pr)
arr = [6, 4, 8, 3, 1, 9, 7]
quick_sort(arr, 0, len(arr)-1)
print(arr)
쉽게 이해하기 시킬 방법을 여러가지 생각해봤지만
퀵 정렬은 코드를 보고 이해하는게 제일 정확하다고 느꼈다.
그래서 미안하지만 '쉽게'는 이해시키지 못할 것 같다...
대신에 그냥 과정을 전부 시각화해서 적었다.
복잡한 코드의 진행과정을 눈으로 이리저리 확인해 보길!
04_동작방식 쉽게 이해하기
(1) Line by Line (Python) : simple version
* 핵심 키워드 정리
피봇 - 기준이 되는 점
파티션 - 기준이 되는 피봇보다 작거나 같은 것(작은 것) 혹은 큰 것(크거나 같은 것) 들의 집합
분할 - 파티션이 만들어지는 과정
병합 - 분할된 파티션을 합치는 과정
간단한 버전은 재귀방식을 활용하기에 코드 읽기는 쉽지만
반복되는 재귀함수의 분할과정을 한번에 이해하는 것은
어려울 수 있기 때문에 간단한 재귀함수의 호출과정을
직접 손으로 따라 써보는 것을 사실상 추천한다.
아래의 구현코드와 함께 재귀함수의 호출과정을 살펴보자
def quick_sort(arr):
n=len(arr)
if n<=1: #종료 조건 : 배열의 크기가 1개이하 일 때
return arr
else:
pivot=arr[0] # 피봇 선정 - 첫항으로 고정
less=[x for x in arr[1:] if x<=pivot] # 파티션 less - 피봇 보다 작거나 같은 것 / arr[1:] - 피봇을 제외한 나머지 항
greater=[x for x in arr[1:] if x>pivot] # 파티션 greater - 피봇 보다 큰 것
return quick_sort(less) + [pivot] + quick_sort(greater) # 병합 : [less]+[pivot]+[greater]
arr=[5,9,4,3,7]
quick_sort(arr)[5,9,4,3,7]
그나마 정말 간단한 버전이라 굳이 시각화하지 않고
간단하게 집고 넘어가기만 하겠다.
1. 분할
pivot = [5]
less = [4,3]
greater = [9,7]
2. (less 분할)
pivot = [4]
less = [3]
greater = []
배열의 크기가 0~1개임으로 종료합니다.
=> [3]+[4]+[ ]
=> [3,4]
3. (greater 분할)
pivot = [9]
less = [7]
greater=[]
배열의 크기가 0~1개임으로 종료합니다.
=> [7]+[9]+[ ]
=> [7,9]
4. 병합
[3,4] + [5] + [7,9]
04_동작방식 쉽게 이해하기
(2) Line by Line (Python) : improved version
앞서 보여준 간단한 버전의 코드는 읽기 편하지만
새로운 리스트를 계속 생성하고 병합하기 때문에
메모리 소모량이 크고 병합에 필요한 연산이 요구된다.
따라서 이번엔 그러한 부분이 개선된 코드를 살펴보겠다.
이번에도 직접 손으로 따라 써보는 것을 사실상 추천한다.
from typing import Any, List
def partition(arr: List[Any], pl: int, pr: int) -> int:
pivot = arr[(pl+pr)//2] # pivot으로 중간값을 뽑습니다. // 산술 연산자는 몫을 도출합니다.
print("pivot :", pivot)
while pl <= pr: # 초기 pl,pr은 배열 맨 왼쪽, 맨 오른쪽에 위치
while arr[pl] < pivot: #pl이 pivot보다 크거나 같으면 멈춥니다.
pl += 1
while arr[pr] > pivot: #pr이 pivot보다 작거나 같으면 멈춥니다.
pr -= 1
if pl <= pr: # pl과 pr이 교차하지 않았다면 교환
arr[pl], arr[pr] = arr[pr], arr[pl]
pl += 1
pr -= 1
print("We found Pl is less than or equal to Pr and added 1 to pl\npl :", pl)
print("We found Pl is less than or equal to Pr and added 1 to pr\npr :", pr)
print("Swapped :",arr,"\n")
return pl
def quick_sort(arr: List[Any], pl: int, pr: int) -> None:
if pr <= pl:
return
div = partition(arr, pl, pr) # 1. partition(arr,0,6)
print("pl :",pl,"/ div :",div,"")
if pl==0 and div-1==1:
print("\n---------[Left terms of first split start quicksort]---------")
quick_sort(arr, pl, div-1)
# 2-1. div=partiton(arr,0,1)
# 2-2. quick_sort(arr,0,0) -> None
# 2-3. quick_sort(arr,0,-1) -> None
if div==2 and pr==6:
print("\n---------[Right terms of first split start quicksort]---------")
quick_sort(arr, div, pr)
# 3-1. div=partiton(arr,2,6)
# 3-2. quick_sort(arr,2,3)
# 3-2-1. div=partiton(arr,2,3)
# 3-2-2. quick_sort(arr,2,2) -> None
# 3-2-3. quick_sort(arr,3,3) -> None
# 3-3. quick_sort(arr,4,6)
# 3-3-1. div=partition(arr,4,6)
# 3-3-2. quick_sort(arr,4,5)
# 3-3-2-1. div=partiton(arr,4,5)
# 3-3-2-2. quick_sort(arr,4,4) -> None
# 3-3-2.3. quick_sort(arr,5,5) -> None
# 3-3-3. quick_sort(arr,6,6) -> None
arr = [6, 4, 8, 3, 1, 9, 7]
print("Before :",arr)
print("pl :",0,"/ pr :",len(arr)-1,"\n")
quick_sort(arr, 0, len(arr)-1)
print("After :",arr)
# 1. partition(arr,0,6)
arr[pl]과 pivot을 비교하여 pivot 보다 큰 값을 찾습니다.
arr[pl] > pivot 임으로 인덱스 0에 정지합니다.
arr[pr]과 pivot을 비교하여 pivot 보다 작은 값을 찾습니다.
pr이 인덱스 5와 6에서 arr[pr] > pivot 임으로 인덱스 4에서 정지합니다.
arr[pl]과 arr[pr]이 교차하지 않았으므로 교환합니다.
pl을 한 칸 오른쪽, pr을 한 칸 왼쪽 이동합니다.
arr[pl]과 pivot을 비교하여 pivot 보다 큰 값을 찾습니다.
arr[pl] > pivot 임으로 인덱스 1에서 정지합니다.
arr[pr]과 pivot을 비교하여 pivot 보다 작은 값을 찾습니다.
arr[pr] = pivot 임으로 인덱스 3에서 정지합니다. -----
arr[pl]과 arr[pr]이 교차하지 않았으므로 교환합니다.
pl을 한 칸 오른쪽, pr을 한 칸 왼쪽 이동합니다.
arr[pl]과 pivot을 비교하여 pivot 보다 큰 값을 찾습니다.
arr[pl] > pivot 임으로 인덱스 2에서 정지합니다.
arr[pr]과 pivot을 비교하여 pivot 보다 작은 값을 찾습니다.
arr[pr] > pivot 임으로 인덱스 1에서 정지합니다.
pl > pr 임으로 while문을 탈출하고 pl(div=2) 반환합니다.
# 2-1. div=partiton(arr,0,1)
arr[pl]과 pivot을 비교하여 pivot 보다 큰 값을 찾습니다.
arr[pl] = pivot 임으로 인덱스 0에서 정지합니다.
arr[pr]과 pivot을 비교하여 pivot 보다 작은 값을 찾습니다.
pr이 인덱스 1에서 arr[pr] > pivot 임으로 인덱스 0에서 정지합니다.
arr[pl]과 arr[pr]이 교차하지 않았으므로 교환합니다.
(제자리 교환으로 실질적인 교환은 이루어지지 않았다.)
pl을 한 칸 오른쪽, pr을 한 칸 왼쪽 이동합니다.
pl > pr 임으로 while문을 탈출하고 pl(div=1) 반환합니다.
# 2-2. quick_sort(arr,0,0)
다음 함수인 quick_sort(arr,0,0) 넘어갑니다.
pl ≥ pr 임으로 return 하여 끝냅니다.
# 2-3. quick_sort(arr,0,-1)
다음 함수인 quick_sort(arr,0,-1)로 넘어갑니다.
pl ≥ pr 임으로 return 하여 끝냅니다.
# 3-1. div=partiton(arr,2,6)
arr[pl]과 pivot을 비교하여 pivot 보다 큰 값을 찾습니다.
arr[pl] > pivot 임으로 인덱스0 에 정지합니다.
arr[pr]과 pivot을 비교하여 pivot 보다 작은 값을 찾습니다.
pr이 인덱스 5와 6에서 arr[pr] > pivot 임으로 인덱스 4에서 정지합니다.
arr[pl]과 arr[pr]이 교차하지 않았으므로 교환합니다.
pl을 한 칸 오른쪽, pr을 한 칸 왼쪽 이동합니다.
arr[pl]과 pivot을 비교하여 pivot 보다 큰 값을 찾습니다.
pr이 인덱스 3에서 arr[pl] < pivot 임으로 인덱스 4에 정지합니다.
arr[pr]과 pivot을 비교하여 pivot 보다 작은 값을 찾습니다.
arr[pr] < pivot 임으로 인덱스 4에 정지합니다.
pl > pr 임으로 while문을 탈출하고 pl(div=4) 반환합니다.
# 3-2-1. div=partiton(arr,2,3)
arr[pl]과 pivot을 비교하여 pivot 보다 큰 값을 찾습니다.
arr[pl] = pivot 임으로 인덱스 2에 정지합니다.
arr[pr]과 pivot을 비교하여 pivot 보다 작은 값을 찾습니다.
arr[pr] < pivot 임으로 인덱스 3에 정지합니다.
arr[pl]과 arr[pr]이 교차하지 않았으므로 교환합니다.
pl을 한 칸 오른쪽, pr을 한 칸 왼쪽 이동합니다.
pl > pr 임으로 while문을 탈출하고 pl(div=3) 반환합니다.
# 3-2-2. quick_sort(arr,2,2)
다음 함수인 quick_sort(arr,2,2) 넘어갑니다.
pr ≥ pl 임으로 return 하여 끝냅니다.
# 3-2-3. quick_sort(arr,3,3)
다음 함수인 quick_sort(arr,3,3) 넘어갑니다.
pr ≥ pl 임으로 return 하여 끝냅니다.
# 3-3-1. div=partition(arr,4,6)
arr[pl]과 pivot을 비교하여 pivot 보다 큰 값을 찾습니다.
pl이 인덱스4에서 arr[pl] < pivot 임으로 인덱스 5에 정지합니다.
arr[pr]과 pivot을 비교하여 pivot 보다 작은 값을 찾습니다.
arr[pr] > pivot 임으로 인덱스 6에 정지합니다.
arr[pl]과 arr[pr]이 교차하지 않았으므로 교환합니다.
pl을 한 칸 오른쪽, pr을 한 칸 왼쪽 이동합니다.
pl > pr 임으로 while문을 탈출하고 pl(div=6) 반환합니다.
# 3-3-2-1. div=partiton(arr,4,5)
arr[pl]과 pivot을 비교하여 pivot 보다 큰 값을 찾습니다.
arr[pl] = pivot 임으로 인덱스 4에 정지합니다.
arr[pr]과 pivot을 비교하여 pivot 보다 작은 값을 찾습니다.
arr[pr] > pivot 임으로 인덱스 5에 정지합니다.
arr[pl]과 arr[pr]이 교차하지 않았으므로 교환합니다.
pl을 한 칸 오른쪽, pr을 한 칸 왼쪽 이동합니다.
pl > pr 임으로 while문을 탈출하고 pl(div=5) 반환합니다.
# 3-3-2-2. quick_sort(arr,4,4)
다음 함수인 quick_sort(arr,4,4) 넘어갑니다.
pr ≥ pl 임으로 return 하여 끝냅니다.
# 3-3-2.3. quick_sort(arr,5,5)
다음 함수인 quick_sort(arr,5,5) 넘어갑니다.
pr ≥ pl 임으로 return 하여 끝냅니다.
# 3-3-3. quick_sort(arr,6,6)
다음 함수인 quick_sort(arr,6,6) 넘어갑니다.
pr ≥ pl 임으로 return 하여 끝냅니다.
05_퀵 정렬 알고리즘의 시간 복잡도
> 시간 복잡성에 대해 궁금하다면 ? 바로가기
Best:
Average :
Worst :
(1) 이상적인 경우
피봇을 기준으로 균등하게 분할이 되었을 때이다.
앞의 간단한 코드 버전를 다시 보면 분할 할 때,
for문이 들어간 list를 두 개 있는 것을 볼 수 있다.
따라서 분할 마다 
이러한 분할은 n개의 길이를 가진 배열의 경우
처음 분할되기 전 배열(초기 배열, 1)을 따로 제외하고 생각하면
2개의 가지치기를 이어서 반복하는 분할층(stack)이
수학의 가지치기를 생각하면 된다.
그렇게 한 층이 할당한 시간복잡도인
분할층(stack)의 개수인 
(점근적인 계산만 함으로 상수는 무시한다)
(2) 최악의 경우
분할 시 피봇을 선택할 때 마다
피봇보다 작은 것(큰 것)의 개수가 0~1개 인 경우이다.
즉, 한 쪽으로 데이터가 뭉쳐있는 경우를 말한다.
배열로 보았을 때, 역순으로 정렬되어 있는 경우
혹은 이미 정렬되어 있는 경우이다.
한 층이 할당한 시간복잡도인
분할층(stack)의 개수인 n을 곱하게 되면
(점근적인 계산만 함으로 상수는 무시한다)
보통 최악의 겨우는 극단적인 상황인지라
통계적으로 따졌을 때 평균적으로 이상적인 경우를 선호한다.
(구체적인 확률 통계론을 사용하면 이산 확률의 정규분포에 근사한다고 한다.)
결과적으로 보통
06_퀵 정렬 응용하기
프로세싱으로 데이터 시각화하기
프로세싱이란 MIT 미디어랩에서 개발한 오프소스 툴중 하나로
그래픽적인 요소를 쉽게 구현할 수 있다는 점에서 강점을 지니고 있다.
float[] values;
void swap(float[] arr, int a, int b) {
float temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
try{Thread.sleep(10);}catch(Exception e){}; //delay the thread operating this function
redraw();
}
int partition(float[] arr, int start, int end) {
int pivotIndex = start;
float pivotValue = arr[end];
for (int i =start; i < end; i++) {
if (arr[i] < pivotValue) {
swap(arr, i, pivotIndex++);
// pivotIndex++;
}
}
swap(arr, pivotIndex, end);
return pivotIndex;
}
void quickSort(float[] arr, int start, int end) {
if (start < end) {
int index = partition(arr, start, end);
quickSort(arr, start, index - 1);
quickSort(arr, index + 1, end);
}
}
//make a thread and override the run to perform the sort instead
Thread t = new Thread(){
public void run(){
quickSort(values, 0, values.length - 1);
}
};
void setup() {
size(800, 300);
values = new float[width];
for (int i = 0; i < values.length; i++) {
values[i] = random(0, height);
}
t.start(); //start the thread after array is populated
}
void draw() {
background(0);
for (int i = 0; i < values.length; i++) {
stroke(255);
line(i, height, i, height - values[i]);
}
//remove this quicksort call here bc its now done in the thread - in parralel to the sketch.
}참조문헌
"토니 호어." (2020년 5월 6일). 위키백과. 2020년 4월 26일 수정, https://ko.wikipedia.org/wiki/%ED%86%A0%EB%8B%88_%ED%98%B8%EC%96%B4.
"Quicksort visualization." (2020년 5월 4일). processing-foundation. 2019년 9월 수정, https://discourse.processing.org/t/quicksort-visualization/14120/3
"【알고리즘】 퀵 정렬 알고리즘 시간복잡도 증명." (2020년 5월 6일). 정빈이의 공부방. 2016년 8월 30일 수정, https://nate9389.tistory.com/130#footnote_link_130_1.
"[알고리즘] - 안정 정렬(Stable Sort)과 불안정 정렬(Unstable Sort) #2 ." (2020년 5월 6일). 졸지말고... 2019년 1월 9일 수정, https://godgod732.tistory.com/10.
'기술' 카테고리의 다른 글
| 빅오표기법 - 시간복잡도 (0) | 2020.05.04 |
|---|---|
| [알고리즘] 버블 정렬 (bubble sort) 쉽게 이해하기 (0) | 2020.05.03 |
| [가성비甲] 30만원대~70만원대 중저가형 가성비 노트북 추천★★★ (1) | 2018.03.03 |