컴퓨터 알고리즘 초급 #6 ( 퀵 정렬 in c )

 

2020/03/20 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c )

컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c )

 

 

퀵 정렬 (Quicksort) : 피봇이라는 값을 기준으로 피봇보다 작은것은 왼쪽, 큰것은 오른쪽으로 보내는 파티셔닝이라는 작업을 반복해서 작은 숫자는 계속 왼쪽, 큰 숫자는 계속 오른쪽으로 보내서 정렬시키는 방법

 

 

 

Divide-and-Conquer paradigm을 사용 (작게 쪼개서 작은걸 연산함 , 그 결과를 합침)

 

퀵 정렬은 partition 을 이용하여 한다.

 

Partitioning 

 

Pivot element 를 정하여

 

피봇의 왼쪽은 작거나 같은 것 오른쪽은 크거나 같은값을 넣는다.

 

 

 

이 Partitioning을 재귀적으로 반복한다.

 

 

피봇의 왼쪽에서 피봇을 또 잡고 다시 그 왼쪽에는 작은값 오른쪽에는 높은값을 넣는다

 

이러한 과정을 반복한다.

 

{ 2 , 8 , 7 , 1 , 3 , 5 , 6, 4 }

 

피봇아이템 : 4

 

4와 2 비교 (4보다 작으므로 회색)

 

8과 4 비교 (4보다 크므로 녹색)

 

7과 4 비교 (4보다 크므로 녹색)

 

1과 4 비교 (4보다 작으므로 회색)

 

3과 4 비교 (4보다 작으므로 회색)

 

5와 4 비교 (4보다 크므로 녹색)

 

6과 4 비교 (4보다 크므로 녹색)

 

 

이런식으로 진행된다.

여기서 만약 녹색이 나오다가 회색이나오면 

 

첫번째 녹색과 회색의 자리를 바꾼다 (ex 1과 8의 자리를 바꾼 것)

 

반복, 최종적으로는 첫번째 녹색과 피봇값을 바꾼다.

 

그렇게되면 최종적으로 {2,1,3,4,7,5,6,8} 이 된다.

 

수행시간 : 한번의 파티셔닝에 N-1번 비교하므로 0(n)

 

그렇다면, 정렬될때까지 몇번의 파티셔닝을 수행하느냐가 관건이다.

 

길이가 N인 배열은 길이가 2/N인 배열로 쪼개지고, 그 배열은 4/N배열로 쪼개지고 이러한 파티셔닝을 Balanced partitioning 이라고 한다.

 

Balanced partitioning 수행시간 : O(nlgn)

 

 

Unbalanced partitioning 

쪼개면 1과 n-1 , 1과 n-2 ... 된다.

 

Unbalanced partitioning 수행시간 : O(n^2)

 

즉 선택한 피봇보다 작은 숫자가 1개 밖에 없을 때 Unbalanced partitioning이다. 최악의 경우이다.

 

 

최악의 경우에 피하기 위해서는

 

배열에서 Pivot을 무작위로 뽑아낸다.

 

그렇게하면 배열되어있는 상태의 배열은 최악의 경우를 따르겠지만, 배열되어 있든 아니든 항상 우리가 기대하는 확률값을 가질 수 있기 때문에 랜덤으로 피봇을 뽑아옴으로써 최악의 경우를 피할 수 있다.

 

 

 

퀵 정렬 in c

 

#include <stdio.h>
#include <stdlib.h> //랜덤함수 호출

void Swap(int arr[], int a, int b) // a,b 스왑 함수 
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
int Partition(int arr[], int left, int right)
{
    int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (low <= right && pivot >= arr[low]) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
        while (high >= (left+1)  && pivot <= arr[high]) // 피벗보다 작은 값을 찾는 과정 
        {
            high--; // high를 왼쪽으로 이동
        }
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            Swap(arr, low, high); //low와 high를 스왑 
        }
    }
    Swap(arr, left, high); // 피벗과 high가 가리키는 대상을 교환 
    return high;  // 옮겨진 피벗의 위치정보를 반환 
 
}
 
 
void QuickSort(int arr[], int left, int right)
{
    if (left <= right)
    {
        int pivot = Partition(arr, left, right); // 둘로 나누어서
        QuickSort(arr, left, pivot - 1); // 왼쪽 영역을 정렬한다.
        QuickSort(arr, pivot + 1, right); // 오른쪽 영역을 정렬한다.
    }
}
 
//메인함수
int main()
{
    int n,i;
    int arr[100];

	
    printf("몇개의 숫자로 정렬하시겠습니까?\n");
    scanf("%d",&n);

	for(i = 0 ; i < n ; i++)
		 arr[i]=rand()%1000;

	 printf("정렬전 배열 :");
	 for(i = 0 ; i < n ; i++)
        printf("%d ", arr[i]);
	 printf("\n");

    QuickSort(arr,0,n-1);

	printf("정렬후 배열 :");
    for(i = 0 ; i < n ; i++)
        printf("%d ", arr[i]);
	printf("\n");

    return 0;
}

//출처 : https://coding-factory.tistory.com/137