[알고리즘][정렬] 퀵 정렬

chellchell·2020년 8월 16일
0

알고리즘 이론

목록 보기
6/11
post-thumbnail

퀵 정렬

정의


출처- https://visualgo.net/ko

  • 중심 값(피봇:Pivot)을 기준으로 두 자료의 키 값을 비교하여 위치를 교환하는 정렬 방식
  • 분할 정복 기법(Divide and Conquer)의 사용 - 피봇의 위치 교환이 끝난 후 피봇 기준으로 2개의 부분 집합(왼쪽,오른쪽)으로 나눠짐, 분할된 부분 집합에 대해 다시 퀵 정렬 실행
  • 합병 정렬과 비슷하게 분할 정복 기법 사용 - 전체 리스트를 2개의 부분 리스트로 분할하고 각각의 부분 리스트를 다시 퀵정렬
  • 합병 정렬과 다른 점 - 비균등 분할, 피봇(pivot)을 기준으로 분할
  • 주로 중간값(median)을 피벗으로 선택

    특정한 값을 기준으로 큰 숫자와 작은 숫자를 반으로 나눈다

항상 피봇 값은 집합의 첫번째 원소(가장 왼쪽에 위치해있음)인 노란색으로 설정한다. 피봇 값을 기준으로 왼쪽에서 오른쪽으로 움직이면서 피봇보다 큰 자료를 찾는 left와 오른쪽 끝에서 왼쪽으로 움직이며 피봇보다 작은 자료를 찾는 right를 사용한다. 단, left는 right까지 이동할 수 없고, right는 left보다 더 왼쪽으로 이동할 수 없다. 피봇보다 큰 값과 작은 값을 찾았으면 두 값을 교환해준다. left나 right이 더 이상 움직일 수 없을 때 해당 위치의 값과 피봇값을 교환해준다. 피봇값을 기준으로 왼쪽 부분은 피봇보다 작은 수들의 모임이고 오른쪽 부분은 피봇보다 큰 수들의 모임이다. 해당 시행을 왼쪽, 오른쪽 부분에 대해 다시 실행시켜준다.

구현1

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
void printArray(int value[], int count) {
	int i = 0;
	for (i = 0; i < count; i++) {
		printf("%d ", value[i]);
	}
	printf("\n");
}

void quickSort(int value[], int start, int end) {
	int pivot = 0;
	if (start < end) {// 시작 위치와 끝 위치를 비교하여 퀵 정렬을 수행할지 결정한다. 시작위치가 끝 위치와 크거나 같다면 더 이상 퀵 정렬을 수행하지 않는다.
		pivot = partitionQuickSort(value, start, end);
		quickSort(value, start, pivot - 1);
		quickSort(value, pivot + 1, end);
	}
	//분할 정복을 위해 리턴된 피봇 위치를 이용하여 왼쪽 부분 집합과 오른쪽 부분 집합에 대해 각각 함수 quickSort를 재귀적으로 호출한다. 
}

int partitionQuickSort(int value[], int start, int end) {
	int pivot = 0;
	int temp = 0, left = 0, right = 0;
	left = start;
	right = end;
	pivot = end;
	//left와 right, pivot의 위치를 초기화 시킨다. 여기서는 pivot의 위치가 right와 동일하다.
	while (left < right) {
		//left가 right의 왼쪽에 있을 때 루프 실행
		while (value[left] < value[pivot] && left < right) {
			left++;
		}
		//left는 pivot값보다 큰 값을 찾기 위해 오른쪽으로 이동한다. 단, right보다 더 오른쪽으로 이동할 수 없다. 
		while(value[right] >= value[pivot] && left < right) {
			right--;
		}
		//right는 pivot값보다 작은 값을 찾기 위해 왼쪽으로 이동한다. 단, left보다 더 왼쪽으로 이동할 수 없다.
		if (left < right) {
			temp = value[left];
			value[left] = value[right];
			value[right] = temp;

			printf("start-[%d], end-[%d], pivot-[%d], in-loop", start, end, value[pivot]);
			printArray(value, end - start + 1);
		}
		//left와 right의 위치가 적합하다면 두 자료의 위치를 교환한다.
	}
	//left와 right의 위치가 겹치면 pivot의 값과 right의 값을 교환한다. 
	temp = value[pivot];
	value[pivot] = value[right];
	value[right] = temp;

	printf("start-[%d], end-[%d], pivot-[%d], out-loop", start, end, value[right]);
	printArray(value, end - start + 1);

	return right;//최종 위치 right을 반환한다.
}

int main() {
	int values[] = { 80,50,70,10,60,20,40,30 };
	printf("Before Sort\n");
	printArray(values, 8);

	quickSort(values, 0, 7);

	printf("After Sort\n");
	printArray(values, 8);
}
  • 위 코드는 pivot값을 오른쪽 기준으로 설정함

구현2

#include <stdio.h>
#pragma warning(disable:4996)
int number = 10;
int data[10] = { 1,10,5,8,7,6,4,3,2,9 };
void quickSort(int* data, int start, int end) {
	if (start >= end) {//원소가 1개인 경우
		return;
	}
	int key = start;//키는 첫번째 원소
	int i = start + 1;//왼쪽 출발지점
	int j = end;//오른쪽 출발지점
	int temp;

	while (i <= j) {//엇갈릴 때까지 반복
		while (data[i] <= data[key]) {//키 값보다 큰 값을 만날 때까지
			i++;
		}
		while (data[j] >= data[key]&&j>start) {//키 값보다 작은 값을 만날 때까지 + 오른쪽으로 넘어가지 않도록 범위 설정(기준값이랑 오른쪽 값을 바꿈)
			j--;
		}
		if (i > j) {//현재 엇갈린 상태면 키 값과 교체
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		else {
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}
	quickSort(data, start, j - 1);
	quickSort(data, j + 1, end);
}
int main(void) {
	int i, j;
	quickSort(data, 0, number - 1);
	for (i = 0; i < number; i++) {
		printf("%d ", data[i]);
	}
} 
  • 위 코드는 pivot값을 왼쪽 기준으로 설정함
  • 엇갈린 상태: left > right 인 경우 right과 pivot을 교환

구현3

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define MAX_SIZE 10
#define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
int list[MAX_SIZE];
int n;
int partition(int list[], int left, int right) {
	int pivot, temp;
	int low, high;
	low = left;
	high = right + 1;
	pivot = list[left];
	do {
		do {
			low++;//low는 left+1에서 출발, do-while루프에서 먼저 증가를 시킴
		} while (list[low] < pivot);
		do {
			high--;//high는 right에서 출발, do-while 루프에서 먼저 감소를 시킴
		} while (list[high] > pivot);
		if (low < high)
			SWAP(list[low], list[high], temp);
	} while (low < high);
	SWAP(list[left], list[high], temp);
	return high;
}
void quick_sort(int list[], int left, int right) {
	if (left < right) {
		int q = partition(list, left, right);
		quick_sort(list, left, q - 1);
		quick_sort(list, q + 1, right);
	}
}
int main(void) {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i < n; i++) {
		list[i] = rand() % 100;
	}
	quick_sort(list, 0, n - 1);
	for (i = 0; i < n; i++) {
		printf("%d ", list[i]);
	}
	printf("\n");
}

특성

  • 최선, 평균: O(nlognnlogn)
  • 최악: O(n2n^2)
  • 상당히 효율이 우수한 알고리즘 but 정렬 전 상태에 따라 많이 다름(최악의 경우와 최선의 경우)
  • 안정성 유지되지 않음

퀵 정렬 라이브러리 함수(qsort)

void qsort(void* base, size_t num, size_t width, int(*compare)(const void*, const void*));
  • 일반적인 구조체 배열을 정렬하기 위하여 제작됨

  • void* base: 배열의 시작주소

  • size_t num: 배열 요소의 개수

  • size_t width: 배열 요소 하나의 크기(바이트 단위)

  • int (compare) (const void, const void*): 포인터를 통하여 두 개의 요소를 비교하여 비교 결과를 정수로 반환하는 함수

    • elem1 < elem2 : 음수 반환
    • elem1 == elem2 : 0 반환
    • elem1 > elem2: 양수 반환
profile
high hopes

0개의 댓글