[Algorithm] 퀵정렬 (빠르고 효율적인 정렬방법)

계속해서 o(n log n) 시간복잡도를 가지는 정렬방법에 대해 알아보겠습니다. 이번에는 퀵정렬입니다. 실무에서도 가장 많이쓰이고 속도와 효율성이 가장 좋다고도 할수있는 정렬 방식입니다.


퀵정렬 

이번에도 그림을 통해 설명해드리겠습니다.


퀵정렬1


☞ 먼저 PVIOT을 정합니다. 대부분 정렬속도를 위하여 가운데 숫자를 PIVOT으로 정하는게 효율적입니다.


☞ PVIOT값과 LEFT값을 비교하여 LEFT값이 PIVOT보다 크다면 PIVOT값과 RIGHT값을 비교합니다.

RIGHT값이 PIVOT보다 크다면 RIGHT커서를 왼쪽으로 이동시킨후 다시 PIVOT값과 비교합니다.


☞ RIGHT값이 PIVOT보다 작다면 LEFT값과 RIGHT값을 바꿉니다. 그런뒤 LEFT값을 오른쪽으로 한칸 옮깁니다.


☞ LEFT값과 RIGHT값이 만날때까지 무한반복합니다.


퀵정렬2

☞ LEFT커서와 RIGHT커서가 만나면 해당값과 PIVOT값을 비교합니다. PIVOT값이 크면 오른쪽에 위치시키고 PIVOT값보다 작으면 왼쪽에 위치시킵니다.


☞ 이전 PIVOT을 기준으로 이전PIVOT보다 작은값과 큰값으로 나누고 이전 PIVOT값보다 작은값을 기준으로 새로운 PIVOT을 설정합니다.


☞ 다시 앞에서 한 방식으로 PIVOT을 기준으로 LEFT값과 RIGHT값을 교환합니다.


☞ 정렬이 완료됩니다.


퀵정렬 소스 코드(C언어/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;
}

결과

퀵정렬결과


[C언어] 버블정렬 (배열에 있는 정수값 오름차순 정렬하기)

[C언어] 선택정렬 (배열에 있는 정수값 내림차순 정렬하기)

[C언어] 삽입정렬 (배열에 있는 알파벳 차례대로 정렬하기)

[C언어] 병합정렬 (실무에서 많이쓰는 정렬방법)

[C언어] 여러가지 정렬 속도 비교(정렬의 시간복잡도


댓글(9)

  • 초보개발자
    2018.05.30 21:00

    감사합니다.

  • ms
    2019.06.05 22:14

    감사합니다 많은 도움이 됐습니다

  • 지나가요
    2019.11.16 14:32

    자료 감사합니다.
    혹시
    while (pivot >= arr[low] && low <= right) // 피벗보다 큰 값을 찾는 과정
    {
    low++; // low를 오른쪽으로 이동
    }
    여기서 low가 right보다 커져서 배열 범위 밖으로 나갈 수는 없나요?

    • 2019.11.17 03:12 신고

      pivot >= arr[low] && low <= right
      AND조건이므로 low의 값이 right보다 커지게되면 while문이 종료됩니다.

  • 2020.09.03 17:12 신고

    감사합니다 퍼갑니다.

  • dfs bfs
    2020.10.11 10:35

    도움됩니다

  • 2021.06.29 11:47

    비밀댓글입니다

    • 2021.06.29 14:48 신고

      안녕하세요 질문 답 드립니다. 아래 두개의 포스팅을 참고해보세요. 참고로 제 블로그에 적용된 내용과 똑같이 하시려면 두번째 URL을 참고하시면 됩니다. 감사합니다.

      https://coding-factory.tistory.com/150

      https://coding-factory.tistory.com/171

    • 2021.06.30 00:29

      비밀댓글입니다

Designed by JB FACTORY