Quick-Sort

퀵 정렬

 

퀵 정렬은 기준점을 중심으로 작은 그룹과 큰 그룹으로 나누어서 정렬한다.

 

 

배열 - (3,5,2,4,6,1)

주어진 배열에서 배열의 첫번째 요소의 인덱스 값(start=0)와 마지막 인덱스 값(end=5)로 양쪽 끝에서 시작하여,

앞쪽 요소값이 pivot 값 보다 큰 값이 나올 때 까지 인덱스를 높여가고, 뒤쪽 요소값이 pivot 값 보다 작은 값이 나올 때 까지 인덱스를 줄여간다.

인덱스를 줄이고 높이는 것을 멈추면 해당 값을 swap 하여 pivot 값을 중심으로 요소들을 정렬해준다.

---

1.  Partition (구분)

void partition(int a[], int start, int end){
	int pivot = a[(start+end)/2];
    
    do{
      while(a[start]<pivot) start++;
      while(a[end]>pivot) end--;
      if(start<=end){
        swap(&a[start], &a[end]);
        start++;
        end--;
    	}
    } while(start<=end)
}
int main() {
  int a[6] = {6,3,5,2,4,1};
  partition(a,0,5)
}

 

a[start] 가 pivot 값 보다 클 때까지 인덱스(start) 값을 높여간다. pivot 값 보다 크면 멈춤

a[end] 가 pivot 값 보다 작을 때까지 인덱스(end) 값을 줄여간다. pivot값 보다 작으면 멈춤

두 인덱스의 값을 높이고 줄이는 것이 멈추어 지면 해당 값을 swap 한다.

배열[start] (pivot값 보다 큼) , 배열 [end] (pivot 값 보다 작음) -> swap

 

   2. QuickSort

앞서 partition을 통해서 pivot을 기준으로 작은값 그룹과 큰값 그룹으로 나누었다.

이렇게 나누어진 그룹은 recursion(재귀)를 통해서 그룹의 요소가 1개가 될 때 까지 함수가 실행되도록 한다.

 

void partition(int a[], int start, int end){
	int pivot = a[(start+end)/2];
    do{
      while(a[start]<pivot) start++;
      while(a[end]>pivot) end--;
      if(start<=end){
        swap(&a[start], &a[end]);
        start++;
        end--;
    	}
    } while(start<=end)
  if(a
}
int main() {
  int a[6] = {6,3,5,2,4,1};
  partition(a,0,5)
}