반응형
Q_19, Q_20 나중에 다시보기
연습문제 Q_12 > 요소의 이동 횟수를 계산할 수 있도록 버전 1과 버전 2를 수정한 프로그램을 작성하세요. 여러 가지 배열을 입력하고 프로그램을 실행하며 이동 횟수를 비교해 보세요.
버전 1
#include <stdio.h>
#include <stdlib.h>
// 셸 정렬 함수
void shell(int a[], int n) {
int i, j, h, count=0;
for(h = n/2; h > 0; h/=2) {
for(i = h; i < n; i++) {
int tmp = a[i];
for(j = i - h; j>=0 && a[j] > tmp; j-=h) {
a[j + h] = a[j];
count++;
}
a[j + h] = tmp; // a[j]가 아닌 a[j + h]인 이유는, 종료 전에 마지막으로 j-=h가 수행되기 때문.
count++;
}
}
printf("요소의 이동 횟수 : %d\n", count);
}
int main(void) {
int i, nx;
int *x;
puts("셸 정렬");
printf("요소 개수: ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] :", i);
scanf("%d", &x[i]);
}
shell(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
버전 2
#include <stdio.h>
#include <stdlib.h>
// 셸 정렬 함수(버전 2 : h = ..., 121, 40, 13, 4, 1)
void shell(int a[], int n) {
int i, j, h, count=0;
for(h = 1; h < n / 9; h = h * 3 + 1)
;
for(; h > 0; h/=3) {
for(i = h; i < n; i++) {
int tmp = a[i];
for(j = i - h; j>=0 && a[j] > tmp; j-=h) {
a[j + h] = a[j];
count++;
}
a[j + h] = tmp; // a[j]가 아닌 a[j + h]인 이유는, 종료 전에 마지막으로 j-=h가 수행되기 때문.
count++;
}
}
printf("요소의 이동 횟수 : %d\n", count);
}
int main(void) {
int i, nx;
int *x;
puts("셸 정렬");
printf("요소 개수: ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] :", i);
scanf("%d", &x[i]);
}
shell(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
연습문제 Q_13 > 아래 형식으로 동작하는 quick_sort 함수를 구현하세요. 두 번째 매개변수인 n은 요소의 개수입니다.
void quick_sort(int a[], int n);
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 퀵 정렬 함수 Q_13
void quick_sort (int a[], int n) {
int left = 0;
int right = n - 1;
int pl = left; // 왼쪽 커서
int pr = right; // 오른쪽 커서
int x = a[(pl + pr) / 2]; // 피벗은 가운데 요소로 선택
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while(pl <= pr);
if(left < pr) quick_sort(a+left, pr - left + 1);
if(pl < right) quick_sort(a+pl, right - pl + 1);
}
int main(void) {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수: ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] :", i);
scanf("%d", &x[i]);
}
quick_sort(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답 제공 : 나는 기존 left right를 인자로 받는 quicksort 함수를 아예 수정했는데, 정답에선 기존 left right를 받는 퀵소트 함수를 그대로 두고 크기값을 받는 함수를 구현한 뒤 기존 함수를 호출하는 간단한 방법을 사용.
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
//--- 퀵 정렬
void quick(int a[], int left, int right)
{
int pl = left; // 왼쪽 커서
int pr = right; // 오른쪽 커서
int x = a[(pl + pr) / 2]; // 피벗(가운데 요소 선택)
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (left < pr) quick(a, left, pr);
if (pl < right) quick(a, pl, right);
}
//--- 퀵 정렬(배열, 요솟수)
void quick_sort(int a[], int n)
{
quick(a, 0, n - 1);
}
int main(void)
{
int i, nx;
int *x;
puts("퀵 정렬");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick_sort(x, nx);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
*/
연습문제 Q_14 > 실습 6 - 10을 수정하여 푸시, 팝, 분할 과정을 출력하는 프로그램을 작성하세요.
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
#include "IntStack.h"
//퀵 정렬을 비재귀적으로 구현한 프로그램
void quick (int a[], int left, int right) {
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right-left+1);
Initialize(&rstack, right-left+1);
Push(&lstack, left);
Push(&rstack, right);
while(!IsEmpty(&lstack)) { // lstack, rstack 둘다 함께 비고 채워지므로 둘중 아무거나 하나로만 체크함
printf("Pushed:\n");
printf("lstack : {");
for(int i = 0; i < Size(&lstack); i++) {
printf("%d ", lstack.stk[i]);
}
printf("}\n");
printf("rstack : {");
for(int i = 0; i < Size(&rstack); i++) {
printf("%d ", rstack.stk[i]);
}
printf("}\n");
int pl = (Pop(&lstack, &left), left); //lstack에서 팝한 값을 left에 대입한 다음 그 left의 값을 다시 pl에 대입
int pr = (Pop(&rstack, &right), right); //rstack에서 팝한 값을 right에 대입한 다음 그 right의 값을 다시 pr에 대입
int x = a[(left + right) / 2]; // 피벗은 가운데 요소로 선택
printf("Popped:\n");
printf("lstack : {");
for(int i = 0; i < Size(&lstack); i++) {
printf("%d ", lstack.stk[i]);
}
printf("}\n");
printf("rstack : {");
for(int i = 0; i < Size(&rstack); i++) {
printf("%d ", rstack.stk[i]);
}
printf("}\n");
//과정 출력해보면 알다시피, 재귀적으로 했을떄와 다르게 뒷 그룹 문저 처리가된다. 이는 아래 if문의 Push 순서와 연관이있다.
int i;
printf("a[%d] ~ a[%d] : {", left, right);
for(i = left; i < right; i++) {
printf("%d ", a[i]);
}
printf("%d}\n", a[right]);
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while(pl <= pr);
// 순서가 현재 재귀구현때와 동일한데, 이렇게되면 둘다 참일 때 앞 그룹이 아닌 뒷 그룹부터 처리가 진행된다. 처리 순서가 바뀌는 것일 뿐 결과에는 문제가없으며 바꿔주고싶다면 if순서를 바꿔주면 되겠다.
if(left < pr) {
Push(&lstack, left);
Push(&rstack, pr);
}
if(pl < right) {
Push(&lstack, pl);
Push(&rstack, right);
}
}
Terminate(&lstack);
Terminate(&rstack);
}
int main(void) {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수: ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] :", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
연습문제 Q_15 > 실습 6-9, 6-10의 quick 함수를, 요소의 개수가 적은 그룹을 먼저 나누는 함수로 수정하세요.
15-1
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
void quick(int a[], int left, int right) {
int pl = left;
int pr = right;
int x = a[(pl + pr) / 2];
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr) {
swap(int, a[pl], a[pr]);
pl++; // 다음거로 넘기는 것
pr--; // 다음거로 넘기는 것
}
} while(pl<=pr);
if(pr - left > right - pl) { // 요소의 갯수가 많은 것부터 먼저 Push하게끔 설계 -> 스택 사용 용량을 줄일 수 있음.
if(left < pr) quick(a, left, pr);
if(pl < right) quick(a, pl, right);
} else {
if(pl < right) quick(a, pl, right);
if(left < pr) quick(a, left, pr);
}
}
int main() {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답 제공 : if문 쌍의 중복 존재를 막기 위해서 swap을 통해서 순서를 바꿔줌.
해당코드 부분
if (pr - left < right - pl) {
swap(int, pl, left);
swap(int, pr, right);
}
if (left < pr) quick(a, left, pr);
if (pl < right) quick(a, pl, right);
*/
15-2
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 비재귀적 퀵정렬
void quick(int a[], int left, int right) {
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right - left + 1);
Initialize(&rstack, right - left + 1);
Push(&lstack, left);
Push(&rstack, right);
while(!IsEmpty(&lstack)) {
int pl = (Pop(&lstack, &left), left);
int pr = (Pop(&rstack, &right), right);
int x = a[(left + right) / 2];
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl<=pr) {
swap(int, a[pl], a[pr]);
pl++; // 다음 칸으로
pr--; // 다음 칸으로
}
} while(pl <= pr);
if(pr - left > right - pl) { // 요소의 갯수가 많은 것부터 먼저 Push하게끔 설계 -> 스택 사용 용량을 줄일 수 있음.
if(left < pr) {
Push(&lstack, left);
Push(&rstack, pr);
}
if(pl < right) {
Push(&lstack, pl);
Push(&rstack, right);
}
} else {
if(pl < right) {
Push(&lstack, pl);
Push(&rstack, right);
}
if(left < pr) {
Push(&lstack, left);
Push(&rstack, pr);
}
}
}
Terminate(&lstack);
Terminate(&rstack);
}
int main() {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답제공 : 위에서와 마찬가지로, if문의 중복 필요없이 left pr pl right 값들의 swap을 통해 순서를 간단명료하게 바꿔줌.
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
//--- 퀵 정렬 (요솟수가 작은 그룹을 먼저 분할 : 비재귀 버전)
void quick(int a[], int left, int right)
{
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right - left + 1);
Initialize(&rstack, right - left + 1);
Push(&lstack, left);
Push(&rstack, right);
while (!IsEmpty(&lstack)) {
int pl = (Pop(&lstack, &left), left);
int pr = (Pop(&rstack, &right), right);
int x = a[(left + right) / 2];
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (pr - left < right - pl) {
swap(int, pl, left);
swap(int, pr, right);
}
if (left < pr) {
Push(&lstack, left);
Push(&rstack, pr);
}
if (pl < right) {
Push(&lstack, pl);
Push(&rstack, right);
}
}
}
int main(void)
{
int i, nx;
int *x;
puts("퀵 정렬");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
*/
연습문제 Q_16 > 퀵 정렬은 요소의 개수가 적은 배열에 대해서는 처리가 아주 빠르게 진행되지는 않는다고 알려져 있습니다. Q_15에서 작성한 두 quick 함수를, 나눈 그룹의 요소 개수가 9개 이하이면 단순 삽입 정렬로 동작하는 함수로 수정하세요.
16 - 1
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 단순 삽입 정렬
void insertion(int a[], int n) {
int i, j;
for(i = 1; i < n; i++) {
int tmp = a[i];
for(j = i; j > 0 && a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
void quick(int a[], int left, int right) {
int pl = left;
int pr = right;
int x = a[(pl + pr) / 2];
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr) {
swap(int, a[pl], a[pr]);
pl++; // 다음거로 넘기는 것
pr--; // 다음거로 넘기는 것
}
} while(pl<=pr);
if(pr - left > right - pl) { // 요소의 갯수가 많은 것부터 먼저 Push하게끔 설계 -> 스택 사용 용량을 줄일 수 있음.
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(left < pr && pr - left > 9) quick(a, left, pr);
else if(left < pr) insertion(a + left, pr - left + 1);
if(pl < right && pl - right > 9) quick(a, pl, right);
else if(pl < right) insertion(a + pl, right - pl + 1);
} else {
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(pl < right && pl - right > 9) quick(a, pl, right);
else if(pl < right) insertion(a + pl, right - pl + 1);
if(left < pr && pr - left > 9) quick(a, left, pr);
else if(left < pr) insertion(a + left, pr - left + 1);
}
}
int main() {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답 제공 : 15-1에서부터 내 코드보다 간단하게 작성한 탓에 변형문제도 내 코드보다 가독성이 훨씬 좋음 + 재귀호출부분에 분기문을 추가하지 않고,
함수 초반부에 분기해주면서 코드의 통일성도 높여줌.
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
//-- 단순 삽입 정렬
void insertion(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
// 퀵 정렬 (요솟수가 9개 이하면 단순 삽입 정렬로 전환 : 재귀 버전)
void quick(int a[], int left, int right)
{
if (right - left < 9)
insertion(&a[left], right - left + 1);
else {
int pl = left;
int pr = right;
int x = a[(pl + pr) / 2];
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (pr - left < right - pl) {
swap(int, pl, left);
swap(int, pr, right);
}
if (left < pr) quick(a, left, pr);
if (pl < right) quick(a, pl, right);
}
}
int main(void)
{
int i, nx;
int *x;
puts("퀵 정렬");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
*/
16 - 2
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 단순 삽입 정렬
void insertion(int a[], int n) {
int i, j;
for(i = 1; i < n; i++) {
int tmp = a[i];
for(j = i; j > 0 && a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
// 비재귀적 퀵정렬
void quick(int a[], int left, int right) {
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right - left + 1);
Initialize(&rstack, right - left + 1);
Push(&lstack, left);
Push(&rstack, right);
while(!IsEmpty(&lstack)) {
int pl = (Pop(&lstack, &left), left);
int pr = (Pop(&rstack, &right), right);
int x = a[(left + right) / 2];
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl<=pr) {
swap(int, a[pl], a[pr]);
pl++; // 다음 칸으로
pr--; // 다음 칸으로
}
} while(pl <= pr);
if(pr - left > right - pl) { // 요소의 갯수가 많은 것부터 먼저 Push하게끔 설계 -> 스택 사용 용량을 줄일 수 있음.
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(left < pr && pr - left > 9) {
Push(&lstack, left);
Push(&rstack, pr);
} else if(left < pr) {
insertion(a+left, pr - left + 1);
}
if(pl < right && right - pl > 9) {
Push(&lstack, pl);
Push(&rstack, right);
} else if(pl < right) {
insertion(a+pl, right - pl + 1);
}
} else {
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(pl < right && right - pl > 9) {
Push(&lstack, pl);
Push(&rstack, right);
} else if(pl < right) {
insertion(a+pl, right - pl + 1);
}
if(left < pr && pr - left > 9) {
Push(&lstack, left);
Push(&rstack, pr);
} else if(left < pr) {
insertion(a+left, pr - left + 1);
}
}
}
Terminate(&lstack);
Terminate(&rstack);
}
int main() {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답 제공 : 15-1에서부터 내 코드보다 간단하게 작성한 탓에 변형문제도 내 코드보다 가독성이 훨씬 좋음. + 재귀목적의 Push부분에 분기문을 추가하지 않고,
함수 초반부에 분기해주면서 코드의 통일성도 높여줌.
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
void insertion(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
void quick(int a[], int left, int right)
{
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right - left + 1);
Initialize(&rstack, right - left + 1);
Push(&lstack, left);
Push(&rstack, right);
while (!IsEmpty(&lstack)) {
int pl = (Pop(&lstack, &left), left);
int pr = (Pop(&rstack, &right), right);
int x = a[(left + right) / 2];
if (right - left < 9)
insertion(&a[left], right - left + 1);
else {
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (pr - left < right - pl) {
swap(int, pl, left);
swap(int, pr, right);
}
if (left < pr) {
Push(&lstack, left);
Push(&rstack, pr);
}
if (pl < right) {
Push(&lstack, pl);
Push(&rstack, right);
}
}
}
}
int main(void)
{
int i, nx;
int *x;
puts("퀵 정렬");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
/*
연습문제 Q_17 > 방법 1을 사용하여 Q_16의 quick 함수(재귀, 비재귀 버전)를 수정하세요.
방법 1 : 나눌 배열의 요소 개수가 3 이상이면, 임의로 3 요소를 선택하고 그 중에서 중앙값인 요소를 피벗으로 선택한다.
(처음, 중간, 끝 세 요소 선택)
17-1
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 중앙값 구하는 함수
int mid(int a, int b, int c) {
if(a >= b) {
if(b >= c)
return b;
else if(a <= c)
return a;
else
return c;
}
else if(a > c)
return a;
else if(b > c)
return c;
else
return b;
}
// 단순 삽입 정렬
void insertion(int a[], int n) {
int i, j;
for(i = 1; i < n; i++) {
int tmp = a[i];
for(j = i; j > 0 && a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
void quick(int a[], int left, int right) {
int pl = left;
int pr = right;
int x = (pr - pl + 1 >= 3)?mid(a[pr], a[pl], a[(pl+pr)/2]):a[(pl + pr) / 2];
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr) {
swap(int, a[pl], a[pr]);
pl++; // 다음거로 넘기는 것
pr--; // 다음거로 넘기는 것
}
} while(pl<=pr);
if(pr - left > right - pl) { // 요소의 갯수가 많은 것부터 먼저 Push하게끔 설계 -> 스택 사용 용량을 줄일 수 있음.
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(left < pr && pr - left > 9) quick(a, left, pr);
else if(left < pr) insertion(a + left, pr - left + 1);
if(pl < right && pl - right > 9) quick(a, pl, right);
else if(pl < right) insertion(a + pl, right - pl + 1);
} else {
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(pl < right && pl - right > 9) quick(a, pl, right);
else if(pl < right) insertion(a + pl, right - pl + 1);
if(left < pr && pr - left > 9) quick(a, left, pr);
else if(left < pr) insertion(a + left, pr - left + 1);
}
}
int main() {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답 제공: 어차피 대소비교니까 요소 3개 체크 안함.
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
//--- a, b, c 중 가운데 값을 구합니다.
int med3(int a, int b, int c)
{
if (a >= b)
if (b >= c)
return b;
else if (a <= c)
return a;
else
return c;
else if (a > c)
return a;
else if (b > c)
return c;
else
return b;
}
//--- 단순 삽입 정렬
void insertion(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
void quick(int a[], int left, int right)
{
if (right - left < 9)
insertion(&a[left], right - left + 1);
else {
int pl = left;
int pr = right;
int x = med3(a[pl], a[(pl + pr) / 2], a[pr]);
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (pr - left < right - pl) {
swap(int, pl, left);
swap(int, pr, right);
}
if (left < pr) quick(a, left, pr);
if (pl < right) quick(a, pl, right);
}
}
int main(void)
{
int i, nx;
int *x;
puts("퀵 정렬");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
*/
17-2
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 중앙값 구하는 함수
int mid(int a, int b, int c) {
if(a >= b) {
if(b >= c)
return b;
else if(a <= c)
return a;
else
return c;
}
else if(a > c)
return a;
else if(b > c)
return c;
else
return b;
}
// 단순 삽입 정렬
void insertion(int a[], int n) {
int i, j;
for(i = 1; i < n; i++) {
int tmp = a[i];
for(j = i; j > 0 && a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
// 비재귀적 퀵정렬
void quick(int a[], int left, int right) {
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right - left + 1);
Initialize(&rstack, right - left + 1);
Push(&lstack, left);
Push(&rstack, right);
while(!IsEmpty(&lstack)) {
int pl = (Pop(&lstack, &left), left);
int pr = (Pop(&rstack, &right), right);
int x = (pr - pl + 1 >= 3)?mid(a[pr], a[pl], a[(pl+pr)/2]):a[(pl + pr) / 2];
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl<=pr) {
swap(int, a[pl], a[pr]);
pl++; // 다음 칸으로
pr--; // 다음 칸으로
}
} while(pl <= pr);
if(pr - left > right - pl) { // 요소의 갯수가 많은 것부터 먼저 Push하게끔 설계 -> 스택 사용 용량을 줄일 수 있음.
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(left < pr && pr - left > 9) {
Push(&lstack, left);
Push(&rstack, pr);
} else if(left < pr) {
insertion(a+left, pr - left + 1);
}
if(pl < right && right - pl > 9) {
Push(&lstack, pl);
Push(&rstack, right);
} else if(pl < right) {
insertion(a+pl, right - pl + 1);
}
} else {
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(pl < right && right - pl > 9) {
Push(&lstack, pl);
Push(&rstack, right);
} else if(pl < right) {
insertion(a+pl, right - pl + 1);
}
if(left < pr && pr - left > 9) {
Push(&lstack, left);
Push(&rstack, pr);
} else if(left < pr) {
insertion(a+left, pr - left + 1);
}
}
}
Terminate(&lstack);
Terminate(&rstack);
}
int main() {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답 제공 : 어차피 대소비교니까 요소 3개 체크 안해줌
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
int med3(int a, int b, int c)
{
if (a >= b)
if (b >= c)
return b;
else if (a <= c)
return a;
else
return c;
else if (a > c)
return a;
else if (b > c)
return c;
else
return b;
}
void insertion(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
void quick(int a[], int left, int right)
{
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right - left + 1);
Initialize(&rstack, right - left + 1);
Push(&lstack, left);
Push(&rstack, right);
while (!IsEmpty(&lstack)) {
int pl = (Pop(&lstack, &left), left);
int pr = (Pop(&rstack, &right), right);
int x = med3(a[pl], a[(pl + pr) / 2], a[pr]);
if (right - left < 9)
insertion(&a[left], right - left + 1);
else {
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (pr - left < right - pl) {
swap(int, pl, left);
swap(int, pr, right);
}
if (left < pr) {
Push(&lstack, left);
Push(&rstack, pr);
}
if (pl < right) {
Push(&lstack, pl);
Push(&rstack, right);
}
}
}
Terminate(&lstack);
Terminate(&rstack);
}
int main(void)
{
int i, nx;
int *x;
puts("퀵 정렬");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
*/
연습문제 Q_18 > 방법 2를 사용하여 Q_16의 quick 함수(재귀, 비재귀 버전)를 수정하세요.
18-1
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 단순 삽입 정렬
void insertion(int a[], int n) {
int i, j;
for(i = 1; i < n; i++) {
int tmp = a[i];
for(j = i; j > 0 && a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
void quick(int a[], int left, int right) {
int pl = left;
int pr = right;
int x = a[(pl + pr) / 2];
if(pr - pl + 1 >= 3) {
// 여기서부터 방법 2 도입.
int z[] = {a[pl], a[pr], x};
insertion(z, 3);
a[pl] = z[0];
a[(pl + pr) / 2] = z[1];
a[pr] = z[2];
swap(int, a[(pl + pr) / 2], a[pr - 1]);
x = a[pr - 1];
pl++;
pr -=2;
// 방법 2 스캔 조정 끝
}
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr) {
swap(int, a[pl], a[pr]);
pl++; // 다음거로 넘기는 것
pr--; // 다음거로 넘기는 것
}
} while(pl<=pr);
if(pr - left > right - pl) { // 요소의 갯수가 많은 것부터 먼저 Push하게끔 설계 -> 스택 사용 용량을 줄일 수 있음.
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(left < pr && pr - left > 9) quick(a, left, pr);
else if(left < pr) insertion(a + left, pr - left + 1);
if(pl < right && pl - right > 9) quick(a, pl, right);
else if(pl < right) insertion(a + pl, right - pl + 1);
} else {
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(pl < right && pl - right > 9) quick(a, pl, right);
else if(pl < right) insertion(a + pl, right - pl + 1);
if(left < pr && pr - left > 9) quick(a, left, pr);
else if(left < pr) insertion(a + left, pr - left + 1);
}
}
int main() {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답 제공 : 마찬가지로, 요소 3개 체크 안해도 지장 없어서 안해줌 + 내 코드는 Insertion sort 사용했는데, bubble sort 기능의 sort3elem 도입하여 세 요소 정렬
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
int sort3elem(int x[], int a, int b, int c)
{
if (x[b] < x[a]) swap(int, x[b], x[a]);
if (x[c] < x[b]) swap(int, x[c], x[b]);
if (x[b] < x[a]) swap(int, x[b], x[a]);
return b;
}
void insertion(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
void quick(int a[], int left, int right)
{
if (right - left < 9)
insertion(&a[left], right - left + 1);
else {
int pl = left;
int pr = right;
int x;
int m = sort3elem(a, pl, (pl + pr) / 2, pr);
x = a[m];
swap(int, a[m], a[right - 1]);
pl++;
pr -= 2;
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (pr - left < right - pl) {
swap(int, pl, left);
swap(int, pr, right);
}
if (left < pr) quick(a, left, pr);
if (pl < right) quick(a, pl, right);
}
}
int main(void)
{
int i, nx;
int *x;
puts("퀵 정렬");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
*/
18-2
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 단순 삽입 정렬
void insertion(int a[], int n) {
int i, j;
for(i = 1; i < n; i++) {
int tmp = a[i];
for(j = i; j > 0 && a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
// 비재귀적 퀵정렬
void quick(int a[], int left, int right) {
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right - left + 1);
Initialize(&rstack, right - left + 1);
Push(&lstack, left);
Push(&rstack, right);
while(!IsEmpty(&lstack)) {
int pl = (Pop(&lstack, &left), left);
int pr = (Pop(&rstack, &right), right);
int x = a[(pl + pr) / 2];
if(pr - pl + 1 >= 3) {
// 여기서부터 방법 2 도입.
int z[] = {a[pl], a[pr], x};
insertion(z, 3);
a[pl] = z[0];
a[(pl + pr) / 2] = z[1];
a[pr] = z[2];
swap(int, a[(pl + pr) / 2], a[pr - 1]);
x = a[pr - 1];
pl++;
pr -=2;
// 방법 2 스캔 조정 끝
}
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl<=pr) {
swap(int, a[pl], a[pr]);
pl++; // 다음 칸으로
pr--; // 다음 칸으로
}
} while(pl <= pr);
if(pr - left > right - pl) { // 요소의 갯수가 많은 것부터 먼저 Push하게끔 설계 -> 스택 사용 용량을 줄일 수 있음.
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(left < pr && pr - left > 9) {
Push(&lstack, left);
Push(&rstack, pr);
} else if(left < pr) {
insertion(a+left, pr - left + 1);
}
if(pl < right && right - pl > 9) {
Push(&lstack, pl);
Push(&rstack, right);
} else if(pl < right) {
insertion(a+pl, right - pl + 1);
}
} else {
// 나눈 그룹의 요소의 개수가 9개 이하면 단순삽입정렬 시행
if(pl < right && right - pl > 9) {
Push(&lstack, pl);
Push(&rstack, right);
} else if(pl < right) {
insertion(a+pl, right - pl + 1);
}
if(left < pr && pr - left > 9) {
Push(&lstack, left);
Push(&rstack, pr);
} else if(left < pr) {
insertion(a+left, pr - left + 1);
}
}
}
Terminate(&lstack);
Terminate(&rstack);
}
int main() {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답 제공 : 마찬가지로, 요소 3개 체크 안해도 지장 없어서 안해줌 + 내 코드는 Insertion sort 사용했는데, bubble sort 기능의 sort3elem 도입하여 세 요소 정렬
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
int sort3elem(int x[], int a, int b, int c)
{
if (x[b] < x[a]) swap(int, x[b], x[a]);
if (x[c] < x[b]) swap(int, x[c], x[b]);
if (x[b] < x[a]) swap(int, x[b], x[a]);
return b;
}
void insertion(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
void quick(int a[], int left, int right)
{
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right - left + 1);
Initialize(&rstack, right - left + 1);
Push(&lstack, left);
Push(&rstack, right);
while (!IsEmpty(&lstack)) {
int pl = (Pop(&lstack, &left), left);
int pr = (Pop(&rstack, &right), right);
int x;
if (right - left < 9)
insertion(&a[left], right - left + 1);
else {
int m = sort3elem(a, pl, (pl + pr) / 2, pr);
x = a[m];
swap(int, a[m], a[right - 1]);
pl++;
pr -= 2;
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (pr - left < right - pl) {
swap(int, pl, left);
swap(int, pr, right);
}
if (left < pr) {
Push(&lstack, left);
Push(&rstack, pr);
}
if (pl < right) {
Push(&lstack, pl);
Push(&rstack, right);
}
}
}
}
int main(void)
{
int i, nx;
int *x;
puts("퀵 정렬");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
quick(x, 0, nx - 1);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
*/아무생각없이 집중안하고 멍때리면서 코딩하고 받아적다가, 긴 코드에서 정말 티도안나는 작은곳의 순서를 바꿔적어버려서 오류가 생겨 정말 한시간을 넘게 디버깅을 했다. 정말 긴 코드일수록 사막에서 바늘찾기같다는 느낌이 다시금 들었다. 그리고 코딩할땐 한땀한땀 집중해야한다는사실을.. 가끔 코드를 아무생각없이 작성하거나 받아적을때가 있는데, 이런 큰 위험에 노출될 수 있으니 항상 정신차리고 코드를 이해하면서 코딩해야겠다.
연습문제 Q_19 > 표준 라이브러리에 있는 qsort 함수를 사용하여 아래 두 배열을 오름차순으로 정렬하는 프로그램을 작성하세요. 프로그램에서 정렬하는 부분의 코드는 각각 독립적인 함수로 구현하세요.
char a[][7] = {"LISP", "C", "Ada", "Pascal"};
char *p[] = {"LISP", "C", "Ada", "Pascal"}; // 포인터변수를 담는 배열한계다.. 나중에 코드 다시보자
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//--- 문자열 배열(n1 × n2의 2차원 배열)을 오름차순으로 정렬 ---
void sort_2dstr(char *p, int n1, int n2)
{
qsort(p, n1, n2, (int(*)(const void *, const void *))strcmp);
}
//--- x, y가 가리키는 문자열 비교 함수 ---
static int pstrcmp(const void *x, const void *y)
{
return strcmp(*(const char **)x, *(const char **)y);
}
//--- 문자열을 가리키는 p를 오름차순으로 정렬 ---
void sort_pvstr(char *p[], int n)
{
qsort(p, n, sizeof(char *), pstrcmp);
}
int main(void)
{
int i;
char a[][7] = { "LISP", "C", "Ada", "Pascal" };
char *p[] = { "LISP", "C", "Ada", "Pascal" };
sort_2dstr(&a[0][0], 4, 7);
sort_pvstr(p, 4);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < 4; i++)
printf("a[%d] = %s\n", i, a[i]);
for (i = 0; i < 4; i++)
printf("p[%d] = %s\n", i, p[i]);
return 0;
}
연습문제 Q_20 > 퀵 정렬 알고리즘을 사용하여 qsort 함수와 같은 형식으로 호출할 수 있는 아래의 함수를 직접 작성하세요.
void q_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));
/*
피벗값의 자료형이 무엇인지 모르는 상태에서
int x = a[(pl+pr)/2] 처럼 할 수 없는 상황인데, 인덱스 값으로 피벗을 찾다가 메모리 교환 작업이 일어나게 되면
기존의 피벗이라고 찍었던 인덱스에 새로운 값이 들어가 있을 수 있으므로..
참고로 자료형이 정해졌을 때엔(ex int)
int x = a[(pl+pr)/2] 이런식으로 피벗'값'을 미리 구해놓음.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//--- x, y가 가리키는 n 바이트의 메모리 영역을 교환 ---
//포인터도 아닌 순수 void자료형의 값을 그대로 쓸 수 없으니까(ex. void a=1), 가장 작은 1byte인 char로 형변환하여 size만큼 복사붙여넣기 진행해줌.
static void memswap(void *x, void *y, size_t n)
{
unsigned char *a = (unsigned char *)x;
unsigned char *b = (unsigned char *)y;
for (; n--; a++, b++) {
unsigned char c = *a;
*a = *b;
*b = c;
}
}
// 비교함수는 배열 요소의 자료형에 대한 포인터를 인수로 받는 것임.
int cmp(const int *a, const int *b) {
if(*a < *b)
return -1;
else if(*a > *b)
return 1;
else
return 0;
}
void quick(void *base, int left, int right, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) {
int pl = left;
int pr = right;
// 피벗의 자료형을 알 수 없으니, 인덱스로 구해놓는 것임. 주의점은 메모리가 교환될때 피벗이 가리키는 인덱스의 위치도 바꿔줘야 한다는것.
int x = (pl + pr)/2;
do {
while(compar(base+size*pl, base+size*x) < 0) pl++;
while(compar(base+size*pr, base+size*x) > 0) pr--;
if(pl <= pr) {
//보통 피벗값을 추출해 연산하나, 현재 자료형을 알 수 없는 전제이므로 인덱스를 기반으로 피벗값을 가리키다보니, 메모리 교환이 일어났을 때 기존에 피벗이라고 가리키고 있던 메모리가 다른 값으로 들어찰 수 있으니 피벗값의 인덱스를 갖도록 바꿔줘야하는 작업이 필요함.
x = (pl == x)?pr:(pr == x)?pl:x;
memswap(base+size*pl, base+size*pr, size);
pl++;
pr--;
}
}while(pl<=pr);
if(left < pr) quick(base, left, pr, nmemb, size, compar);
if(pl < right) quick(base, pl, right, nmemb, size, compar);
}
void q_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) {
quick(base, 0, nmemb - 1, nmemb, size, compar);
}
int main() {
int i, nx;
int *x;
puts("퀵 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
q_sort(x, nx, sizeof(int), (int(*)(const void *, const void *))cmp);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답제공 : 이걸 보고 꺠달았으나, 내 방법이 더 간편한듯 ㅎ
#include <stdio.h>
#include <stdlib.h>
//--- x, y가 가리키는 n 바이트의 메모리 영역을 교환 ---
static void memswap(void *x, void *y, size_t n)
{
unsigned char *a = (unsigned char *)x;
unsigned char *b = (unsigned char *)y;
for (; n--; a++, b++) {
unsigned char c = *a;
*a = *b;
*b = c;
}
}
void q_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
{
if (nmemb > 0) {
size_t pl = 0; // 왼쪽 커서
size_t pr = nmemb - 1; // 오른쪽 커서
size_t pv = nmemb; // 피벗
size_t pt = (pl + pr) / 2; // 피벗 업데이트
char *v = (char *)base; // 첫 번째 요소에 대한 포인터
char *x; // 피벗에 대한 포인터
do {
if (pv != pt) x = &v[(pv = pt) * size];
while (compar((const void *)&v[pl * size], x) < 0) pl++;
while (compar((const void *)&v[pr * size], x) > 0) pr--;
if (pl <= pr) {
pt = (pl == pv) ? pr : (pr == pv) ? pl : pv;
memswap(&v[pl * size], &v[pr * size], size);
pl++;
if (pr == 0) // 부호가 없는 정수 0부터 1씩 감소를 피합니다.
goto QuickRight;
pr--;
}
} while (pl <= pr);
if (0 < pr) q_sort(&v[0], pr + 1, size, compar);
QuickRight:
if (pl < nmemb - 1) q_sort(&v[pl * size], nmemb - pl, size, compar);
}
}
int int_cmp(const int *a, const int *b)
{
return *a < *b ? -1 : *a > *b ? 1 : 0;
}
int main(void)
{
int i, nx;
int *x;
printf("q_sort 함수로 정렬합니다.\n");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
q_sort(x, //배열
nx, // 요솟수
sizeof(int), // 요소 하나의 크기
(int(*)(const void *, const void *))int_cmp // 비교 함수
);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
*/
연습문제 Q_21 > 병합 정렬 알고리즘을 사용해 qsort 함수와 같은 형식으로 호출할 수 있는 다음 함수를 안정된 정렬이 될 수 있도록 작성하세요.
void m_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void*));
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void *buff; // 작업용 배열
int compare(int *a, int *b) {
if(*a < *b)
return -1;
else if(*a > *b)
return 1;
else
return 0;
}
void merge_sort(void *a, int left, int right, size_t size, int(*compar)(const void *, const void *)) {
if(left < right) { // 배열 요소가 2개 이상임을 간접 의미
int center = (left + right) / 2;
int p = 0;
int i;
int j = 0;
int k = left;
merge_sort(a, left, center, size, compar);
merge_sort(a, center + 1, right, size, compar);
for(i = left; i <= center; i++) {
memcpy(buff+p*size, a+i*size, size);
p++;
}
while(i <= right && j < p) {
if(compar(buff+j*size, a+i*size) <= 0) {
memcpy(a+k*size, buff+j*size, size);
k++; j++;
} else {
memcpy(a+k*size, a+i*size, size);
k++; i++;
}
}
// i 부분은 해줄 필요가 없음. 알아서 뒤에 위치하고 있기 때문에.
while(j < p) {
memcpy(a+k*size, buff+j*size, size);
k++; j++;
}
}
}
void m_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) {
merge_sort(base, 0, nmemb - 1, size, compar);
}
int main() {
int nx = 0;
printf("요소 개수 : ");
scanf("%d", &nx);
int *x = calloc(nx, sizeof(int));
buff = calloc(nx, sizeof(int));
for(int i = 0; i < nx; i++) {
printf("x[%d] :", i);
scanf("%d", &x[i]);
}
m_sort(x, nx, sizeof(int), (int(*)(const void *, const void *))compare);
for(int i = 0; i < nx; i++) {
printf("%d ", x[i]);
}
}
/*
+ 책에서 자꾸 void *를 일단 char *로 바꾸는 이유도, 자료형이 확실치 않으니까 일단 1byte 단위인 char 포인터로 바꿔서 연산하는 듯 싶다.
int *a 가 있을 때, a + 1 은 알아서 +4byte가 되니까 이걸 1byte 기준으로 만드려고 char를 이용하는 듯 싶다. 나는 현재 void *를 그대로
쓰고있긴 한데, 이렇게 하면 아예 값의 기준이 없으므로 char *을 굳이 이용하지 않아도 된다.(같은 효과를 낼 수 있음)
+ 이건 비교하면서 메모리 이동이 일어난다 해도 비굣값에 영향이 없는 과정이므로 20번 피벗처리처럼 해줘야할건없음.
*/
연습문제 Q_22 > downheap 함수가 호출될 때마다 오른쪽 그림처럼 배열의 값을 트리 형식으로 출력하는 프로그램을 작성하세요.
// 다시는 하고 싶지 않아라... 공백 선정이 너무 대가리가 안돌아가서 정답 봤는데도 이해하는데 한참걸림. 할거많은데 개빡침 벽느낌.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define swap(type, x, y) do { type t = x; x = y; y = t;} while(0)
// a[left] ~ a[right] 를 힙으로 만드는 함수. a[left] 이외에는 모두 힙 상태라고 가정.
static void downheap (int a[], int left, int right) {
int temp = a[left]; // 루트
int child;
int parent;
// 이 인덱스를 기준으로 다음 인덱스부터는 리프노드임 -> (Right-1)/2
// (Right-1)/2 + 1 보다 작아야 리프노드가 아닌것 = (Right +1)/2보다 작아야 리프노드가 아닌것
for(parent = left; parent < (right + 1) / 2; parent = child) {
int cl = parent * 2 + 1; // 왼쪽 자식
int cr = cl + 1; // 오른쪽 자식
// 일단 리프가 아니라는것은 아니까 cr이 없으면 바로 cl로 처리.
child = (cr <= right && a[cr] > a[cl]) ? cr : cl; // 차일드 둘 중 큰 값 선택
if(temp >= a[child]) // 이미 힙 상태인 경우 (부모보다 자식의 값이 이미 작음)
break;
a[parent] = a[child];
}
a[parent] = temp; // 밀어내기 후 채우기.
}
void print_heap(int a[], int n) {
int temp = n;
int i=0; // 0부터 시작하는 height
int index = 0;
// 트리의 높이 구하는건 도저히 대가리가 안돌아가서 퍼오긴 했는데..
// 생각해보면 n층까지의 값은 1, 3, 7, 15... = 2^1 -1, 2^2 -1, 2^3 -1 이런식으로 규칙이 있음.
// 따라서 새로운 층이 만들어지는 단위는 2 4 8 16 ..인 2의 제곱이므로 간단히 생각해서 2의 제곱단위로 나눠주면서 층수를 계산하면 됨.
while(temp/=2)
i++; // 루트는 0 그다음은 1 이런식으로 계산한 높이.
for(int x = 0; x <= i; x++) {
int zz= pow(2, i + 1 - x) - 2; //시작 공백 정하기. 정답 코드와 포문 선언 방식도 다르고 높이가 0부터냐 1부터냐의 차이도 다르지만 어쨌든 공백출력 횟수가 이 기능 목적이므로, 횟수만 같게 하면 되니까 +1 해줌.
for(int s = 0; s < zz; s++) {
printf(" ");
}
for(int y = 0; y < pow(2, x) && index < n; y++) {
printf("%02d ", a[index++]);
printf("%*s", ((int)pow(2, i - x + 2) - 2), " "); // 아래 시작 공백을 사잇값으로 계산해줌
}
putchar('\n');
}
putchar('\n');
}
// 힙 정렬 함수
void heap_sort(int a[], int n) {
int i;
// 리프노드가 아닌 노드부터 루트노드까지 downheap 진행하여 힙으로 만들어줌. 근데 생각해보니 n은 크기이므로 리프노드가 아닌 노드는 (n - 1)/2가 아니라 (n - 2)/2부터인데 책의 예제에선 (n - 1)/2로 해서 쓸모없는 작업 하나 더 하더라. (+이상해서 디버깅으로 직접 확인함)
for(i = (n - 2) / 2; i >= 0; i--) {
downheap(a, i, n - 1);
print_heap(a, n);
}
// i가 0이되면 종료(힙정렬 end 조건임)
for(i = n - 1; i > 0; i--) {
swap(int, a[0], a[i]);
downheap(a, 0, i - 1);
print_heap(a, n);
}
}
int main(void) {
int i, nx;
int *x;
puts("힙 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for(i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
heap_sort(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
연습문제 Q_23 > 도수 정렬의 각 단계(for 문) 에서 배열 a, b, f의 요솟값의 변화를 출력하는 프로그램을 작성하세요.
//for문 안에서 과정을 일일이 출력했는데, 이걸 원하는건지 아니면 끝날때마다를 원하는건진 모르겠다 ㅋ
#include <stdio.h>
#include <stdlib.h>
// 도수 정렬 함수(배열의 요솟값은 0 이상 max 이하)
void fsort(int a[], int n, int max) {
int i;
int *f = calloc(max + 1, sizeof(int)); // 도수분포표 & 누적 도수
int *b = calloc(n, sizeof(int)); // 작업용 목적 배열
// step_0 (생략가능 : calloc함수가 동적으로 확보하는 메모리의 모든 값은 0으로 초기화되기 때문)
for(i = 0; i <= max; i++) f[i] = 0;
// step_1
puts("STEP 1:");
for(i = 0; i < n; i++) {
f[a[i]]++;
puts("Array F:");
for(int x = 0; x < max + 1; x++) {
printf("%d ", f[x]);
}
printf("\n\n");
}
// step_2
puts("STEP 2:");
for(i = 1; i <= max; i++) {
f[i] += f[i - 1];
puts("Array F:");
for(int x = 0; x < max + 1; x++) {
printf("%d ", f[x]);
}
printf("\n\n");
}
// step_3
puts("STEP 3:");
for(i = n - 1; i >= 0; i--) {
b[--f[a[i]]] = a[i];
puts("Array F:");
for(int x = 0; x < max + 1; x++) {
printf("%d ", f[x]);
}
printf("\n");
puts("Array B:");
for(int x = 0; x < n; x++) {
printf("%d ", b[x]);
}
printf("\n\n");
}
// step_4
puts("STEP 4:");
for(i = 0; i < n; i++) {
a[i] = b[i];
puts("Arary A:");
for(int x = 0; x < n; x++) {
printf("%d ", a[x]);
}
printf("\n\n");
}
free(b);
free(f);
}
int main() {
int i, nx;
int *x;
const int max = 100;
puts("도수 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
printf("0 ~ %d의 정수를 입력하세요.\n", max);
for(i = 0; i < nx; i++) {
do {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
} while(x[i] < 0 || x[i] > max);
}
fsort(x, nx, max);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답 제공 : 난 각 루프 단위 마다 출력했는데, 역시 그걸 원하는게 아니였음. 정답은 각 단계가끝날 때 마다 이쁘게 출력해줌
#include <stdio.h>
#include <stdlib.h>
//--- 도수 정렬 (배열 요소 값 제한: 0 ~ max) ---
void fsort(int a[], int n, int max)
{
int i;
int *f = calloc(max + 1, sizeof(int)); // 누적 도수
int *b = calloc(n, sizeof(int)); // 작업용 목적 배열
puts("\n정렬 전의 배열");
for (i = 0; i < n; i++) printf("%3d", i); putchar('\n');
for (i = 0; i < n; i++) printf("---", i); putchar('\n');
for (i = 0; i < n; i++) printf("%3d", a[i]); putchar('\n');
for (i = 0; i <= max; i++) f[i] = 0; // [Step0]
for (i = 0; i < n; i++) f[a[i]]++; // [Step1]
puts("\n도수 분포");
for (i = 0; i < max; i++) printf("%3d", i); putchar('\n');
for (i = 0; i < max; i++) printf("---", i); putchar('\n');
for (i = 0; i < max; i++) printf("%3d", f[i]); putchar('\n');
for (i = 1; i <= max; i++) f[i] += f[i - 1]; // [Step2]
puts("\n누적 도수 분포");
for (i = 0; i < max; i++) printf("%3d", i); putchar('\n');
for (i = 0; i < max; i++) printf("---", i); putchar('\n');
for (i = 0; i < max; i++) printf("%3d", f[i]); putchar('\n');
putchar('\n');
for (i = n - 1; i >= 0; i--) { // [Step3]
b[--f[a[i]]] = a[i];
printf("a[%2d]의 %2d를 b[%2d]에 저장.\n", i, a[i], f[a[i]]);
}
for (i = 0; i < n; i++) a[i] = b[i]; // [Step4]
puts("\n정렬 후의 배열");
for (i = 0; i < n; i++) printf("%3d", i); putchar('\n');
for (i = 0; i < n; i++) printf("---", i); putchar('\n');
for (i = 0; i < n; i++) printf("%3d", a[i]); putchar('\n');
free(b);
free(f);
}
int main(void)
{
int i, nx;
int *x;
const int max = 10;
puts("도수 정렬");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
printf("0 ~ %d의 정수를 입력하세요.\n", max);
for (i = 0; i < nx; i++) {
do {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
} while (x[i] < 0 || x[i] > max);
}
fsort(x, nx, max);
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
*/
연습문제 Q_24 > 요솟값의 범위가 min 이상 max 이하이고 요소의 개수가 n개인 배열 a를 도수 정렬하는 함수를 작성하세요.
#include <stdio.h>
#include <stdlib.h>
// 도수 정렬 함수 (배열의 요솟값 범위는 min 이상 max 이하, 요소의 개수는 n개)
void fsort2(int a[], int n, int min, int max) {
int i;
int *f = calloc(max - min + 1, sizeof(int));
int *b = calloc(n, sizeof(int));
// 추가된 제일 중요한 작업. 일단 min값으로 모두 빼줘. 기준값 생성. 나중에 다시 더해주면 돼
for(i = 0; i < n; i++) {
a[i] -= min;
}
//step_0(f의 요소 0으로 초기화해주는 작업) 생략. 어차피 calloc으로 할당받은 메모리는 모두 0으로 초기화되므로.
for(i = 0; i < n; i++) f[a[i]]++; //
for(i = 1; i <= max - min; i++) f[i] += f[i - 1];
for(i = n - 1; i >=0; i--) b[--f[a[i]]] = a[i];
for(i = 0; i < n; i++) a[i] = b[i];
free(b);
free(f);
// 추가된 제일 중요한 작업. 빼줬던 min을 다시 더해줌.
for(i = 0; i < n; i++) {
a[i] += min;
}
/*
배열 a의 증감( +-min)없이 아래 방법(f배열에서 증감처리하여 a에는 영향없게)도 있음
for (i = 0; i < n; i++) f[a[i] - min]++;
for (i = 1; i <= max - min; i++) f[i] += f[i - 1];
for (i = n - 1; i >= 0; i--) b[--f[a[i] - min]] = a[i];
for (i = 0; i < n; i++) a[i] = b[i];
*/
}
int main() {
int i, nx;
int *x;
int min = 0;
int max = 0;
puts("도수 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
printf("요소 최솟값 : ");
scanf("%d", &min);
printf("요소 최댓값 : ");
scanf("%d", &max);
printf("%d ~ %d의 정수를 입력하세요.\n", min, max);
for(i = 0; i < nx; i++) {
do {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
} while(x[i] < min || x[i] > max);
}
fsort2(x, nx, min, max);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i < nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
정답 제공 : 아무리 생각해도 정답이 틀렸다. 나는 도수분포/누적도수 용 배열을 max - min + 1 크기만큼 할당하는게 맞다고 생각하는데, 정답에서는 max - min + 2 만큼 할당한다.
3~47이라고 보면, 3 - 3 ~ 47 - 3 = 0 ~ 44로 생각하게 되는 것이니, 예제에서처럼 0 이상 44 이하의 경우엔 45개를 선언해서 0~44 점수를 담을 배열을 만드는게 맞다. 최댓값에 해당하는 인덱스가 존재해야하는 이유 때문.
근데 연습문제 정답 코드에서는 한 칸을 더 받음.
+ 분석결과 제공된 정답이 틀림-> 디버깅해보니 마지막 값이 아예 쓰이지도 않고 불필요함.
*/
공부 내용 정리
셸 정렬
셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬 알고리즘이다.
정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법이다.
여러 개의 그룹으로 나누어 정렬하는 이유는 단순 삽입 정렬의 장점은 살리고 단점은 보완하기 위해서다.
정렬해야 하는 횟수는 늘지만 전체적으로는 요소 이동의 횟수가 줄어들어 효율적인 정렬을 할 수 있다.
셸 정렬 과정에서 h칸만큼 떨어진 요소를 모아 그룹을 h개로 나누어 수행하는 각각의 정렬을 'h-정렬'이라고 합니다.
코드
// 셸 정렬 함수
void shell(int a[], int n) {
int i, j, h;
for(h = n/2; h > 0; h/=2) {
for(i = h; i < n; i++) {
int tmp = a[i];
for(j = i - h; j>=0 && a[j] > tmp; j-=h) {
a[j + h] = a[j];
}
a[j + h] = tmp; // a[j]가 아닌 a[j + h]인 이유는, 종료 전에 마지막으로 j-=h가 수행되기 때문.
}
}
}
멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않다.
셸 정렬의 시간복잡도 : 간격에 따라 O(n^1.25) ~ O(n^1.5)
∙ 셸 정렬 개선 방안
증분값 h가 서로 배수인 경우엔, 그룹을 나누면서도 항상 겹치는 그룹과 겹치지 않는 그룹으로 나뉜다.
그룹이 점점 세세하게 나눠지는 동안 절대 섞이지 않는 그룹이 있다는 것.
(결국 h=1*2n인 그룹A와 h = 2n 그룹 B안에서 각각 따로 놀기에 h=1이 올 때와 맨 처음 때의 그룹의 구성요소가 같기에 1-정렬 때 비효율적일 수 있다 )
따라서 증분값 h값이 서로 배수가 되지 않도록 해주면 좋다. 이렇게 하면 요소가 충분히 섞여 효율적인 정렬을 기대할 수 있다.
h = ..., 121, 40, 13, 4, 1
이 수열을 거꾸로 살펴보면 1부터 시작해서 3배한 값에 1을 더하는 수열이라는 것을 알 수 있다. 또 h 초깃값은 너무 크면 효과가 없기 때문에 요소 개수 n을 9로 나눈 값을 넘지 않도록 정해야 한다.
코드
// 셸 정렬 함수(버전 2 : h = ..., 121, 40, 13, 4, 1)
void shell(int a[], int n) {
int i, j, h;
for(h = 1; h < n / 9; h = h * 3 + 1)
;
for(; h > 0; h/=3) {
for(i = h; i < n; i++) {
int tmp = a[i];
for(j = i - h; j>=0 && a[j] > tmp; j-=h) {
a[j + h] = a[j];
}
a[j + h] = tmp; // a[j]가 아닌 a[j + h]인 이유는, 종료 전에 마지막으로 j-=h가 수행되기 때문.
}
}
}
퀵 정렬
퀵 정렬은 가장 빠른 정렬 알고리즘 중 하나로 널리 사용되고 있다.
먼저 전체에서 데이터값 하나(A)를 선택한다. 그리고 A를 기준으로 A보다 큰 그룹과 작은 그룹으로 나눈다. 이때 A(그룹을 나누는 기준)를 피벗(pivot)이라고 한다. 퀵 정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬을 마친다.
ps. 피벗은 마음대로 선택할 수 있고, 피벗은 왼쪽 그룹과 오른쪽 그룹 어디에 들어가도 상관없다.
∙ 구현
배열 a가 있다.
왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr이라고 하고 가운데 요소를 피벗 x라 둔다.
1. a[pl] >= x 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 옮긴다.
2. a[pl] <= x 가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 옮긴다.
두 경우를 찾으면 두 요소를 교환한다.
그렇게 pl <= pr 일때까지 이를 반복한다.
반복이 끝나면 pl > pr 상태가 되고, 데이터는 아래 두 그룹으로 나누어진다.
피벗 이하의 그룹 : a[0], ..., a[pl - 1]
피벗 이상의 그룹 : a[pr + 1], ..., a[n - 1]
또한 만약 pl > pr + 1인 경우에는 다음과 같은 그룹이 생긴다.
피벗과 일치하는 값을 가지는 그룹 : a[pr + 1], ..., a[pl - 1]
+ 이 그룹(가운데 그룹)이 생기는 원리
-> 피벗값 기준으로 각각 왼쪽 오른쪽에 더이상 피벗보다 큰/작은 값이 없다는것 = 피벗값의 지금 위치가 정렬된 위치가 맞다는것.
그리고 이 분할과정을 반복하면 되는데,
요소의 개수가 1개인 그룹은 더 이상 그룹을 나눌 필요가 없으므로 요소의 개수가 2개 이상인 그룹만 나누면 된다. 따라서 아래처럼 데이터를 반복해서 나눈다.
1. pr이 a[0]보다 오른쪽에 있으면(= left<pr) 왼쪽 그룹을 나눈다.
2. pl이 a[8]보다 왼쪽에 있으면( = pl<right) 오른쪽 그룹을 나눈다.
+ 이는 그룹의 개수가 1개가 아닌 경우에만 그룹을 나누는 조건이다.
+ 가운데 그룹(a[pr + 1] ~ a[pl - 1])은 나눌 필요가 없으므로 분할 대상에서 제외된다.
결국 피벗과 일치하는 값을 갖는 그룹은 다룰 필요가 없으므로, pl <= pr 까지 반복 이후에
left < pr일때 left ~ pr을 또 새로 그룹으로 나눠 반복하고
pl < right일때 pl ~ right을 또 새로 그룹으로 나눠서 반복한다.
+ 이전에 피벗 이하/이상의 그룹을 나눠주는 방식(a[0]~a[pl-1], a[pr+1]~a[n-1])은 피벗과 일치하는 값을 가지는 그룹(a[pr+1]~a[pl-1])이 생기는 경우엔 그룹을 나누기가 애매해진다.
가운데 그룹이 생기지 않으면 잘 분할되지만 가운데 그룹이 생기면 제대로 분할되지 않는 것이다. 하지만 가운데그룹이 생기던 안생기던 상관없이 그룹이 잘 나뉘게 동작하도록 해줘야한다.
따라서 가운데그룹이 생기는 경우에도 문제없이 진행되도록 그룹나누기를 해줘야하므로, a[0] ~ a[pl - 1]과 a[pr + 1] ~ a[n - 1]로 바라볼 것이 아니라 a[0] ~ a[pr]과 a[pl] ~ a[n - 1]로 바라보는 것(참고로 a[0] = left, a[n - 1] = right). 이렇게 해주면 가운데그룹의 발생유무에 상관없이 그룹나누기가 잘 진행된다. (가운데발생x 일땐 피벗값이 두 그룹중 하나로 된 상태로 그룹이 잘 나뉘어지고, 가운데발생o일땐 가운데그룹이 분할대상에서 제외되어 잘 나뉘어짐)
코드
// 퀵 정렬 함수
void quick (int a[], int left, int right) {
int pl = left; // 왼쪽 커서
int pr = right; // 오른쪽 커서
int x = a[(pl + pr) / 2]; // 피벗은 가운데 요소로 선택
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while(pl <= pr);
if(left < pr) quick(a, left, pr);
if(pl < right) quick(a, pl, right);
}
퀵 정렬의 시간복잡도 : O(n log n)
다만 정렬할 배열의 초깃값이나 피벗의 선택 방법에 따라 시간복잡도가 증가하는 경우도 있다.
퀵 정렬은 서로 이웃하지 않고 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않다.
퀵 정렬 비재귀적으로 구현
코드
//퀵 정렬을 비재귀적으로 구현한 프로그램
void quick (int a[], int left, int right) {
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right-left+1);
Initialize(&rstack, right-left+1);
Push(&lstack, left);
Push(&rstack, right);
while(!IsEmpty(&lstack)) { // lstack, rstack 둘다 함께 비고 채워지므로 둘중 아무거나 하나로만 체크함
int pl = (Pop(&lstack, &left), left); //lstack에서 팝한 값을 left에 대입한 다음 그 left의 값을 다시 pl에 대입
int pr = (Pop(&rstack, &right), right); //rstack에서 팝한 값을 right에 대입한 다음 그 right의 값을 다시 pr에 대입
int x = a[(left + right) / 2]; // 피벗은 가운데 요소로 선택
//과정 출력해보면 알다시피, 재귀적으로 했을떄와 다르게 뒷 그룹 문저 처리가된다. 이는 아래 if문의 Push 순서와 연관이있다.
int i;
printf("a[%d] ~ a[%d] : {", left, right);
for(i = left; i < right; i++) {
printf("%d ", a[i]);
}
printf("%d}\n", a[right]);
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while(pl <= pr);
// 순서가 현재 재귀구현때와 동일한데, 이렇게되면 둘다 참일 때 앞 그룹이 아닌 뒷 그룹부터 처리가 진행된다. 처리 순서가 바뀌는 것일 뿐 결과에는 문제가없으며 바꿔주고싶다면 if순서를 바꿔주면 되겠다.
if(left < pr) {
Push(&lstack, left);
Push(&rstack, pr);
}
if(pl < right) {
Push(&lstack, pl);
Push(&rstack, right);
}
}
Terminate(&lstack);
Terminate(&rstack);
}
비재귀적으로 구현할 때, 그룹을 나누고 나서 요소의 개수가 많은 그룹을 먼저 스택에 푸시하도록 동작하게 하면(요소의 개수가 적은 그룹이 먼저 실행됨) 실행과정에서 스택에 쌓여 있는 데이터의 최대 개수를 줄일 수 있다(이 경우, 요소 개수가 n일때 스택에 쌓이는 데이터의 최대 개수는 log n보다 적게됨).
+ int a = (1, 2)의 동작은 int a = 1; a = 2;와 같다.
따라서 위 코드에선 int pl = Pop(&lstack, left); pl = left;로 동작하게되는데, 딱히 이렇게 해야할 필요가 있는지는 의문..!
+ 퀵 정렬은 요소의 개수가 적은 배열에 대해서는 처리가 아주 빠르게 진행되지는 않는다고 알려져 있다. 요소의 개수가 일정 개수 이하이면 단순삽입정렬로 동작하게 하면 좋다.
∙ 피벗 선택
피벗 선택 방법은 퀵 정렬의 실행 효율에 큰 영향을 준다. 배열 내의 크기가 중간값인 값을 피벗으로 하면 배열의 크기가 균등하게 그룹이 나누어지므로 빠른 정렬로 이어질 수 있다. 하지만 가운데 값을 구하고자 할 경우 그에 대한 처리가 필요하고 이 처리에 대해 많은 계산 시간이 요구되어 배보다 배꼽이 커진다. 이런 문제를 해결하기 위해 다음의 방법을 사용하면 적어도 최악의 경우는 피할 수 있다.
나눌 배열의 요소 개수가 3 이상이면 임의로 3 요소를 선택하고 그중에서 중앙값인 요소를 피벗으로 선택한다.
이 아이디어를 조금 더 발전시킨 방법은 다음과 같다.
나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두 번째 요소를 교환한다. 피벗으로 끝에서 두 번째 요소의 값(a[right - 1]을 선택하여 나눌 대상의 범위를 a[left + 1] ~ a[right - 2]로 좁힌다.
이렇게 되면 스캔하기 위한 커서의 시작 위치는 아래와 같이 변경되어, 나눌 대상의 범위가 좁아집니다
1. 왼쪽 커서 pl의 시작 위치
left -> left + 1
2. 오른쪽 커서 pr의 시작 위치
right -> right - 2
이 방법은 나눌 그룹의 크기가 한쪽으로 치우치는 것을 피하면서도 나눌 때 스캔할 요소를 3개씩 줄일 수 있다는 장점이 있습니다. 이 방법을 사용하지 않을 때보다는 조금 더 빠른 속도로 정렬할 수 있습니다.
+ 피벗을 어느 위치에서 선택하느냐는 상관없이, pl pr 값을 이용한 비교-교환 작업을 하고 나면 그 피벗값 이하인 그룹과 이상인 그룹(피벗은 둘 중 하나의 그룹 또는 가운데그룹으로)으로 나뉘게 된다. 따라서 중간값을 선택하면 배열이 균등하게 나눠져 좋은것.
∙ 표준 라이브러리 qsort 함수
헤더 : #include <stdio.h>
형식 : void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));
설명 : base는 정렬할 배열, nmemb는 요소의 개수, size는 배열 요소의 크기, compar는 비교 함수.
compar에 전달할 비교 함수는 다음과 같은 기능을 할 수 있도록 직접 작성해야 한다. 첫 번째 인수가 두 번째 인수보다 작은 경우에는 0보다 작은 값을, 같을 경우에는 0을, 클 경우에는 0보다 큰 정수를 반환합니다(오름차순 기준).
qsort 함수는 bsearch 함수와 마찬가지로 int형이나 double 형 등의 배열뿐만 아니라 구조체형 배열 등의 모든 자료형의 배열에 적용할 수 있다. 함수 이름은 퀵 정렬에서 따왔지만 내부적으로 항상 퀵 정렬 알고리즘을 사용하지는 않는다.
그리고 이또한 정렬이 안정적이지 않다.
병합 정렬
병합 정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘
∙ 병합
정렬을 마친 배열 a, b가 있을때 새로운 배열 c를 선언한다. 그리고 각 배열마다 0부터 시작하는 커서변수를 두고, 배열 a와 b의 커서에 해당하는 요소들을 비교하며 배열 c의 커서에 해당하는 위치로 넣어주고 커서값들을 조정하며 이 작업을 반복한다. 배열 a 또는 b의 커서가 배열끝에 도달했을경우 이 작업을 종료하고, a 또는 b의 커서를 기준으로 아직 배열끝에 도착하지 못한 인덱스의 값을을 전부 배열c로 옮겨준다.
병합에 필요한 시간복잡도 : O(n)
+ 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다.
∙ 병합 정렬 알고리즘 순서 정리
배열의 요소 개수가 2개 이상인 경우
1. 배열의 앞부분을 병합 정렬로 정렬한다.
2. 배열의 뒷부분을 병합 정렬로 정렬한다.
3. 배열의 앞부분과 뒷부분을 병합한다.
코드_1
// 내가 만든 merge_sort
void merge_sort(int a[], int n, int c[]) {
int mid = (n - 1) / 2;
if(n >= 2) {
merge_sort(a, mid + 1, c);
merge_sort(a + mid + 1, n -(mid + 1), c);
int pa = 0, pb = mid + 1, pc = 0;
while(pa <= mid && pb <= n - 1) {
a[pa] <= a[pb] ? (c[pc++]=a[pa++]):(c[pc++]=a[pb++]);
}
while(pa<=mid)
c[pc++] = a[pa++];
while(pb<=n-1)
c[pc++] = a[pb++];
for(int x = 0; x < n ; x++) {
a[x] = c[x];
}
//free(c);
}
}
코드_2
static int *buff;
void __merge_sort(int a[], int left, int right) {
if(left < right) {
int p = 0;
int i;
int j = 0;
int k = left;
int center = (left + right) / 2;
__merge_sort(a, left, center);
__merge_sort(a, center+1, right);
for(i = left; i <= center; i++) {
buff[p++] = a[i];
}
while(i <= right && j < p) {
a[k++] = (buff[j] <= a[i])?buff[j++]:a[i++];
}
while(j < p) {
a[k++] = buff[j++];
}
}
}
int merge_sort(int a[], int n) {
if((buff=calloc(n, sizeof(int))) == NULL)
return -1;
__merge_sort(a, 0, n - 1);
free(buff);
return 0;
}
병합 정렬은 서로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬 방법이다.
(서로 교환안하니까 안정적이라고생각하면될듯)
배열 병합의 시간복잡도는 O(n)이고 데이터의 요소 개수가 n개일 때 병합 정렬의 단계는 log n만큼 필요하므로 전체 시간복잡도는 O(n log n)이다.
힙 정렬
선택 정렬을 응용한 알고리즘인 힙 정렬(heap sort)은 힙(heap)의 특성을 이용하여 정렬을 수행한다.
∙ 힙
'부모의 값이 자식의 값보다 항상 크다' 라는 조건을 만족하는 완전이진트리다. 이때 부모의 값이 자식보다 항상 작아도 힙이라고 합니다. (최대 힙/최소 힙)
+ 힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않아서 '부분순서트리'라고도 한다
∙ 완전 이진 트리
완전 : 부모는 자식을 왼쪽부터 추가하는 모양 유지
이진 : 부모가 가질 수 있는 자식의 개수는 최대 2개
∙ 힙의 요소를 배열에 저장
힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 사이에 다음과 같은 관계가 성립한다.
1. 부모는 a[(i - 1) / 2]
2. 왼쪽 자식은 a[i * 2 + 1]
3. 오른쪽 자식은 a[i * 2 + 2]
∙ 힙 정렬 과정
힙 정렬은 가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘이다. 힙에서 가장 큰 값인 루트를 꺼내고 힙을 다시 재구성하는 작업을 반복한다.
1. 루트를 꺼낸다.
2. 마지막 요소를 루트로 이동한다.
3. 자기보다 큰 값을 가지는 자식 요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복한다. 이때 자식의 값이 작거나 잎에 다다르면 작업이 종료됨.
∙ 힙 정렬 알고리즘 by 배열
1. 배열 a[0]를 꺼내 배열 마지막 요소 a[n-1]와 바꾼다
2. 가장 큰 값을 a[n-1]로 옮기면 a[n-1]은 정렬을 마친 상태가 된다. 이제 a[0] ~ a[n-2]의 요소를 힙으로 만든다.
3. a[0] 을 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[n-2]와 바꾼다.
4. 두번째로 큰 값을 a[n-2]로 옮기면 a[n-2] ~ a[n-1]는 정렬을 마치게 된다. 그런 다음 a[0] ~ a[n-3]의 요소를 힙으로 만든다.
이런 과정을 반복하면 된다. 위를 간단히 정리하면 아래와 같다.
a. 변수 i의 값을 n - 1로 초기화
b. a[0]와 a[i]를 바꾼다.
c. a[0], a[1], ... , a[i - 1]을 힙으로 만든다.
d. i의 값을 1씩 줄여 0이 되면 끝, 그렇지 않으면 b로 돌아감.
+ 적용하기 전에 초기 배열이 우선 힙 상태여야 함 주의
∙ 배열로 힙 만들기
아랫부분의 작은 부분트리부터 시작해 올라가는 방식(bottom-up)으로 전체 배열을 힙으로 만들 수 있다.
힙 정렬 전체 코드
#define swap(type, x, y) do { type t = x; x = y; y = t;} while(0)
// a[left] ~ a[right] 를 힙으로 만드는 함수. a[left] 이외에는 모두 힙 상태라고 가정.
static void downheap (int a[], int left, int right) {
int temp = a[left]; // 루트
int child;
int parent;
// 이 인덱스를 기준으로 다음 인덱스부터는 리프노드임 -> (Right-1)/2
// (Right-1)/2 + 1 보다 작아야 리프노드가 아닌것 = (Right +1)/2보다 작아야 리프노드가 아닌것
for(parent = left; parent < (right + 1) / 2; parent = child) {
int cl = parent * 2 + 1; // 왼쪽 자식
int cr = cl + 1; // 오른쪽 자식
// 일단 리프가 아니라는것은 아니까 cr이 없으면 바로 cl로 처리.
child = (cr <= right && a[cr] > a[cl]) ? cr : cl; // 차일드 둘 중 큰 값 선택
if(temp >= a[child]) // 이미 힙 상태인 경우 (부모보다 자식의 값이 이미 작음)
break;
a[parent] = a[child];
}
a[parent] = temp; // 밀어내기 후 채우기.
}
// 힙 정렬 함수
void heap_sort(int a[], int n) {
int i;
// 리프노드가 아닌 노드부터 루트노드까지 downheap 진행하여 힙으로 만들어줌. 근데 생각해보니 n은 크기이므로 리프노드가 아닌 노드는 (n - 1)/2가 아니라 (n - 2)/2부터인데 책의 예제에선 (n - 1)/2로 해서 쓸모없는 작업 하나 더 하더라. (+이상해서 디버깅으로 직접 확인함)
for(i = (n - 2) / 2; i >= 0; i--) {
downheap(a, i, n - 1);
}
// i가 0이되면 종료(힙정렬 end 조건임)
for(i = n - 1; i > 0; i--) {
swap(int, a[0], a[i]);
downheap(a, 0, i - 1);
}
}
downheap 함수
배열 a 가운데 a[left] ~ a[right]의 요소를 힙으로 만드는 함수. a[left] 이외에는 모두 힙 상태라고 가정하고 a[left]를 아랫부분의 알맞은 위치로 옮겨 힙 상태를 만든다.
heapsort 함수
요소의 개수가 n인 배열 a를 힙정렬한다.
1. downheap을 사용해 배열 a를 힙으로 만든다.
(배열로 힙 만들기)
2. 루트에 있는 가장 큰 값을 빼내어 배열 마지막 요소와 바꾸고 배열의 나머지 부분을 다시 힙으로 만드는 과정을 반복하여 정렬 수행.
(힙 정렬 알고리즘 by 배열)
다시 말하지만, 힙 정렬은 단순 선택 정렬을 응용한 알고리즘이다. 그리고 역시나 안정적이지 않은 정렬이다.
힙 정렬의 시간복잡도 : O(n log n)
+ downheap의 for문 조건식 추가설명
right는 마지막 인덱스 인자다. 그의 부모는 (Right - 1) / 2이고, 완전이진트리 특징 상 그의 부모를 기준으로 다음 인덱스부터는 리프노드다.
-> 인덱스 (Right-1)/2 를 기준으로 다음 인덱스부터는 리프노드임
-> (Right-1)/2 + 1 보다 작아야 리프노드가 아닌것
= (Right +1)/2보다 작아야 리프노드가 아닌것
+ printf("%*s", 5, ""); = printf("%5s", ""); = 공백개수 지정 역할
도수 정렬
도수 정렬은 요소의 대소관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘
도수 정렬 알고리즘은 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4 단계로 이루어집니다.
∙ 도수분포표 만들기
10점 만점의 점수에서, 학생 9명을 대상으로 a[9] 배열을 만들어 점수를 넣습니다.
도수분포표를 나타내기 위해 새로운 배열 b[10]을 사용합니다.
먼저 배열b의 모든 요소의 값을 0으로 초기화한 다음 배열 a를 스캔하면서 점수에 해당하는 배열b의 인덱스의 요소값을 증가시킴.
for(i = 0; i < n; i++)
b[a[i]]++;
∙ 누적도수분포표 만들기
도수분포표를 만든 다음 '0점부터 점수 n까지 몇 명의 학생이 있는지' 누적된 값을 나타내는 누적도수분포표를 만든다.
for(i = 1; i <= max; i++)
b[i] += b[i - 1];
∙ 목적 배열 만들기
배열 a와 같은 요소의 개수를 갖는 작업용 배열 c가 필요하다. 배열 a의 요소를 마지막 위치부터 처음 위치까지 스캔하면서 배열 b와 대조하는 작업을 수행
for(i = n - 1; i >=0; i--)
c[--b[a[i]]] = a[i];
- 어려운 점
뒤에서부터 배열을 도는 만큼 누적도수분포표의 현재 요소값 A를 A번째로 보고, 배열 c의 A번째인 A-1인덱스에 넣어서 같은 값이 있어도 순서대로 유지되게끔 하여 안정적 정렬로 이끌어낸다.
∙ 배열 복사하기
정렬을 마친 배열 c의 내용을 배열 a로 복사
for(i = 0; i < n; i++)
a[i] = b[i];
도수 정렬 알고리즘 코드
// 도수 정렬 함수(배열의 요솟값은 0 이상 max 이하)
void fsort(int a[], int n, int max) {
int i;
int *f = calloc(max + 1, sizeof(int)); // 도수분포표 & 누적 도수
int *b = calloc(n, sizeof(int)); // 작업용 목적 배열
// step_0 (생략가능 : calloc함수가 동적으로 확보하는 메모리의 모든 값은 0으로 초기화되기 때문)
for(i = 0; i <= max; i++) f[i] = 0;
// step_1
for(i = 0; i < n; i++) f[a[i]]++;
// step_2
for(i = 1; i <= max; i++) f[i] += f[i - 1];
// step_3
for(i = n - 1; i >= 0; i--) b[--f[a[i]]] = a[i];
// step_4
for(i = 0; i < n; i++) a[i] = b[i];
free(b);
free(f);
}
각 for문 단계에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값에 대해서 순서가 바뀌는 일이 없어 이 정렬 알고리즘은 안정적이라고 할 수 있다.
도수정렬은 if문 대신 for문만을 사용해 정렬할 수 있는 매우 아름다운 알고리즘이다.
도수 정렬 알고리즘 시간복잡도 : O(n)
도수 정렬 알고리즘은 데이터의 비교, 교환 작업이 필요 없어 매우 빠릅니다. 단일 for문만을 사용하며 재귀 호출, 이중 for문 없이 아주 효율적인 알고리즘입니다. 하지만 도수분포표가 필요하기에 데이터의 최솟값과 최댓값을 미리 알고있는 경우에만 사용할 수 있다.
출처 - '자료구조와 함께 배우는 알고리즘 입문 C언어편' 도서
반응형
'[알고리즘 + 자료구조] > [Do it 자료구조와 함께 배우는 알고리즘]' 카테고리의 다른 글
| [알고리즘] Do it 자료구조와 알고리즘 8장 정리 & KMP, BM 다시보기 (0) | 2020.12.24 |
|---|---|
| [알고리즘] Do it 자료구조와 알고리즘 7장 정리 (0) | 2020.12.06 |
| [알고리즘] Do it 자료구조와 알고리즘 5장 정리 (0) | 2020.10.28 |
| [알고리즘] Do it 자료구조와 알고리즘 4장 정리 (0) | 2020.10.15 |
| [알고리즘] Do it 자료구조와 알고리즘 3장 정리 (0) | 2020.10.11 |
