(7)[Chapter5]정렬_버블정렬,삽입정렬(이론 + 코드), 작성중

##버블정렬,삽입정렬_이론/코드 노트:

Chapter5_1_버블정렬_삽입정렬.pdf

3.13MB

##버블정렬 핵심 개념

<1> .  버블정렬 직접 구현 핵심 개념 : (오름차순 : "낮 → 높" 으로 가정) 

1.  비교 : 서로 이웃한 값끼리 비교 
2. 연산 : "오름차순" => 왼 > 오 라면, => Swap()
3. ★N회전 범위(i) : size(원소 개수 : N )~ 1(원소 개수 :2) (역순 : 왼쪽으로 좁혀진다.)
4. 비교 연산의 범위 (j) : 0~ ( i -1) (순행)

 

<2> . ★버블정렬의 총 비교홧수 , 총 연산횟수 :

※ N회전마다, 비교, 연산횟수 빠르게 구하는 방법 

=> N회전 범위에서, 가장 큰 원소를 기준으로 왼쪽 오른쪽 나누고,

• 비교 횟수 : 원소 배열 상태에 상관없이, N회차 범위 원소개수 - 1번
• 연산 횟수 : N회차 범위 내에서, 가장 큰 원소가 왼쪽에 있을수록 , 횟수가 많아진다.

<예시코드>

 

#include <stdio.h>
 
void PrintArr(int* arr, int size) {
    for (int i = 0; i < size; i++) {
        printf(" %d", arr[i]);
    }printf("\n");
}
 
void BubbleSort(int* arr, int size) {
    int num = 1;
    int CP_cnt = 0;
    int S_cnt = 0;
    int sum_cnt = 0;
    for (int i = size-1; i >0; i--) {
        printf("%d회전의 연사횟수 :", num++);
        for (int j = 0; j <i; j++) {
            CP_cnt++;//비교 횟수 세기
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                S_cnt++;//연산(swap) 횟수 세기
            }
        }
        printf("%d\n", S_cnt);
        sum_cnt += S_cnt;
        S_cnt = 0;
    }
 
    PrintArr(arr, size);
    printf("비교 횟수 : %d\n",CP_cnt);
    printf("연산 횟수 : %d\n",sum_cnt);
 
}
 
int main() {
 
    int arr[6] = { 5, 1,6,4,2,3 };
 
    BubbleSort(arr, 6);
 
    return 0;
}

<출력결과>

 

##삽입정렬 핵심 개념

<1> .  삽입정렬 직접 구현 핵심 개념 : (오름차순 : "낮 → 높" 으로 가정) 

1. N회차의 범위 (i) : 원소개수2개부터 시작 ~ 원소개수 N까지
2. 비교 연산 범위 (j) : N회차의 범위의 원소개수 -1이고, i-1에서 역순으로 바교, 연산 진행한다.
3. 원리 : N회차의 arr[i]를 key로 설정 후, 

• arr[j] > key => 뒤로 땡기는 작업과 j를 왼쪽 이동: arr[j] = arr[j+1]; , j-- 
•  arr[j] < key => 비교 연산 종료 , ★j+1이 key가 들어갈 자리이다. : break; , arr[j+1] = key; 

<2>. ★삽입정렬의 총 비교홧수 , 총 연산횟수 :

    <2>_1. ※ N회전마다, 비교, 연산횟수 빠르게 구하는 방법 

=> N회차 범위 내에서, 맨마지막 원소(key)를 기준으로 왼쪽원소들을 빠르게

• 왼쪽원소 > key => 비교 연산 o
• 오른쪽원소 <key => 비교만 o , 연산 x , 그리고 그 다음 왼쪽은 비교,연산 없이 종료

    <2>_2. <2>의 과정 때문에, 어떤 상황이든, 버블정렬보다 삽입정렬이 시간복잡도가 더 적다.

<예시 코드>

#include <stdio.h>
 
void PrintArr(int* arr, int size) {
    for (int i = 0; i < size; i++) {
        printf(" %d", arr[i]);
    }printf("\n");
}
 
void InsertionSort(int* arr, int size) {
    int num = 1;
    int CP_cnt = 0;
    int S_cnt = 0;
    int sum_cnt = 0;
    
    for (int i = 1; i < size; i++) {
        printf("%d회전의 연산 횟수 : ", num++);
        int key = arr[i],j;
        //key의 역순으로 key자리 탐색, swap
        for (j = i - 1; j >= 0; j--) {
            CP_cnt++;
            if (arr[j] > key) {
                arr[j + 1] = arr[j];
                S_cnt++;
            }
            else break;//key가 들어갈 자리 찾음
        }
        //key가 들어갈 자리 대입 : ★j+1
        arr[j + 1]=key;
        printf("%d\n", S_cnt);
        sum_cnt += S_cnt;
        S_cnt = 0;
    }
 
    PrintArr(arr, size);
    printf("비교 횟수 : %d\n",CP_cnt);
    printf("연산 횟수 : %d\n",sum_cnt);
 
}
 
int main() {
 
    int arr[6] = { 5, 1,6,4,2,3 };
 
    InsertionSort(arr, 6);
 
    return 0;
}