퀵 정렬 : quick sort

퀵 정렬은 피벗이라는 기준 숫자를 정하여 기준숫자보다 작으면 왼쪽인덱스로 크면 오른쪽은덱스로 옮기는 방식으로

약간 분할정복 개념 으로 정렬을 한다.

 

c++의 sort STL 은 퀵정렬을 사용하며 시간복잡도 O(NlogN)을 보장한다.

퀵정렬의 시간복잡도는 최악의 경우 O(N^2) 이지만 평균적으로 O(NlogN)을 보인다.

 

 

 정렬 과정 

밑줄친 숫자는 피벗 숫자이고 빨간색 숫자는 정렬이 완료된 숫자이다

 

 알고리즘 

1. 배열의 가장 왼쪽 에 있는 수를 피벗 으로 정함

2. 피벗기준으로 피벗보다 작은수는 왼쪽으로 큰수는 오른쪽으로 옮김

3. 피벗을 계속 갱신해주고 피벗을 이용하여 정렬한 숫자를 다시 1-2번과정을 통하여 정렬.

 

#include<iostream>
 
using namespace std;
int arr[10] = { 3,7,8,1,5,9,6,10,2,4 };
 
void quickSort( int start, int end) {
   if (start >= end) { //원소가 한개인 경우
      return;
   }
 
   int key = start; //키는 첫번째 원소
   int i = start + 1; //왼쪽 출발지점
   int j = end; //오른쪽 출발지점
   int temp;
   
   while (i <= j) {//엇갈릴 때까지 반복
      while (arr[i] <= arr[key]) { //키 값보다 큰 값을 만날때 까지
         i++;
      }
      while (arr[j] >= arr[key] && j > start) {
         j--;
      }
      if (i > j) {// 엇갈렸을경우
         temp = arr[j];
         arr[j] = arr[key];
         arr[key] = temp;
      }
      else { //엇갈리지 않았다면 i 와 j를 교체
         temp = arr[j];
         arr[j] = arr[i];
         arr[i] = temp;
      }
   }
   quickSort(start, j - 1);
   quickSort(j + 1, end);
}
 
 
int main() {
 
   int idx, temp;
   int number = 10;
 
   cout << "정렬전 :";
   for (int i = 0; i < 10; i++)
      cout << arr[i] << " ";
   cout << endl << "정렬후 : ";
 
   quickSort( 0, number - 1);
 
 
 
 
 
 
   
 
   for (int i = 0; i < 10; i++)
      cout << arr[i] << " ";
   cout << endl;
}

 

모든 글의 내용은 나동빈님 블로그를 참고 하였습니다.

https://blog.naver.com/ndb796/221228342808