(1)[Chapter11]알고리즘_성능분석_1_버블정렬,삽입정렬_복습

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

1_ 버블정렬

1_1) 데이터 크기가 N일 때,

• 총 비교 연산 횟수 : 1부터 N-1합 == (N-1)*(N)/2 (정렬상태와 상관없이)
• 총 SWAP 연산 횟수 : 데이터 정렬 상태에 따라 다르다

최악의 정렬 상태 : 오름차순 기준 정렬하려고 할 때, 정렬 전 배열이 내림차순으로 정렬되어있을 때, => SWAP연산 횟수 최대

최적의 정렬 상태 : 오름차순 기준 정렬하려고 할 때, 정렬 전 배열이 오름차순으로 정렬되어있을 때, => SWAP연산 횟수 0

• 1회전 당 정렬 결과 (오름차순 정렬 기준) : 데이터 N개 중 최댓값이 맨 오른쪽에 배치 된다.

1_2) 정렬 노트 분석 사진

 

 

 

##버블정렬 출력 장면

 

 

2_ 삽입 정렬

2_1) 데이터 크기가 N일 때,

• 총 비교 연산 횟수 : 1부터 N-1합 == (N-1)*(N)/2 (정렬상태에 따라 다르다!!)

- 최악의 정렬 상태일 경우 : (N-1)*N/2

- 최적의 정렬 상태일 경우 : N-1

• 총 SWAP 연산 횟수 : 데이터 정렬 상태에 따라 다르다

- 최악의 정렬 상태일 경우 : (N-1)*N/2

- 최적의 정렬 상태일 경우 : 0

2_2) 정렬 노트 분석 사진 :

 

##삽입정렬 출력 장면(SWAP연산==전진연산)

 

<전체 코드>

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
int C_cnt = 0;//비교 연산 획수
int S_cnt = 0;//SWAP 연산 횟수
int N;//데이터 크기 입력값
 
void BubbleSort(int* A,int size) {
    //오름차순 : 낮 -> 높
    for (int i = N-1; i >=0 ; i--) {
        for (int j = 0; j < i; j++) {
            C_cnt++;
            if (A[j] > A[j + 1]) 
            {
                int tmp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = tmp;
 
                S_cnt++;
            }
        }
    }
 
}
 
void InsertSort(int* A, int size) 
{
    
    int i, key, j;
 
    for (int i = 1; i < size; i++) 
    {
        key = A[i];
        
        j = i - 1;
 
        while (j >= 0)//j가 A배열 원소인덱스 && 전진연산
        {
            C_cnt++;
            if (A[j] > key)
            {
                //전진연산
                A[j + 1] = A[j];
                S_cnt++;
 
                //j역순 이동
                j--;
            }
            else break;
        }
 
        //key삽입
        A[j + 1] = key;
    }
 
}
 
 
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);
 
    InsertSort(A, N);
 
    printf("버블 정렬 후 배열 상태 : \n");
 
    PrintArr(A, N);
 
    printf("데이터 크기 : %d\n", N);
    printf("비교연산 횟수 : %d\n",C_cnt);
    printf("SWAP연산 횟수 : %d\n", S_cnt);
 
    free(A);
 
    return 0;
}