정렬 방법론.
1. 분할.
1). 가장 오른쪽 값을 피봇으로 정한다.
2). l부터 시작하여 오른쪽으로 이동하며 피봇보다 큰 값을 가진 원소를 찾는다.
3). r-l부터 시작하여 왼쪽으로 이동하며 피봇보다 작은 값을 가진 원소를 찾는다.
4). i=l, j=r-l이 들어가게 되며 i가 j보다 커지면(즉 왼쪽 오른쪽이 교차되면) 반복문을 벗어난다.
5). a[i]와 a[j]를 서로 교환한다.
1). l값은 인덱스 1로 시작하고,(0은 감시 키값) r값은 끝에서 시작한다. 끝값은 피봇이라고 위에 적었는데 어차피 j=r-l이므로 j는 피봇을 제외한 오른쪽 끝값이 된다.
특징.
1. 빠르다.
2. 최악의 경우 선택, 삽입정렬과 같다.
예시. 책에서 가져옴.
찾아보니 여기에 있다.
리스트 a = [6, 2, 8, 1, 3, 9, 4, 5, 10, 7] 가 있다고 하자.
l=1,r=10
-1 6 2 8 1 3 9 4 5 10 7 로 나열되며 맨 앞의 -1은 감시키값, 끝의 7은 피봇이다. i는 감시키값을 제외한 왼쪽값인 6부터, j는 피봇을 제외한 오른쪽값인 10부터 시작한다.
-1 6 2 8 1 3 9 4 5 10 7 진하게 표시된 8과 5가 걸렸다. 8은 피봇보다 큰 값이고, 5는 오른쪽부터 시작할때 피봇보다 작은 값이다. 서로 값을 바꾼다.
-1 6 2 5 1 3 9 4 8 10 7 교환후 i값은 5 이후에 1로 되고, j는 4로 가서 다시 오른쪽 왼쪽으로 조여가며 값을 찾는다.
-1 6 2 5 1 3 9 4 8 10 7 9,4가 걸렸고 서로 교환한다.
-1 6 2 5 1 3 4 9 8 10 7 교환이후 i,j는 서로 교차한다. i=9,j=4가 되는데 교차된 이후 i값과 피봇 값을 교환한다. (그리고 j의 인덱스는 다음 단계의 피봇이 된다.)그러면
-1 6 2 5 1 3 4 7 8 10 9 피봇과 9가 교환되었다. 이제 다음단계로 넘어간다. 다음단계의 r은 마지막의 j값이다.(여기에선 4다)
l=1, r=6
-1 6 2 5 1 3 4 7 8 10 9 i==6이고, j==3, 피봇은 4다. 위에처럼 i는 오른쪽, j는 왼쪽으로 가면서 찾아보면
-1 3 2 5 1 6 4 7 8 10 9 i==6이 피봇 4보다 크고, j==3이 피봇 4보다 작으므로 둘이 서로 교환해준다.
-1 3 2 1 5 6 4 7 8 10 9 1,5가 걸려서 둘이 교환해줬다. 이제 i와 j가 교차됬고 i==5,j==1이다.
-1 3 2 1 4 6 5 7 8 10 9 위처럼 피봇값이었던 4와 i값이었던 5를 교환해준다. (j의 인덱스였던 3은 다음 값의 피봇이 된다.)
다음은 l=1, r=3이 되고, 그다음은 l=5,r=6, l=8,
시간 복잡도 최선 : O(NlogN) 평균적인 경우 : 1.38NlogN, 최악 : O(N^2)
# -*- encoding: cp949 -*-
import time
import random
N = 100000
def swap(a,i,j):
a[i],a[j] = a[j],a[i]
def CheckSort(a,n):
Sorted = True
for i in range(n):
if a[i] > a[i+1]:
Sorted = False
if not Sorted:
break
if Sorted: print '정렬 완료.'
else: print '정렬 오류 발생.'
def QuickSort(a,l,r):
if r>l:
v = a[r]
i = l-1
j = r
while True:
while True:
i += 1
if a[i]>=v: break
while True:
j -= 1
if a[j]<=v: break
if i>=j: break
swap(a,i,j)
swap(a,i,r)
QuickSort(a,l,i-1)
QuickSort(a,i+1,r)
def main():
a = [random.randint(1,65536) for i in range(0,N+1)] #랜덤한 10000개의 데이터
a[0] = -1
start_time = time.time()
QuickSort(a,1,N)
print '(랜덤)퀵 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
#a = [i for i in range(0,N+1)] #정렬된 10000개의 데이터 #리커전이 너무 많이 일어나서 랜덤한 데이터밖에 정렬이 안된다.
#a[0] = -1
#start_time = time.time()
#QuickSort(a,1,N)
#print '(최고)퀵 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
#CheckSort(a,N)
#a = [i for i in range(N,-1,-1)] #최악의 경우의 10000개의 데이터
#a[0] = -1
#start_time = time.time()
#QuickSort(a,1,N)
#print '(최악)퀵 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
#CheckSort(a,N)
if __name__=='__main__':
main()
퀵정렬의 성능 향상을 위한 순환을 제거한 퀵 정렬. 순환 알고리즘의 성능을 향상시키기 위해 스택을 사용하여 순환을 제거한다. QuickSort부분만 이걸로 바꾼다.
class Stack:
def __init__(self,max=100):
self.stack = [0 for i in range(max)]
self.p = 0
def push(self,v):
self.stack[self.p] = v
self.p += 1
def pop(self):
self.p -= 1
return self.stack[self.p]
def empty(self):
return True if self.p==0 else False
def partition(a,l,r):
v = a[r]
i = l-1
j = r
while True:
while True:
i += 1
if a[i]>=v: break
while True:
j -= 1
if a[j]<=v: break
if i>=j: break
swap(a,i,j)
swap(a,i,r)
return i
def QuickSort(a,l,r):
sf = Stack(50)
while True:
while r > l:
i = partition(a,l,r)
if i-l > r-i:
sf.push(l)
sf.push(i-1)
l = i+1
else:
sf.push(i+1)
sf.push(r)
r = i-1
if sf.empty(): break
r = sf.pop()
l = sf.pop()
작은 부분파일을 고려한 퀵 정렬.
퀵 정렬중 처리해야 할 원소의 갯수가 상수 M보다 작아지게 되면 거의 정렬된 파일이 만들어지는데, 이걸 삽입 정렬로 처리하면 퀵 정렬의 성능을 향상시킬수 있다고 한다.
# -*- encoding: cp949 -*-
import time
import random
N = 10000
M = 20
def swap(a,i,j):
a[i],a[j] = a[j],a[i]
def CheckSort(a,n):
Sorted = True
for i in range(n):
if a[i] > a[i+1]:
Sorted = False
if not Sorted:
break
if Sorted: print '정렬 완료.'
else: print '정렬 오류 발생.'
def InsertionSort(a,l,r):
for i in range(l+1,r+1):
v = a[i]
j=i
while a[j-1] > v:
a[j] = a[j-1]
j -= 1
a[j] = v
def QuickSort(a,l,r):
if r-l <= M: InsertionSort(a,l,r)
else:
v = a[r]
i = l-1
j = r
while True:
while True:
i += 1
if a[i]>=v: break
while True:
j -= 1
if a[j]<=v: break
if i>=j: break
swap(a,i,j)
swap(a,i,r)
QuickSort(a,l,i-1)
QuickSort(a,i+1,r)
def main():
a = [random.randint(1,65536) for i in range(0,N+1)] #랜덤한 10000개의 데이터
a[0] = -1
start_time = time.time()
QuickSort(a,1,N)
print '(랜덤)퀵 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
if __name__=='__main__':
main()
퀵 정렬의 성능향상을 위해 분할 원소를 선택 시 왼,오른,가운데 중 값이 중간인 원소를 선택하는것이다. 이걸 중간 값 분할이라고 한다고 한다.
최악의 경우가 발생하는 확률을 낮추어 주고 감시 키를 사용할 필요가 없다고 한다.
*위의 것들은 이상하게 랜덤인 경우에는 잘 됬는데 최선,최악의 경우에는 리커전 에러였나? 그게 떠서 랜덤의 경우에만 올렸다. 이번에 중간 값 분할을 이용한 것은 왠일인지 다 잘 작동한다.
# -*- encoding: cp949 -*-
import time
import random
N = 100000
def swap(a,i,j):
a[i],a[j] = a[j],a[i]
def CheckSort(a,n):
Sorted = True
for i in range(n):
if a[i] > a[i+1]:
Sorted = False
if not Sorted:
break
if Sorted: print '정렬 완료.'
else: print '정렬 오류 발생.'
def QuickSort(a,l,r):
if r-l > 1:
m = (l+r) / 2
if a[l] > a[m]:swap(a,l,m)
if a[l] > a[r]:swap(a,l,r)
if a[m] > a[r]:swap(a,m,r)
swap(a,m,r-1)
v = a[r-1]
i = l
j = r-1
while True:
while True:
i += 1
if a[i]>=v: break
while True:
j -= 1
if a[j]<=v: break
if i>=j: break
swap(a,i,j)
swap(a,i,r-1)
QuickSort(a,l,i-1)
QuickSort(a,i+1,r)
elif a[l] > a[r]: swap(a,l,r)
def main():
a = [random.randint(1,65536) for i in range(0,N+1)] #랜덤한 10000개의 데이터
a[0] = -1
start_time = time.time()
QuickSort(a,1,N)
print '(랜덤)퀵 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
a = [i for i in range(0,N+1)] #정렬된 10000개의 데이터 #리커전이 너무 많이 일어나서 랜덤한 데이터밖에 정렬이 안된다.
a[0] = -1
start_time = time.time()
QuickSort(a,1,N)
print '(최고)퀵 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
a = [i for i in range(N,-1,-1)] #최악의 경우의 10000개의 데이터
a[0] = -1
start_time = time.time()
QuickSort(a,1,N)
print '(최악)퀵 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
if __name__=='__main__':
main()