exp_blog

퀵 정렬(quick sort) 알고리즘

오름차순 정렬

• 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
  • 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
• 분할 정복(divide and conquer) 방법
  • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
  • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
• 하나의 리스트를 피벗(pivot) 을 지정하여 그를 기준으로 두 개의 비균등한 크기로 분할하고, 
  분할된 부분 리스트를 정렬 -> 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 한다. 
• 단계
  1. 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
     
  2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
     
  3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
     
  4. 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)은 최종적으로 위치가 정해지므로, 
     반드시 이 알고리즘은 끝난다는 것을 보장한다. 
     
     

알고리즘 특징

• 장점
  • 속도가 빠르다.
  • 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
  • 추가 메모리 공간을 필요로 하지 않는다.
  • 퀵 정렬은 O(log n)만큼의 메모리를 필요로 한다.
• 단점
  • 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
  • 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다
    EX) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값(medium)을 피벗으로 선택한다.
    
    

시간복잡도

• 최선의 경우
  • 비교 횟수 
    • 순환 호출의 깊이 
    • T(n) = O(nlog₂n)
• 최악의 경우 
  • 리스트가 계속 불균형하게 나누어 지는 경우 ( 이미 정렬된 리스트에 대해 퀵 정렬을 실행하는 경우)
  • T(n) = O(n^2)
• 평균
  • T(n) = O(nlog₂n)
  • 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다 
  • 퀵 정렬이 불필요한 데이터 이동을 줄이고 먼 거리의 데이터를 교환할 뿐 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성으로 빠르다

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

퀵 정렬을 C언어 코드로 

# include <stdio.h>
# define MAX_SIZE 9
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )

// 1. 피벗을 기준으로 2개의 부분 리스트로 나눈다.
// 2. 피벗보다 작은 값은 모두 왼쪽 부분 리스트로, 큰 값은 오른쪽 부분 리스트로 옮긴다.
/* 2개의 비균등 배열 list[left...pivot-1]와 list[pivot+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
int partition(int list[], int left, int right){
  int pivot, temp;
  int low, high;

  low = left;
  high = right + 1;
  pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택(임의의 값을 피벗으로 선택)

  /* low와 high가 교차할 때까지 반복(low<high) */
  do{
    /* list[low]가 피벗보다 작으면 계속 low를 증가 */
    do {
      low++; // low는 left+1 에서 시작
    } while (low<=right && list[low]<pivot);

    /* list[high]가 피벗보다 크면 계속 high를 감소 */
    do {
      high--; //high는 right 에서 시작
    } while (high>=left && list[high]>pivot);

    // 만약 low와 high가 교차하지 않았으면 list[low]를 list[high] 교환
    if(low<high){
      SWAP(list[low], list[high], temp);
    }
  } while (low<high);

  // low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]를 교환
  SWAP(list[left], list[high], temp);

  // 피벗의 위치인 high를 반환
  return high;
}

// 퀵 정렬
void quick_sort(int list[], int left, int right){

  /* 정렬할 범위가 2개 이상의 데이터이면(리스트의 크기가 0이나 1이 아니면) */
  if(left<right){
    // partition 함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 -분할(Divide)
    int q = partition(list, left, right); // q: 피벗의 위치

    // 피벗은 제외한 2개의 부분 리스트를 대상으로 순환 호출
    quick_sort(list, left, q-1); // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 -정복(Conquer)
    quick_sort(list, q+1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 -정복(Conquer)
  }

}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {5, 3, 8, 4, 9, 1, 6, 2, 7};

  // 퀵 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 8)
  quick_sort(list, 0, n-1);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

고언어 통한 quick sort

func Quick(arr []int) {

	if len(arr) <= 1 {
		return
	}
	p := Divide(arr)
	Quick(arr[:p])
	Quick(arr[p:])

}

func Divide(arr []int) int {
	pivot, end := arr[0], len(arr)-1
	start := 1

	for {
		for ; start < len(arr); start++ { 
			if arr[start] > pivot {
				break
			}
		}
		for ; end > 0; end-- {
			if arr[end] < pivot {
				break
			}
		}
		if start > end { 
			break
		}
		arr[start], arr[end] = arr[end], arr[start]
	}
	arr[0], arr[end] = arr[end], arr[0]
	return end + 1
}

func main() {
	arr := []int{3, 7, 4, 1, 7, 5, 4, 8}
    algorithm.Quick(arr)
	fmt.Println(arr)

}