퀵정렬
in Algorithms
알고리즘 설명
IDEA : Partioning 을 이용해 정렬. Divide-and-Conquer 사용
- 피봇을 기준으로 파티셔닝을 한다.
- 파티션한 부분을 재귀적으로 함수에 넣는다. 크기가 1이 될때까지 반복
성능 분석
- balanced partitioning : 절반으로 나누기 O(nlogn)
- unbalanced partitioning : Θ(n^2)
JAVA 코드
public static void quick_sort(int[] ary, int start, int end){
int pivot = end;
if(start+1>=end){return;}
int first =start;
int last = end-1;
while (first<last) {
while(ary[first]<ary[pivot] && first <last){first++;}
while(ary[last]>ary[pivot] && first <last) {last--;}
int tmp = ary[first];
ary[first]= ary[last];
ary[last]= tmp;
}
/*이 코드는 1. 이미 정렬된 배열일때, 2. while 문을 나올 때 접할 수 있다.
그래서 if문으로 체크해줘서 1번의 경우인지 2번의 경우인지 판별할 수 있다.
pivot을 어레이의 마지막 원소를 잡았기 때문에 last랑 바꾸는 것.
만약 어레이의 첫번째 원소로 잡았다면 first랑 바꿨을 것이다.*/
if(ary[last] > ary[pivot]) {
int tmp = ary[last];
ary[last]=ary[pivot];
ary[pivot]=tmp;
}
quick_sort(ary,start,last);
quick_sort(ary,last,end);
}
PYTHON 코드
def quick_sort(ary):
if len(ary)<=1 :
return ary
pivot = ary[-1];
left =[]
right = []
for i in range(0,len(ary)-1):
if(ary[i]<pivot):
left.append(ary[i])
else:
right.append(ary[i])
return quick_sort(left)+[pivot] + quick_sort(right)
quick_sort([12,23,123,1,2,4,22,421,87])
역시.. array는 파이썬이 너무 편한데..? 맨처음에 공간 할당 안하는게 진짜.. 넘 편..해