C
2005.08.10 10:20

퀵 정렬 Quick Sort

조회 수 38663 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

+ - Up Down Comment Print Files
?

단축키

Prev이전 문서

Next다음 문서

+ - Up Down Comment Print Files


※ stdlib.h 파일에는 qsort() 라는 훌륭한 함수가 존재한다. 해당 함수를 활용하여도 무방하다.

※ 함수 설명
두 함수 모두 비재귀 형식의 퀵소트이며
- quick_sort1() 함수는 : 세값의 중위 분할을 통한 퀵소트로, 삽입정렬을 사용한다.
- quick_sort2() 함수는 : 난수 분할을 통한 퀵소트이며, 삽입정렬을 사용한다.

이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.


■ 퀵 정렬 개념

주어진 입력 리스트를 피봇(pivot) 또는 제어키(control key)이라 불리는 특정 키 값보다 작은 값을 가지는 레코드들의 리스트와 큰 값을 가지는 레코드들의 리스트로 분리한 다음, 이러한 두 개의 서브 리스트들을 재귀적으로 각각 재배열하는 과정을 수행하는 방식
퀵 정렬 방법은 하나의 커다란 입력 데이터의 집합을 정렬하는 것보다는 두개의 작은 입력 데이터들을 정렬하는 것이 빠르다는 일반적인 사실에 바탕을 둠
분할 및 정복 방법 사용
피봇(Pivot)이라 부르는 특정한 데이터를 기준으로 피봇보다 작은 값을 가진 데이터들은
배열의 왼쪽 부분에, 큰 값을 가진 데이터는 오른쪽에 위치하도록 배열
퀵 정렬은 기본적으로 순환(recursive) 알고리즘 형태를 취하며, 오름차순으로 정렬할 경우 레코드 R1을 제어 키 또는 피봇 키로 하여 왼쪽으로 가면서 R1보다 큰 키 값을 찾고, 오른쪽으로부터 왼쪽으로 가면서 R1보다 작은 키 값을 찾아 서로 교환한다. 위의 과정이 수행될 때 오른쪽과 왼쪽이 서로 교차하면 중지하고 R1을 제일 나중에 찾은 R1보다 작은 키 값과 교환하면 R1보다 작은 키 값을 갖는 레코드들과 큰 키 값을 갖는 레코드들로 분할되어 하나의 파일이 제어키 R1을 기준으로 두 개의 서브 파일로 재배열된다. 재배열된 서브파일에 대해 독립적으로 위의 수행 과정을 반복하면 정렬이 완료된다.

■ 퀵 정렬 알고리즘 단계 : 분할과 정복 방식
① 피봇(Pivot) : 정렬할 데이터 S에서 하나 v를 선택한다.
② 분할 : S1 = {v보다 작은 수}, v, S2 = {v보다 큰 수}
③ 재귀적 수행 : return {퀵 정렬(S1), v, 퀵 정렬(S2)}



■ 특징
▷ 평균 연산 시간에 있어서 내부 정렬 방법 중 가장 우수
     - 실제 수행속도가 가장 빠른 정렬 알고리즘
▷ 스택 공간을 사용
▷ 재귀 호출을 기반으로 동작

■ 퀵 정렬 알고리즘

-----------------------------------------------------------------------------
void Quicksort(int A[], int N) {Qsort(A,0, N-1); }      /* 퀵 정렬 호출 함수 */

int Median3(int A[], int Left, int Right)                       /* 세 수의 중위수 계산 함수 */
{      int Center= (Left + Right) / 2;              /* A[Left]<= A[Center]<= A[Right]*/
        lf( A[Left] > A[Center] ) Swap( &A[Left], &A[Center] );
        if( A[Left] > A[Right] )  Swap( &A[Left], &A[Right] );
        if( A[Center] > A[Right]) Swap(&A[Center], &A[Right]);
        swap( &A[Center], &A[Right-1] );   /* 피봇된 수를 오른쪽-1의 위치에 있는 수와 SWAP */
        return A[Right-1];                            /*return 피봇 */
}

#define Cutoff(3)                                                     /* 퀵 정렬 함수 */
void Qsort( int A[], int Left, int Right )       /* 배열 A의 왼쪽 끝 첨자:Left, 오른쪽 끝 첨자:Right */
         {     int i, j, Pivot;                              
/*1*/       if( Left + Cutoff <= Right )          
/*2*/       {     Pivot = Median3( A, Left, Right);  
/*3*/              i=Left; j=Right-1;
/*4*/              for( ; ; )
/*5*/             {    while( A[++i ] < Pivot ){}
/*6*/                   while( A[--j ] > Pivot ){}
/*7*/                   if( i < j )
/*8*/                        swap( &A[ i ], &A[ j ] );
/*9*/                   else   break;
                      }
/*10*/            swap( &A[ i ], &A[ Right-1] );
/*11*/            Qsort( A, Left, i-1 );
/*12*/            Qsort( A, i+1, Right );  
                }
                else                            
/*13*/           InsertionSort( A+Left , Right-Left+1)        
           }



②세 수의 중위수 계산, Pivot에 중앙값 넣기
⑤배열의 왼쪽에서부터 중앙값보다 큰 원소까지
   이동
⑥배열의 오른쪽에서부터 원소의 값이 중앙값보다
   작은 원소까지 이동
⑦⑧⑨정렬이 끝나지 않았으면 중앙값보다 작은
   원소는 왼쪽에, 큰 원소는 오른쪽에 들어가도록
   교체함. 정렬이 끝났으면 무한루프를 벗어남
⑩중앙값보다 큰 첫 번째 요소와 중앙값을 교환해
   중앙값을 작은 값과 큰 값 사이에 끼워 넣음.
   중위치 정렬
⑪왼쪽부분리스트(중앙값보다 작은부분)의 퀵정렬
⑫오른쪽부분리스트(중앙값보다 큰부분)의 퀵정렬
⑬원소가 Cutoff보다 작거나 같은 서브트리의
   삽입정렬
-----------------------------------------------------------------------------



■ 성능

▷ 최악의 경우: O(n2)
▷ 평균: O(nlogn)
▷ 최선의 경우는 n 개의 데이터가 저장된 배열이 각 분할 단계에서 정확히 이등분 될 때
▷ 교환 및 비교 회수가 매우 적음 : 단순하고 매우 빠른 속도로 수행
▷ 안정성은 없음
▷ 난수 배열 및 반쯤 정렬된 배열 자료에 대해서는 성능이 우수
▷ 피봇이 중간 값을 갖도록 해야 수행속도가 좋아짐


Dreamy의 코드 스크랩

내가 모으고 내가 보는

List of Articles
번호 분류 제목 날짜 조회 수 추천 수
491 C# 텍스트 파일에서 읽기/쓰기 2013.08.08 12835 0
490 JAVA 텍스트 파일 읽기, 쓰기 2015.10.21 12922 0
489 일반 탐색기 오른쪽 팝업메뉴에 항목 추가하기 2005.08.05 41874 0
488 Android 킷캣에서 바뀐 점 정리 2014.01.26 12082 0
487 Pi 키르히호프의 법칙 2016.12.05 10354 0
» C 퀵 정렬 Quick Sort file 2005.08.10 38663 0
485 C 콘솔 창에서 글자 색깔 바꾸기 2005.08.05 27110 0
484 C# 컬렉션(Collection) - ArrayList / HashTable / Queue / Stack 2012.11.12 16027 0
483 Pi 커패시터 용량, 오차 및 정격전압 판별법 (Capacitor Code) file 2016.11.21 15588 0
482 LINUX 커맨드라인에서 url 접근 - wget 사용법 2015.09.30 12002 0
481 MFC 커맨드 창 속성 제어 2009.09.01 37886 0
480 Python 커맨드 라인에서 컬러로 출력하기 termcolor 2014.06.27 10596 0
479 Android 카톡 SDK 의 안드로이드 기기 unique ID 얻기 방법 2015.01.02 15698 0
478 Pi 칩 저항 사이즈표, 사이즈변환, 와트, 오차표 2019.01.11 10420 0
477 Python 줄 바꿈 없이 출력하는 방법 2019.03.30 6798 0
목록
Board Pagination ‹ Prev 1 2 3 4 5 6 7 8 9 10 ... 34 Next ›
/ 34

나눔글꼴 설치 안내


이 PC에는 나눔글꼴이 설치되어 있지 않습니다.

이 사이트를 나눔글꼴로 보기 위해서는
나눔글꼴을 설치해야 합니다.

설치 취소

Designed by sketchbooks.co.kr / sketchbook5 board skin

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5