(2)실습2주차_우선순위 큐(선택 & 삽입 정렬)_2_문제3의 코드와 노트

[문제3]

##질문들에 대한 필요한 자료 :

### **질문 A: 정렬되지 않은 데이터가 주어지는 경우**

1. **a) 동일한 n으로 여러 번 실행하여, 어느 정렬이 더 빠른지 비교해보자:**
   - 정렬되지 않은 데이터에 대해 선택 정렬과 삽입 정렬 중 어느 것이 더 빠른지 비교하는 것이 목표입니다.
   - 선택 정렬은 데이터의 초기 상태와 상관없이 항상 \(O(n^2)\)의 시간 복잡도를 가지며, 삽입 정렬은 부분적으로 정렬된 데이터에 대해 더 나은 성능을 보일 수 있습니다. 하지만, 두 알고리즘 모두 최악의 경우에는 \(O(n^2)\) 시간이 걸리기 때문에 성능 차이가 크지 않을 수 있습니다.
   - 동일한 크기의 n에 대해 여러 번 프로그램을 실행해보고, 어느 알고리즘이 더 빠른지 실행 시간을 비교해보면 됩니다.

2. **b) n이 증가함에 따라 두 정렬의 실행시간이 어떤 비율로 증가하는지 확인해보자:**
   - 입력 크기 n이 증가함에 따라 두 알고리즘의 실행 시간이 어떻게 증가하는지 관찰해야 합니다.
   - 일반적으로 선택 정렬과 삽입 정렬 모두 \(O(n^2)\)의 시간 복잡도를 가지므로, n이 증가할수록 실행 시간은 대략적으로 제곱의 비율로 증가할 것입니다. 하지만 삽입 정렬이 부분적으로 정렬된 데이터를 다룬다면, 실제 실행 시간은 선택 정렬보다 더 적게 증가할 수 있습니다.

### **질문 B: 정렬된 데이터가 주어지는 경우**

1. **a) 동일한 n으로 여러 번 실행하여, 어느 정렬이 더 빠른지 비교해보자:**
   - 정렬된 데이터가 주어진 경우, 삽입 정렬은 각 요소가 이미 제자리에 있는지 확인만 하면 되기 때문에 최선의 경우 \(O(n)\)의 시간 복잡도를 가집니다.
   - 반면, 선택 정렬은 데이터의 기존 정렬 상태를 활용하지 않으므로 여전히 \(O(n^2)\) 시간이 소요됩니다.
   - 따라서 정렬된 데이터에 대해서는 삽입 정렬이 선택 정렬보다 훨씬 빠르게 실행될 것입니다.

2. **b) n이 증가함에 따라 두 정렬의 실행시간이 어떤 비율로 증가하는지 확인해보자:**
   - n이 증가함에 따라 삽입 정렬의 시간 복잡도는 선형적으로 증가하는 반면, 선택 정렬은 여전히 제곱의 비율로 증가할 것입니다.
   - 이로 인해 입력 크기가 커질수록 삽입 정렬의 시간 복잡도 이점이 더욱 두드러지게 나타날 것입니다.

### **질문 C: 역순으로 정렬된 데이터가 주어지는 경우**

1. **a) 동일한 n으로 여러 번 실행하여, 어느 정렬이 더 빠른지 비교해보자:**
   - 역순으로 정렬된 데이터는 삽입 정렬의 최악의 경우를 나타내며, 각 요소를 맨 앞으로 이동해야 하기 때문에 \(O(n^2)\)의 시간 복잡도를 가집니다.
   - 선택 정렬 역시 항상 \(O(n^2)\)의 시간 복잡도를 가지므로, 역순 데이터에 대해서는 두 알고리즘이 비슷한 성능을 보일 것입니다.
   - 여러 번 테스트를 실행해보면, 작은 차이가 있을 수 있으나 둘 다 유사한 실행 시간을 보일 것으로 예상됩니다.

2. **b) n이 증가함에 따라 두 정렬의 실행시간이 어떤 비율로 증가하는지 확인해보자:**
   - 두 알고리즘 모두 \(O(n^2)\)의 시간 복잡도를 가지므로, 입력 크기 n이 증가할수록 실행 시간은 유사하게 제곱의 비율로 증가할 것입니다.

##위의 문제에 대한 코드 :

#include <stdio.h>
#include <stdlib.h>//rand()메소드 / 동적할당
#include<time.h>//srand()메소드 호출용
#include <windows.h>
#pragma warning (disable : 4996)
 
void InPlaceSort(int* A, int size)
{
    for (int i = size - 1; i >= 0; i--)
    {
        int max_i = 0;//최댓값을 첫번째 원소로 지정
        for (int j = 1; j <= i; j++)//★j범위에 i포함해야함 
        {
            if (A[max_i] < A[j]) max_i = j;//최댓값 원소 업데이트
        }
 
        //0~i-1번째중 최댓값을 i와 SWAP
        int tmp = A[max_i];
        A[max_i] = A[i];
        A[i] = tmp;
    }
}
 
void InsertSort(int* A, int size) {
 
    for (int i = 1; i < size; i++) //i의 범위 : 0(x), 1~끝범위
    {
        int j = i - 1;//j의 범위 :처음부터 ~ i뺀 나머지
        int key = A[i];//i를 key로 정함
 
        while (j >= 0 && key < A[j]) //A[j]와 key와 비교
        {//오름차순 기준 : key가 더 쎄면, A[j]를 한칸 전진
            A[j + 1] = A[j];
            j--;//j이전칸 이동
        }
        //★j+1자리에 key삽입
        A[j + 1] = key;
 
    }
}
 
void PrintArr(int* A, int size) {
 
    for (int i = 0; i < size; i++) printf(" %d", A[i]);
    printf("\n");
}
 
int main()
{
 
    LARGE_INTEGER ticksPerSec;
    LARGE_INTEGER start, end, diff;
 
 
    srand(time(NULL));
 
    //A,B배열 동적할당, 배열 원소 초기화 부분
    int N;
    int* A = NULL;
    int* B = NULL;
    scanf("%d", &N);
 
    A = (int*)malloc(sizeof(int) * N);
    B = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++) {
        A[i] = rand() % (0 + (N + 1));
        B[i] = A[i];
    }
 
    // A를 삽입정렬의 수행시간을 측정하는 코드 구간
 
    QueryPerformanceFrequency(&ticksPerSec);
    QueryPerformanceCounter(&start);
 
    InPlaceSort(A, N);
 
    QueryPerformanceCounter(&end);
 
    diff.QuadPart = end.QuadPart - start.QuadPart;
 
    printf("time: %.12f sec\n\n", ((double)diff.QuadPart / (double)ticksPerSec.QuadPart));
    
    // B를 삽입정렬의 수행시간을 측정하는 코드 구간
 
    QueryPerformanceFrequency(&ticksPerSec);
    QueryPerformanceCounter(&start);
 
 
    
    InsertSort(B, N);
 
    QueryPerformanceCounter(&end);
 
    diff.QuadPart = end.QuadPart - start.QuadPart;
 
    printf("time: %.12f sec\n\n", ((double)diff.QuadPart / (double)ticksPerSec.QuadPart));
 
    free(A);
    free(B);
 
    return 0;
}

 

##위의 코드의 출력 장면 :