퀵소트 구현 소스

퀵 정렬(Quick Sort)

퀵정렬경우 데이터양이 크고 뒤죽박죽일 경우 가장 빠른속도를 낼 수 있다.
(데이터양이 작고 덜섞인 경우 삽입정렬이 빠르다.)

먼저 퀵정렬의 원리.

다음과 같이 pivot이라는 기준점을 정하고 (주로 가장 왼쪽이나 오른쪽을 택한다. )
그외의 요소를 각각 바깥쪽에서 접근한다.
left는 기준(pivot)보다 작은값을 찾고, right는 기준(pivot)보다 큰 값을 찾는다.

pivot은 조만간 가운데에 낄것이다. 그 가운데를 기점으로 왼쪽으로는 pivot보다 작은값 , 오른쪽으로는 pivot보다 큰값을
들어가게 하려는 작정이다. (이는 오름차순으로 정렬할 목적일때 경우)

왼쪽부터 움직이는 인덱스(left)가 움직이다가 대상을 찾으면 멈추고
다음으로 오른쪽에서 왼쪽으로 움직이는 인덱스(right) 가 계속 움직이다가 대상을 찾으면 멈춘다.
그리고 각각의 대상을 바꾼다.

그래도 잘 이해가 안간다면 쉽게 표현하자면, 기준점 5라는 놈이 있다. 이놈이 left와 right에게 명령한다. "left야 right야 나보다 작은놈은 왼쪽으로 나보다 큰놈은 오른쪽으로 보낼거다." 그럼 left와 right는 각각 대상을 찾은후 서로 바꾼다.

이렇게 움직이다가 left와 right가 만나거나 서로 위치가 바뀌면
if(left >= right)
 swap( array[left], array[right])
서로의 값을 바꾼다.
그리고 루프를 나온다.

지금까지 했던 작업을 다시 반복해야하는데 주로 재귀함수 즉 이 작업을 하는 바로자신 함수를
다시 호출한다. 호출할때는 범위를 pivot을 중심으로 왼쪽범위 호출, 오른쪽 범위 호출 2개를 호출한다.

 

#include <stdio.h>

#include <stdlib.h>

 

void quick_sort(int *arr, int left, int right)

{

        int i, j;

        int temp;

        int pivot = arr[left];

        if(left < right)

        {

               i = left;

               j = right+1; //do while문경우 --연산먼저하므로 index를 1초과한값으로 시작

               while( i <= j)

               {

                       do

                       i++;

                       while(arr[i] > pivot); //오름차순을 원할경우 >를 <로

                       do

                       j--;

                       while(arr[j] < pivot); //오름차순을 원할경우 <를 >로

                       if(i<j) // 엇갈리지않으면 두 요소를 스왑

                       {

                              temp = arr[i];

                              arr[i] = arr[j];

                              arr[j] = temp;

                       }

                       else //찾은 두소요가 겹치거나 엇갈리면 한바퀴 끝
                             break;

               }

               // j위치 요소를 기준이 되었던 pivot 과 Swap

               temp = arr[j];

               arr[j] = arr[left];

               arr[left] = temp;

               //Swap ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

               quick_sort(arr, left, j-1); // 가운데가 된 pivot을 중심으로 왼쪽 영역 재귀

               quick_sort(arr, j+1, right);// 가운데가 된 pivot을 중심으로 오른쪽 영역 재귀

        }

}

 

void main()

{

        int arr[10] = {33,12,33,14,45,6,27,8,49,1};
        int i=0;

 

        quick_sort(arr, 0, 9);

 

        for(i=0; i<10; i++)

               printf("%d ", arr[i]);

 

 

}