(5)실습5주차_합병정렬과 퀵정렬

 

알고리즘 및 실습_5주차.pdf

0.12MB

[문제1]_합병정렬(오름차순)

##코드 :

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
void Merge(int* A, int start, int mid , int end) 
{
    int L = start;
    int R = mid + 1;
 
    int* B = (int*)malloc(sizeof(int) * (end - start + 1));
    int B_idx = 0;
    while (L<=mid&&R<=end) {
        if (A[L] < A[R]) 
        {
            B[B_idx] = A[L];
            L++;
        }
        else
        {
            B[B_idx] = A[R];
            R++;
        }
 
        B_idx++;
    }
 
    if (L <= mid) 
    {
        while (L <= mid) 
        {
            B[B_idx] = A[L];
            L++;
            B_idx++;
        }
    }
 
    if (R <= end) 
    {
        while (R <= end)
        {
            B[B_idx] = A[R];
            R++;
            B_idx++;
        }
    }
 
    for (int i = 0; i < (end - start + 1); i++) {
        A[start + i] = B[i];
    }
 
    free(B);
 
}
 
void MergeSort(int* A, int start, int end) 
{
    if (start + 1 > end) return;
 
    int mid = (start + end) / 2;
 
    MergeSort(A, start, mid);
    MergeSort(A, mid + 1, end);
 
    Merge(A,start,mid,end);
 
}
 
void PrintArr(int* A, int size) 
{
    for (int i = 0; i < size; i++)printf(" %d", A[i]);
    printf("\n");
}
 
int main() 
{
 
    int N;
    int* A = NULL;
    scanf("%d", &N);
 
    A = (int*)malloc(sizeof(int) * N);
 
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);
 
    MergeSort(A, 0, N - 1);
 
    PrintArr(A, N);
 
    free(A);
 
    return 0;
}

[문제2]_퀵정렬(오름차순)

##실수한 부분 :

• 랜덤 피벗 인덱스 지정 : rand() % (end - start + 1)  + start ;
• 정찰대 2명(L , R) 넘어서기 전 SWAP 과정 : SWAP 후, L++ , R--을 왜하는지를 예시 몇 개 들어서 해보기

##코드 :

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#pragma warning (disable : 4996)
 
int findPivot(int start, int end) {
 
    //실수1
    int index = rand() % (end - start + 1) + start;
}
 
int Partition(int* A, int start, int end) 
{
    int index = findPivot(start, end);
 
    int tmp = A[index];
    A[index] = A[end];
    A[end] = tmp;
 
    int L = start;
    int R = end-1;
 
    //1 3(R) 7(L) 6
    while (1) {
        
        while (L <= R && A[L] < A[end]) {
            L++;
        }
 
        while (L <= R && A[R] > A[end]) {
            R--;
        }
 
        if (L <= R) {
            tmp = A[L];
            A[L] = A[R];
            A[R] = tmp;
        
            //실수2??
            L++;
            R--;
        
        }
        else break;
    }
 
    tmp = A[L];
    A[L] = A[end];
    A[end] = tmp;
 
    return L;
 
}
 
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 < size; i++) {
        printf(" %d", A[i]);
    }
    printf("\n");
}
 
int main() 
{
    srand(time(NULL));
 
    int N;
    int* arr = NULL;
    
    scanf("%d", &N);
 
    arr = (int*)malloc(sizeof(int)*N);
 
    for (int i = 0; i < N; i++)scanf("%d", &arr[i]);
    
    QuickSort(arr, 0, N - 1);
 
    PrintArr(arr, N);
 
    free(arr);
 
    return 0;
}