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

---

퀵정렬 알고리즘이란

---

분할 정복 알고리즘의 하나이다. 

분할 정복 방법이란, 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

퀵 정렬은 문제를 2개의 부분문제로 분할할 때, 크기가 일정하지 않은 특징이 있다.

 

왜 부분문제의 크기가 다르냐면, 퀵 정렬을 할 때

피봇을 기준으로 피봇보다 큰 숫자는 오른편에, 작은 숫자는 왼편에 위치하도록 분할한 후에 

피봇을 그 사이에 놓는다.

 

알고리즘)

quickSort(A, left, right)
input: A[left] ~ A[right]
output: 정렬된 A[left] ~ A[right]

1. if(left < right){
2. 	피봇이 되는 숫자를 정의한다.
3.  피봇을 배열의 원소와 비교한다.
4.  피봇보다 작은 숫자들은 A[left] ~ A[p-1]로 옮긴다.
	피봇보다 큰 숫자들은 A[p+1] ~ A[right]로 옮긴다.
5.  quickSort(A, left, p-1) //피봇보다 작은 그룹
6.  quickSort(A, p+1, right)//피봇보다 큰 그룹

 

퀵정렬의 과정

1. 리스트 안에 있는 한 요소를 선택한다. 이 요소는 피봇이다.

2. 피봇보다 작은 요소는 피봇의 왼쪽으로 옮기고, 피봇보다 큰 요소는 피봇의 오른쪽으로 옮긴다.

3. 피봇을 제외한 왼쪽과 오른쪽 요소들을 정렬한다.

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 15
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void makeList(int list[])
{
    for(int i = 0; i < SIZE; i++)
        list[i] =rand() % 100 + 1;
}

void printList(int list[])
{
    for(int i = 0; i < SIZE; i++)
        printf("%d ", list[i]);
    printf("\n");    
}

int partition(int list[], int left, int right)
{
    int pivot, temp, low, high;
    
    pivot = list[left];
    low = left; high = right + 1;
    
    do
    {
        do
            low++;
        while (list[low] < pivot);
        
        do  
            high--;
        while (list[high] > pivot);
        
        /*
        for (int i = 0; i < SIZE; i++)	
			printf("%d ", list[i]);
		printf("\nlow=%d, high=%d\n", low, high);
        */
        
        if(low < high)
            SWAP(list[low], list[high], temp);
    
    } while (low < high);
    
    SWAP(list[left], list[high], temp);
    return high;
}

void quickSort(int list[], int left, int right)
{
    if(left < right)
    {
        int q = partition(list, left, right);
        quickSort(list, left, q - 1);
        quickSort(list, q + 1, right);
    }
}

int main()
{
	int list[SIZE];
	srand(time(NULL));
    
    makeList(list);
    printList(list);
    
    quickSort(list, 0, SIZE - 1);
    printList(list);
}

 

 

https://spacebike.tistory.com/29

퀵 정렬 (Quick sort) 쉽게 알기