DataStructure] C언어로 쉽게 풀어쓴 자료구조 9장 - 6

DataStructure] C언어로 쉽게 풀어쓴 자료구조 9장 - 6

C언어로 쉽게 풀어쓴 자료구조

9장 Exercise 문제다.

필자가 학교 다니면서 자료구조론 수업을 들었는데,

과제로 제출했던 것들이고,

난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.

자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다.

24. 퀵 정렬에서 함수가 수행되면서 정렬의 매 패스마다 다음과 같은 형식으로 화면에 출력하도록 함수를 수정하라.

#include <stdio.h>
#include <stdlib.h>
 
#define SWAP(a,b) {int t; t=a; a=b; b=t;}
 
// 배열의 크기
int n;
 
void PrintSit(int list[], int high, int low)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d\t", list[i]);
    }
    printf("\n");
    for (int i = 0; i < n; i++)
    {
        if (i == high)
            printf("high\t");
        else if (i == low)
            printf("low\t");
        else
            printf("\t");
    }
    printf("\n");
}
int partition(int list[], int left, int right)
{
    int pivot;
    int low, high;
    low = left;
    high = right + 1;
    pivot = list[left];
    do
    {
        do
        {
            low++;
        } while (low <= right && list[low] < pivot);
        do
        {
            high--;
        } while (high >= left && list[high] > pivot);
        if (low < high)
        {
            PrintSit(list, high, low);
            SWAP(list[low], list[high]);
        }
        if (low+1 >= high)
            PrintSit(list, high, low);
    } while (low < high);
 
    SWAP(list[left], list[high]);
    return high;
}
void QuickSort(int list[], int left, int right)
{
    if (left < right)
    {
        int q = partition(list, left, right);
        QuickSort(list, left, q - 1);
        QuickSort(list, q + 1, right);
    }
}
 
int main(void)
{
    int* ar;
    printf("배열의 크기 : ");
    scanf_s("%d", &n);
    
    printf("배열의 내용 입력 : ");
    ar = (int*)malloc(sizeof(int)*n);
 
    for (int i = 0; i < n; i++)
        scanf_s("%d", &ar[i]);
 
    QuickSort(ar, 0, n - 1);
 
    free(ar);
    return 0;
}