Computer Science/Data Structure, Algorithm

DataStructure] 퀵정렬 정렬 패스마다 high, low 출력

TwinParadox 2016. 12. 29. 18:03
728x90

대학교 때 과제로 제출했던 기억이 있다.

퀵 정렬을 진행하면서 정렬의 매 패스마다 high, low를 출력하도록 하는 거였다.

혹여 자료구조 과제를 하면서 골치 아파할 대학생들을 위해 올려놓는다.

생능출판에서 나온 'C언어로 쉽게 풀어쓴 자료 구조(개정판)'라는 책이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#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;
}
cs


728x90