[알고리즘 트레이닝 2일차] quick sorting.

quick sorting.

quick sorting은 평균시간복잡도의 시간복잡도를 가진 정렬 알고리즘으로 

버블정렬과 같이 시간복잡도 의 비효율적인 성능시간을 개선하기 위해 사용한다.

기본적으로 이전에 포스팅 했던 binary search와 같이 분할정복법을 이용하여 정렬한다.

큌정렬 방식은 기본적으로 값의 기준이 되는 pivot을 정하여 pivot을 기준으로 큰값은 오른쪽, 

작은값은 왼쪽으로 이동시키며 좌,우를 분할하여 정렬한다. 정렬이 끝나면 pivot의 기준을 바꾸어

다시 좌우로 정렬하는 식의 동작을 반복하여 정렬한다.

cpp code 

#include <iostream>
#define ARRAY_SIZE 10

int q_sort(int *list , int left, int right);
int main()
{
  int list[ARRAY_SIZE] = { 3, 5, 7, 1, 10, 2, 4, 9, 8, 6};
  int left = 0;
  int right = ARRAY_SIZE-1;

  q_sort(list, left, right);

  std::cout << "RESULT : ";
  for(int i=0; i < ARRAY_SIZE; i++){
    std::cout << list[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

int q_sort(int *list , int left, int right){
  int pivot = list[left];
  int init_left = left;
  int init_right = right;
  while( left < right){
    while( (pivot <= list[right]) && (left < right) ){
      right--;
    }
    if( list[left] != list[right] ){
      list[left] = list[right];
    }
    while( (pivot >= list[left]) && (left < right) ){
      left++;
    }
    if (left != right) {
      list[right] = list[left];
      right--;
    }
  }
  list[left] = pivot;
  for(int i=0; i < ARRAY_SIZE; i++){
    std::cout << list[i] << " ";
  }
  std::cout << std::endl;

  if( init_left < left ){
    q_sort( list, init_left, left-1 );
  }
  if( init_right > left ){
    q_sort( list, left+1, init_right );
  }
  return 0;
}

실행결과

2 1 3 7 10 5 4 9 8 6

1 2 3 7 10 5 4 9 8 6

1 2 3 7 10 5 4 9 8 6

1 2 3 6 4 5 7 9 8 10

1 2 3 5 4 6 7 9 8 10

1 2 3 4 5 6 7 9 8 10

1 2 3 4 5 6 7 9 8 10

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

RESULT : 1 2 3 4 5 6 7 8 9 10