퀵정렬

19 Jan 2021 in Algorithms

알고리즘 설명

IDEA : Partioning 을 이용해 정렬. Divide-and-Conquer 사용

1. 피봇을 기준으로 파티셔닝을 한다.
2. 파티션한 부분을 재귀적으로 함수에 넣는다. 크기가 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는 파이썬이 너무 편한데..? 맨처음에 공간 할당 안하는게 진짜.. 넘 편..해