선택, 삽입, 버블, 셸, 퀵, 기수, 병합, 힙 정렬 코드(퀵 이상함)

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <string.h>

#define max 10

#define mem(a) memset(a, 0, sizeof(a))

#define swap(a,b) {int t; t = a; a = b; b = t;}

int number[max], result[max];

clock_t start, end;

void console();

void initialize();

void printResult();

void copyIndex();

void selection();

void insert();

void bubble();

void shell();

void quickCall();

void quick(int left, int right);

void radix();

void merge(int *base, int n);

void mergeCall();

void heap();

int main()

{

initialize();

console();

}

void initialize()

{

srand((unsigned)time(NULL));

for (int i = 0; i < max; ++i)

number[i] = (rand() % 100);

printf("현재 저장된 배열의 값은 [%d", number[0]);

for (int i = 1; i < max; ++i)

printf(", %d", number[i]);

printf("]\n");

}

void console()

{

while (1)

{

char command[4];

printf("\n명령어 : ini - 배열 재설정, sel - 선택 정렬, ins - 삽입 정렬\n명령어 : bub - 버블 정렬, she - 셸 정렬, qui- 퀵 정렬\n명령어 : rad - 기수 정렬, mer - 병합 정렬, hea - 힙 정렬\n");

printf("\n명령어를 입력해주세요 : ");

scanf("%s", &command);

start = clock();

if (!strcmp(command, "ini"))

{

initialize();

continue;

}

else if (!strcmp(command, "sel"))

selection();

else if (!strcmp(command, "ins"))

insert();

else if (!strcmp(command, "bub"))

bubble();

else if (!strcmp(command, "she"))

shell();

else if (!strcmp(command, "qui"))

quickCall();

else if (!strcmp(command, "rad"))

radix();

else if (!strcmp(command, "mer"))

mergeCall();

else if (!strcmp(command, "hea"))

heap();

else

{

printf("\n명령어를 다시 확인해주세요.\n");

continue;

}

end = clock();

printResult();

}

}

void copyIndex()

{

for (int i = 0; i < max; ++i)

result[i] = number[i];

}

void printResult()

{

printf("정렬된 배열의 값은 [%d", result[0]);

for (int i = 1; i < max; ++i)

printf(", %d", result[i]);

printf("]\n");

printf("정렬에 소요된 시각은 %.4f s\n", (double)(end - start) / (double)1000);

}

void selection()

{ // 선택 정렬은 1번 인덱스를 2~10번과 비교, 2번 인덱스를 3~10번과 비교... 하는 방식

copyIndex();

for (int i = 0; i < max - 1; ++i)

for (int j = i + 1; j < max; ++j)

if (result[i] > result[j])

swap(result[i], result[j]);

}

void insert()

{ // insert는 2번까지의 인덱스 정렬, 3번을 추가해 정렬, 4번을 추가해 정렬 ...

copyIndex();

for (int i = 1; i<max; ++i)

for (int j = i - 1; j > -1; --j)

if (result[j] > result[j + 1])

{

swap(result[j + 1], result[j]);

}

else

break;

}

void bubble()

{ // bubble은 1,2번 비교, 2,3번 비교, 3,4번 비교 ...

copyIndex();

for (int i = max - 1; i >= 0; --i)

for (int j = 1; j <= i; ++j)

if (result[j] < result[j - 1])

swap(result[j], result[j - 1]);

}

void shell()

{ // 레코드를 분할한 다음, 분할한 간격을 띄어넘어가며 삽입 정렬.

copyIndex();

int gap = 1;

while (gap < max)

gap = gap * 3 + 1;

while (1)

{

gap = (gap - 1) / 3; // marcin ciura의 연구. 이런 식으로 나온게 가장 평균 연산 시간이 적다고 증명함.

for (int k = 0; k < gap; ++k) //k의 값은 현재 나뉘어진 그룹에서의 인덱스 순서.

for (int i = k, j, temp; i < max; i += gap) // i와 j는 값 비교용

{

temp = result[i];

j = i - gap;

while (j >= 0 && result[j] > temp)

{

result[j + gap] = result[j];

j -= gap;

}

result[j + gap] = temp;

}

if (gap <= 1)

break;

}

}

void quickCall()

{//quick함수는 재귀함수라 result값 설정 겸, max의 -1을 넣어줄 겸 그냥 만든 함수

copyIndex();

quick(0, max - 1);

}

void quick(int left, int right)

{ //가장 오른쪽 원소를 pivot으로 쓰는 case. // 코드에문제있으니 http://makefortune2.tistory.com/201 이거 보고 디버깅 해보기

int l = left, r = right-1, pvPosition = right;

if (right - left < 1)

return;

while (1)

{

while (result[l] < result[pvPosition])

++l;

while (result[r] > result[pvPosition])

--r;

if (l >= r)

break;

swap(result[l], result[r]);

}

swap(result[pvPosition], result[l]);

pvPosition = l;

quick(left, pvPosition - 1);

quick(pvPosition + 1, right);

}

void radix()

{ // https://www.cs.usfca.edu/~galles/visualization/RadixSort.html 애니메이션 참조

copyIndex();

int temp[max], count[max];

mem(count);

for (int i = 0; i < max; ++i)

++count[(result[i] % 10)];

for (int i = 0; i < max - 1; ++i)

count[i + 1] += count[i];

for (int i = max-1, j; i > -1; --i)

{

j = result[i] % 10;

temp[(--(count[j]))] = result[i];

}

mem(count);

for (int i = 0; i < max; ++i)

++count[(temp[i] / 10)];

for (int i = 0; i < max - 1; ++i)

count[i + 1] += count[i];

for (int i = max - 1, j; i > -1; --i)

{

j = temp[i] / 10;

result[(--(count[j]))] = temp[i];

}

}

void mergeCall()

{

copyIndex();

merge(result, max);

}

void merge(int *base, int n)

{ // 자잘하게 쪼갠다음에 합쳐가며 정렬

int left = n / 2, right = n - left, l = 0, r = left, *copyBase, i = 0;

if (n <= 1)

return;

merge(base, left);

merge(base + left, right);

copyBase = (int *)malloc(sizeof(int)*n);

memcpy(copyBase, base, sizeof(int)*n);

while ((l < left) && (r < n))

{

if (copyBase[l] <= copyBase[r])

base[i] = copyBase[l++];

else

base[i] = copyBase[r++];

++i;

}

while (l < left)

base[i++] = copyBase[l++];

while (r < n)

base[i++] = copyBase[r++];

free(copyBase);

}

void heap()

{

copyIndex();

int *copyHeap = (int *)malloc(sizeof(int)*(max + 1));

for (int i = 0; i < max; ++i)

{

copyHeap[i + 1] = result[i];

if(i != 0)

for (int j = i + 1; copyHeap[j / 2] > copyHeap[j]; j /= 2)

swap(copyHeap[j / 2], copyHeap[j]);

}

for (int i = 0, j; i < max; ++i)

{

j = 1;

result[i] = copyHeap[1];

copyHeap[1] = copyHeap[max - i];

while ((j * 2) < (max - i)) // child가 있을 때에만.

{

if ((j * 2) + 1 < (max - i)) // child가 둘이면 true

{

if (copyHeap[j * 2] < copyHeap[j * 2 + 1]) // 왼쪽 child이 오른쪽 child보다 작다

{

if (copyHeap[j * 2] < copyHeap[j])//왼쪽 child가 부모보다 작음

{

swap(copyHeap[j * 2], copyHeap[j]);

j *= 2;

}

else

break;

}

else if (copyHeap[j * 2 + 1] < copyHeap[j]) // 오른쪽이 왼쪽보다 작으니까 오른쪽이 부모보다 작은지 검사

{

swap(copyHeap[j * 2 + 1], copyHeap[j]);

j = j * 2 + 1;

}

else // 아니면 끝내 걍

break;

}

else if (copyHeap[j * 2] < copyHeap[j]) // child가  하나일때 부모랑 비교

{

swap(copyHeap[j * 2], copyHeap[j]);

j *= 2;

}

else

break;

}

}

free(copyHeap);

}