(2)[Chapter11]알고리즘_성능분석_2_퀵정렬_복습

각 정렬당, 비교연산 횟수, SWAP연산 횟수, 회전당 정렬 결과 분석

퀵정렬

부연설명 : 퀵정렬은 피벗에 위치에 따라 모든 연산횟수가 달라진다. 여기서 작성할 피벗은 첫,끝인덱스 기준 퀵정렬이다.

# 데이터 크기가 N일 때, 정렬상태와 상관없이 비교연산,  SWAP연산 횟수가 일정하다.

• 총 비교연산횟수 : (N-1)*N/2 ( But, 랜덤 피벗으로 할 때는, 최작의 정렬상태 < 최상의 정렬상태 )
• 총 SWAP연산 횟수 : N-1 (But, 랜덤 피벗으로 할 때는, 최작의 정렬상태 < 최상의 정렬상태 )

# 정렬 노트 분석 사진 :

##퀵정렬 출력 장면 :

 1) 끝 인덱스를 피벗으로 했을 경우 :

1_1) 최악의 정렬 상태 :

1_2) 최적의 정렬 상태 :

 

2) 랜덤 피벗으로 했을 경우 :

2_1) 최악의 정렬 상태 :

2_2) 최적의 정렬 상태 :

##전체 코드 :

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#pragma warning (disable : 4996)
 
int C_cnt = 0;//비교 연산 획수
int S_cnt = 0;//SWAP 연산 횟수
int N;//데이터 크기 입력값
 
 
int Partition(int* A, int start,int end) 
{
 
    //1_ 맨끝 인덱스 피벗 설정
    int pivotIndex = start + rand() % (end - start + 1);
    int tmp = A[pivotIndex];
    A[pivotIndex] = A[start];
    A[start] = tmp;
    S_cnt++;
 
    int pivot = A[start];
 
    //2_ 정찰조 변수 선언, 초기화
    int L = start+1;
    int R = end;
 
    //3_정찰 시작
    while (1) 
    {
        while (L<=R&&A[L]<=pivot)//pivot보다 큰애가 있으면, 멈춘다.
        {
            L++;
            C_cnt++;
        }
 
        while (L<=R&&A[R]>=pivot) //pivot보다 작은애가 있으면, 멈춘다.
        {
            R--;
            C_cnt++;
        }
 
        if (L <= R) //정찰 후, A[L]과 A[R] SWAP
        {
            tmp = A[L];
            A[L] = A[R];
            A[R] = tmp;
            S_cnt++;
        }
        else break;
 
    }
 
    //L과 pivot Swap
    tmp = A[R];
    A[R] = A[start];
    A[start] = tmp;
    S_cnt++;
 
    //Pivot의 위치 인덱스 반환
    return R;
 
}
 
void QuickSort(int* A, int start,int end) 
{
    if (start >= end) return;//재귀 종료조건
 
    int index = Partition(A, start, end);
 
    QuickSort(A, start, index - 1);
    QuickSort(A, index+1, end);
}
 
void PrintArr(int* A, int size) {
    for (int i = 0; i < N; i++)
    {
        printf(" %d", A[i]);
    }
    printf("\n");
}
 
 
int main() {
 
    printf("데이터 크기를 입력하시오. :");
    scanf("%d", &N);
 
    int* A = (int*)malloc(sizeof(int) * N);
 
    printf("배열들 원소를 입력하시오. :\n");
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
 
    printf("퀵 정렬 전 배열 상태 : \n");
 
    PrintArr(A, N);
 
    QuickSort(A, 0,N-1);
 
    printf("퀵 정렬 후 배열 상태 : \n");
 
    PrintArr(A, N);
 
    printf("데이터 크기 : %d\n", N);
    printf("비교연산 횟수 : %d\n", C_cnt);
    printf("SWAP연산 횟수 : %d\n", S_cnt);
 
    free(A);
 
    return 0;
}