연습문제_Q1 > 버블정렬의 각 패스에서 비교, 교환의 시작은 왼쪽 오른쪽 상관이 없다. 오름차순의 정렬일 경우에 왼쪽부터 시행하면 각 패스에서 가장 큰 값의 요소가 오른쪽 끝으로 옮겨지는 것이고, 오른쪽부터 시행하면 각 패스에서 가장 작은 값 요소가 왼쪽 끝으로 옮겨지는 것이다. 왼쪽부터 시행한 경우의 프로그램을 작성하세요
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 뒤에서 앞으로 검사 & 오름차순. 기존
void bubble(int a[], int n)
{
int i, j;
for(i = 0; i < n - 1; i++) {
for(j = n - 1; j > i; j--) {
if(a[j - 1] > a[j])
swap(int, a[j - 1], a[j]);
}
}
}
//앞에서 뒤로 검사 & 오름차순. Q_1
void bubble2(int a[], int n)
{
int i, j;
for(i = 0; i < n - 1; i++) {
for(j = 0; j < n - 1 - i; j++) {
if(a[j] > a[j + 1])
swap(int, a[j], a[j + 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]);
}
bubble2(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i< nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
아래는 제공된 정답. 내 답은 바깥포문은 이전과 그대로 일치시키고도 가능하다는 것을 보여준 것이고, 이 답은 바깥포문부터 변형시켜줌. 둘다상관없음.
void bubble(int a[], int n)
{
int i, j;
for (i = n - 1; i > 0; i--) {
for (j = 0; j < i; j++)
if (a[j] > a[j + 1])
swap(int, a[j], a[j + 1]);
}
}
*/
연습문제_Q2 > 비교, 교환 과정을 자세히 출력하면서 버블 정렬을 수행하는 프로그램을 작성하세요. 두 요소 사이에 교환을 수행하면 '+' 그렇지 않으면 '-'를 출력하고 정렬을 마치면 비교 횟수와 교환 횟수를 출력하세요.
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 뒤에서 앞으로 검사 & 오름차순 & 과정 출력
void bubble(int a[], int n)
{
int i, j, z, y, co = 0,ch = 0;
for(i = 0; i < n - 1; i++) {
printf("패스 %d:\n", i+1);
for(j = n - 1; j > i; j--) {
for(int z = 0; z < j - 1; z++) {
printf("%d ", a[z]);
}
if(a[j - 1] > a[j]) {
printf("%d + %d ", a[j - 1], a[j]);
swap(int, a[j - 1], a[j]);
ch++;
}
else {
printf("%d - %d ", a[j - 1], a[j]);
}
co++;
for(y = j + 1; y < n; y++) {
printf("%d ", a[y]);
}
putchar('\n');
}
// 각 패스가 끝난 뒤엔 결과를 한번 보여줌
for(z = 0; z < n; z++) {
printf("%d ", a[z]);
}
putchar('\n');
}
printf("비교를 %d회 했습니다.\n교환을 %d회 했습니다.\n", co, ch);
}
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]);
}
bubble(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i< nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
연습문제_Q3 > 버블 정렬(버전2=패스에서 시도한 교환횟수가 0일 경우 정렬을 종료)의 아이디어는 배열이 정렬을 마쳤는지를 검사하는 데 응용할 수 있다. 전달받은 배열 a가 오름차순으로 정렬을 마쳤는지 검사하는 함수를 작성하세요. 오름차순으로 정렬을 마친 상태라면 1, 그렇지 않으면 0을 반환하도록 작성하세요.
#include <stdio.h>
#include <stdlib.h>
// 배열이 정렬을 마쳤는지 확인하는 함수
int is_sorted(const int a[], int n) {
int i;
for(i = n - 1; i > 0; i--) {
if(a[i - 1] > a[i]) {
return 0; // 바로 0 리턴
}
}
return 1; // 리턴되지 않았을 경우 리턴 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]);
}
is_sorted(x, nx)?printf("정렬"):printf("비정렬");
free(x);
return 0;
}
연습문제_Q4 > 버블 정렬(버전2)을 Q2 처럼 비교, 교환 과정을 자세히 출력하는 프로그램으로 수정하세요.
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 뒤에서 앞으로 검사 & 오름차순 & 과정 출력 & 패스 단위 멈춤 도입
void bubble(int a[], int n)
{
int i, j, z, y, co = 0,ch = 0;
for(i = 0; i < n - 1; i++) {
int exchg = 0;
printf("패스 %d:\n", i+1);
for(j = n - 1; j > i; j--) {
for(int z = 0; z < j - 1; z++) {
printf("%d ", a[z]);
}
if(a[j - 1] > a[j]) {
printf("%d + %d ", a[j - 1], a[j]);
swap(int, a[j - 1], a[j]);
ch++;
exchg++;
}
else {
printf("%d - %d ", a[j - 1], a[j]);
}
co++;
for(y = j + 1; y < n; y++) {
printf("%d ", a[y]);
}
putchar('\n');
}
for(z = 0; z < n; z++) {
printf("%d ", a[z]);
}
putchar('\n');
if(exchg == 0) {
puts("정렬을 미리 마칩니다.");
break;
}
}
printf("비교를 %d회 했습니다.\n교환을 %d회 했습니다.\n", co, ch);
}
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]);
}
bubble(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i< nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
연습문제_Q5 > 버블정렬(버전3 = 마지막으로 교환을 수행한 위치를 저장하고 그 앞쪽은 정렬되어있으니 불필요하게 작업하지 않음)을 Q2와 마찬가지로 비교, 교환 과정을 자세히 출력하는 프로그램으로 수정하세요.
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 뒤에서 앞으로 검사 & 오름차순 & 과정 출력 & 패스 내부 멈춤 도입
void bubble(int a[], int n)
{
int j, z, y, co = 0,ch = 0;
int k = 0; // a[k] 보다 앞쪽의 요소는 정렬을 마친 상태입니다. ( 본래 버블정렬에서 바깥포문 변수가 그런 뜻을 내포함)
int p = 0; // 패스 횟수
while(k < n - 1) {
printf("패스 %d:\n", ++p);
int last = n - 1; //패스에서 교환을 하게 되면 값이 바뀌겠고, 교환을 하지 않게 되면 k = n-1 그대로가 되면서 정렬됨을 뜻하고 작업종료.
for(j = n - 1; j > k; j--) {
for(int z = 0; z < j - 1; z++) {
printf("%d ", a[z]);
}
if(a[j - 1] > a[j]) {
printf("%d + %d ", a[j - 1], a[j]);
swap(int, a[j - 1], a[j]);
last = j;
ch++;
}
else {
printf("%d - %d ", a[j - 1], a[j]);
}
co++;
for(y = j + 1; y < n; y++) {
printf("%d ", a[y]);
}
putchar('\n');
}
for(z = 0; z < n; z++) {
printf("%d ", a[z]);
}
putchar('\n');
k = last;
}
printf("비교를 %d회 했습니다.\n교환을 %d회 했습니다.\n", co, ch);
}
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]);
}
bubble(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i< nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
연습문제_Q6 > 버블정렬(버전3)을 사용해도 효율의 효과가 없는 경우가 생길 수 있다. 이런 경우의 극복을 위해선 홀수 번째의 패스는 가장 작은 요소를 맨 앞으로 옮기고, 짝수 번째 패스는 가장 큰 요소를 뒤로 옮기는 방식(패스의 스캔 방향을 교대로 바꾸는 방식)을 사용하면 된다. 버전3의 프로그램을 개선하여 '양방향 버블 정렬'을 수행하는 프로그램을 작성하세요.
+ 추가로 개인적으로 과정출력도 더해줬음.
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 오름차순 & 과정 출력 & 패스 내부 멈춤 도입 & 양방향 버블 정렬(칵테일 정렬, 쉐이커 정렬)
void bubble(int a[], int n)
{
int z, y, co = 0,ch = 0;
int p = 0;
int left = 0;
int right = n - 1;
int last = right; // 여기서도 마찬가지의 의미로 작동해줌.
while(left < right) {
int j;
printf("패스 %d:\n", ++p);
for (j = right; j > left; j--) { // 가장 작은 요소를 맨 앞으로
for(int z = 0; z < j - 1; z++) {
printf("%d ", a[z]);
}
if(a[j - 1] > a[j]) {
printf("%d + %d ", a[j - 1], a[j]);
swap(int, a[j - 1], a[j]);
last = j;
ch++;
}
else {
printf("%d - %d ", a[j - 1], a[j]);
}
co++;
for(y = j + 1; y < n; y++) {
printf("%d ", a[y]);
}
putchar('\n');
}
// 패스 다끝나고 확인차
for(z = 0; z < n; z++) {
printf("%d ", a[z]);
}
putchar('\n');
left = last;
if(left >= right) // 3번째에 끝났을 경우엔 아래 코드가 전부 작동하지 않도록 ( 과정 출력 도중에, 아래 포문이 작동하지 않더라도 패스 출력문이나 전체출력문이 출력되어서, 여기서도 while문의 탈출조건을 넣어줬음.
break;
printf("패스 %d:\n", ++p);
for(j = left; j < right; j++) { // 가장 큰 요소를 맨 뒤로
for(int z = 0; z < j; z++) {
printf("%d ", a[z]);
}
if(a[j] > a[j + 1]) {
printf("%d + %d ", a[j], a[j + 1]);
swap(int, a[j], a[j + 1]);
last = j;
ch++;
}
else {
printf("%d - %d ", a[j], a[j + 1]);
}
co++;
for(y = j + 2; y < n; y++) {
printf("%d ", a[y]);
}
putchar('\n');
}
// 패스 다끝나고 확인차
for(z = 0; z < n; z++) {
printf("%d ", a[z]);
}
putchar('\n');
right = last;
}
printf("비교를 %d회 했습니다.\n교환을 %d회 했습니다.\n", co, ch);
}
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]);
}
bubble(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i< nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
연습문제_Q7 > 요소의 교환 과정을 자세하게 출력할 수 있도록 단순 선택 정렬 프로그램을 수정하세요. 정렬하지 않은 부분의 첫 번째 요소 위에는 기호 *를, 정렬하지 않은 부분의 가장 작은 값의 요소 위에는 기호 +를 출력하세요.
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 단순 선택 정렬 & 과정 출력
void selection(int a[], int n) {
int i, j, z, y;
for(i = 0; i < n - 1; i++) {
int min = i;
for(z = 0; z < min; z++) {
printf(" ");
} printf(" *");
for(j = i + 1; j < n; j++) {
if(a[j] < a[min])
min = j;
}
// z가 *의 위치로 되어있으니, +1로 그다음위치부터 현재 min보다 작을때까지 공백으로 채워줌.
for(y = z + 1; y < min; y++) {
printf(" ");
} printf(" +\n");
for(int x = 0; x < n; x++) {
printf("%2d", a[x]);
}
putchar('\n');
swap(int, a[i], a[min]); // 이렇게 하면 min == i 일 경우에도 실행은 되나 제자리 이동이므로 결과는 같음 (오히려 두 값이 다를 때에만 적용하게 비교하는 구문을 삽입하는게 전체 프로그램의 효율을 떨어뜨릴 수도 있음)
}
}
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]);
}
selection(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i< nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
제공된 정답 : 조건식?A:B를 중첩으로 써서 훨씬 가독성 좋게 구현했음.
내 방법은 *이나 + 출력 전까지 공백을 채우고, *나 +를 따로 출력하는 과정을 일일이 가졌는데
정답의 방법은 이를 한번에 해결
//--- 단순 선택 정렬(정렬 과정 출력)---
//void selection(int a[], int n)
//{
// int i, j, m;
//
// for (i = 0; i < n - 1; i++) {
// int min = i;
// for (j = i + 1; j < n; j++)
// if (a[j] < a[min])
// min = j;
// for (m = 0; m < n; m++)
// printf((m == i) ? " * " : (m == min) ? " + " : " ");
// putchar('\n');
//
// for (m = 0; m < n; m++)
// printf("%3d ", a[m]);
// putchar('\n');
//
// swap(int, a[i], a[min]);
// }
// putchar('\n');
// for (m = 0; m < n; m++)
// printf("%3d ", a[m]);
// putchar('\n');
//}
*/
연습문제_Q8 > 요소의 삽입 과정을 자세하게 출력할 수 있도록 단순 삽입 정렬 프로그램을 수정하세요. 현재 선택한 요소 아래에 기호 +, 삽입하는 위치의 요소 아래에 기호 ^, 그 사이에 기호 -를 출력하세요. 삽입하지 않는 경우에는 선택한 요소 아래에 +만 출력하면 됩니다.
#include <stdio.h>
#include <stdlib.h>
// 단순 삽입 정렬 함수 & 과정 출력
void insertion(int a[], int n) {
int i, j, z, y;
for(i = 1; i < n; i++) {
for(z = 0; z < n; z++) {
printf("%2d ", a[z]);
} putchar('\n');
int tmp = a[i];
for(j = i; j > 0 && a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
if(i!=j) { // 삽입 결과가 제자리가 아닌 경우
for(z = 0; z < j; z++) {
printf(" ");
}
printf("^--");
for(y = z+1; y < i; y++) {
printf("---");
}
printf("-+");
} else { // 변화 없이 제자리인 경우
for(z = 0; z < i; z++) {
printf(" ");
}
printf(" +");
}
putchar('\n');
a[j] = tmp;
}
// 마지막으로 정리한거 출력
for(int k = 0; k<n; k++) {
printf("%2d ", a[k]);
} putchar('\n');
}
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]);
}
insertion(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i< nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
//제공된 정답은 딱히.
연습문제_Q9 > 단순 삽입 정렬에서 배열의 첫 번째 요소(a[0])부터 데이터를 저장하지 않고 a[1] 부터 데이터를 저장하면 a[0]을 보초로 하여 삽입을 마치는 조건을 줄일 수 있다. 이를 기반으로 프로그램을 작성하세요.
#include <stdio.h>
#include <stdlib.h>
// 단순 삽입 정렬 함수 & 보초법 적용(main함수 내용과 연관있음)
void insertion(int a[], int n) {
int i, j;
for(i = 2; i < n; i++) {
int tmp = a[i];
for(j = i; a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
int main() {
int i, nx;
int *x;
puts("단순 삽입 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
nx++;
x = calloc(nx, sizeof(int));
x[0] = -1; // -1 값을 보초로 넣어놓음. 마이너스인 값을 넣어서 insertion함수에서 배열 범위를 벗어나는 체크를 할 필요가 없게 만들어줌.
for(i = 1; i < nx; i++) {
printf("x[%d] : ", i-1);
scanf("%d", &x[i]);
}
insertion(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 1; i< nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
/*
제공된 정답 : main 함수 안에서 보초를 지정하지도 않아서 독립적이여서 좋고, 보초값으로 나 자신을 매번 선택함으로써 배열 안에 어떤 값들이 있던 신경쓰지않아도됌.
내 경우엔 가장작은 수를 -1로 임의지정하여 배열안의 수들은 그보다 크다는 전제의 코드.
#include <stdio.h>
#include <stdlib.h>
void insertion(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[0] = a[i]; // 아예 현재 값을 보초값으로 넣어버림
for (j = i; a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
a[j] = tmp; // if(j)로 감싸있었는데, 필요없는 코드인 것 같아 지워버림. if(j)가 false가 되려면 j가 0이되어야하고, 그뜻은 인덱스 0과 다른 인덱스간의 교환이 있다는건데 a[0] = a[i] 이므로 그런 경우는 절대 없지.
}
}
int main(void)
{
int i, nx;
int *x;
puts("단순 삽입 정렬");
printf("요솟수 : ");
scanf("%d", &nx);
x = calloc(nx + 1, sizeof(int)); //a[0]를 보초로 사용하기 때문에 n + 1개의 배열을 생성
for (i = 1; i < nx + 1; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
insertion(x, nx + 1);
puts("오름차순으로 정렬했습니다.");
for (i = 1; i < nx + 1; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x);
return 0;
}
*/
연습문제_Q10 > 단순 삽입 정렬은 배열의 요소 개수가 많아지면 많아질수록 요소 삽입에 필요한 비교, 대입 비용이 무시할 수 없을 정도로 커집니다. 이때 배열에서 이미 정렬된 부분은 이진 검색을 사용할 수 있기 때문에 삽입할 위치를 더 빨리 찾을 수 있습니다. 이진 검색을 사용하여 프로그램을 수정하세요. => 이진 삽입 정렬을 구현하세요.
#include <stdio.h>
#include <stdlib.h>
// 이진 검색 + 단순 삽입 정렬 = 이진 삽입 정렬(binary insertion sort). 안정적이지 않은 알고리즘.
void insertion(int a[], int n) {
int i;
for(i = 1; i < n; i++) {
int tmp = a[i];
// 아래 if문을 만족하지 않을 경우엔 그냥 값을 그대로 냅둠. 책의 이전 예제들처럼 제자리 교환작업(i = j일 때, int tmp = a[i]; a[j] = tmp;)을 불필요하게 수행하지 않음.
if(a[i - 1] > tmp){
int pl = 0; // 검색 범위 맨 앞의 인덱스
int pr = i - 1; // 검색 범위 맨 끝의 인덱스
int pc; // 검색 범위 가운데의 인덱스
do {
pc = (pl + pr) / 2;
if(a[pc] == tmp) { // 같은값이 있을 때
// 흐름을 들어가보니, pl <= pr 을 만족하지 못하고 while문이 종료될 때 pl 자리가 값이 들어갈 자리더라(pl or pr+1). 난 pl로 지정하기로 했으니 여기서도 pl에 넣어줌.
pl = pc; break;
}
else if(a[pc] < tmp)
pl = pc + 1;
else
pr = pc - 1;
} while(pl <= pr);
//분석해보니 while문이 탈출될 때의 pl값이 tmp값이 들어갈 자리인 것을 알게됌. // pl or pr+1
for(int z=i; z > pl; z--) {
a[z] = a[z-1];
}
a[pl] = tmp; // 책의 이전 예제들과 달리 내 코드는 교환작업이 필요한 이 if문 안에서만 코드를 넣음으로써, a[i - 1] > tmp 가 아닐 경우엔 불필요한 제자리 체인지를 안해줌.
}
}
}
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]);
}
insertion(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i< nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
//제공된 정답은 pc 자리가 아닌 pc+1자리에 넣는다는 것(동일한 값을 찾았을 때 앞에 넣는지 뒤에 넣는지 차이)과
//pl 대신 pr + 1을 사용한다는 것(pl<=pr로 인해 while문을 탈출하게 될 때 pl(=pr+1)자리가 들어갈 자리이다.)이 내 코드와 다를 뿐, 결과는 동일하다.
연습문제_Q11 > Q10알고리즘은 삽입할 위치의 검색은 빠르지만, 삽입을 위해 요소를 하나씩 뒤쪽으로 미는 작업 비용이 단순 삽입 정렬 알고리즘과 같다. 요소를 뒤쪽으로 미는 작업을 memmove함수를 사용하여 구현하면 비용을 줄일 수 있다. 이를 토대로 구현하세요.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 이진 검색 + 단순 삽입 정렬 = 이진 삽입 정렬(binary insertion sort). 안정적이지 않은 알고리즘.
void insertion(int a[], int n) {
int i;
for(i = 1; i < n; i++) {
int tmp = a[i];
// 아래 if문을 만족하지 않을 경우엔 그냥 값을 그대로 냅둠. 책의 이전 예제들처럼 제자리 교환작업(i = j일 때, int tmp = a[i]; a[j] = tmp;)을 불필요하게 수행하지 않음.
if(a[i - 1] > tmp){
int pl = 0; // 검색 범위 맨 앞의 인덱스
int pr = i - 1; // 검색 범위 맨 끝의 인덱스
int pc; // 검색 범위 가운데의 인덱스
do {
pc = (pl + pr) / 2;
if(a[pc] == tmp) { // 같은값이 있을 때
// 흐름을 들어가보니, pl <= pr 을 만족하지 못하고 while문이 종료될 때 pl 자리가 값이 들어갈 자리더라(pl or pr+1). 난 pl로 지정하기로 했으니 여기서도 pl에 넣어줌.
pl = pc; break;
}
else if(a[pc] < tmp)
pl = pc + 1;
else
pr = pc - 1;
} while(pl <= pr);
//분석해보니 while문이 탈출될 때의 pl값이 tmp값이 들어갈 자리인 것을 알게됌. // pl or pr+1
memmove(a+pl+1, a+pl, sizeof(int)*(i-pl)); // 메모리단위의 데이터 이동 함수, for문을 통해 요소를 뒤쪽으로 미는 작업보다 비용이 적지만 결과는 동일하여 좋음. memmove(dest, src, size) 형식을 갖는다.
a[pl] = tmp; // 책의 이전 예제들과 달리 내 코드는 교환작업이 필요한 이 if문 안에서만 코드를 넣음으로써, a[i - 1] > tmp 가 아닐 경우엔 불필요한 제자리 체인지를 안해줌.
}
}
}
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]);
}
insertion(x, nx);
puts("오름차순으로 정렬했습니다.");
for(i = 0; i< nx; i++) {
printf("x[%d] = %d\n", i, x[i]);
}
free(x);
return 0;
}
공부 내용 정리
정렬
이름, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업.
∙ 오름차순 정렬
키 값이 작은 데이터를 앞쪽에 놓아 정렬
∙ 내림차순 정렬
키 값이 큰 데이터를 앞쪽에 놓아 정렬
정렬 알고리즘의 안정성
∙ 안정된 정렬
같은 키 값인 요소의 순서가 정렬 전후에도 유지되는 정렬
내부 정렬과 외부 정렬
∙ 내부 정렬
정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘
∙ 외부 정렬
정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘
정렬 알고리즘의 핵심 요소 3가지
교환, 선택, 삽입
버블 정렬
이웃한 두 요소의 대소 관계를 비교하여 교환을 반복
+ 앞에서 뒤로 / 뒤에서 앞으로 순서를 정할 수 있다.
∙ 큰 틀
for(i = 0; i < n - 1; i++) {
/*
이 포문 안에서 a[i], a[i+1], ... a[n-1]에 대해
끝에서부터 앞쪽으로 스캔하면서 이웃하는
두 요소를 비교하고 교환하는 작업을 구상
*/
}
∙ 과정
6 4 3 7 1 9 8 배열을 오름차순으로 정렬할 예정이다. 뒤에서부터 작업한다.
요소의 개수가 n인 배열에서 처음 n-1회 비교, 교환 작업을 거치고 나면 가장 작은 요소가 맨 처음으로 이동한다. 이런 일련의 과정을 패스라고 한다. 이후 맨 앞 요소를 고정시키고, 위 패스를 수행한다(n-2회. 패스를 수행할 때마다 정렬할 요소가 하나씩 줄어들기 때문). 패스를 k회 수행하면 앞쪽의 요소 k개가 정렬된다는 것을 알 수 있고, 따라서 모든 정렬이 끝나려면 n-1회의 패스가 수행되어야 한다. 그리고 각 k번째 패스에서는 n - k 번의 작업을 수행한다.
+ 수행하는 패스의 횟수가 n회가 아니라 n-1회인 것은 n-1개 요소의 정렬이 끝나면 마지막 요소는 이미 끝에 놓이기 때문
+ 버블 정렬이라는 말은 액체 안의 공기방울이 위로 올라오는 모습에서 유래
∙ 버블 정렬 코드
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
void bubble(int a[], int n)
{
int i, j;
for(i = 0; i < n-1; i++) {
//아래 포문이 패스
for(j = n-1; j > i; j--) {
if(a[j-1] > a[j])
swap(int, a[j-1], a[j]); //교환작업
}
}
}
서로 이웃한 요소에 대해서만 교환하므로 이 정렬 알고리즘은 안정적이다.
비교 횟수는 첫 번째 패스는 n-1회, 두 번째 패스는 n-2회... 1회 이므로 합계는 n(n-1)/2.
실제 요소를 교환하는 횟수는 배열의 요솟값에 더 많이 영향을 받기 때문에(교환을 안할 수도 있음) 교환 횟수의 평균값은 비교 횟수의 절반인 n(n-1)/4.
또한 swap 함수 안에서 값의 이동이 3회 발생하므로 이동 횟수의 평균은 3n(n-1)/4.
버블 정렬 시간 복잡도 : O(n^2)
버블 정렬 알고리즘 개선 (1)
한 패스에서 요소의 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 뜻이기 때문에 정렬 작업을 멈추게 하여 이후의 불필요한 작업을 갖지 않는다.
∙ 코드
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
void bubble(int a[], int n)
{
int i, j;
for(i = 0; i < n-1; i++) {
//아래 포문이 패스
int exchg=0; //패스에서 시도한 교환 횟수
for(j = n-1; j > i; j--) {
if(a[j-1] > a[j]) {
swap(int, a[j-1], a[j]); //교환작업
exchg++;
}
}
if(exchg == 0) break; // 교환이 수행되지 않으면 정렬 멈춤.
}
}
버블 정렬 알고리즘 개선 (2)
패스에서 비교 , 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태인 것. 다음 패스부터는 그 요소들을 제외한 요소들에서만 비교, 교환을 수행하도록 하면 됨.
∙ 코드
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
void bubble(int a[], int n)
{
int k = 0; // a[k]보다 앞쪽의 요소는 정렬을 마친 상태. 본래 버블정렬에서 바깥포문의 변수가 그런 뜻을 내포.
while(k < n - 1) { //본래 버블정렬에서 바깥포문이 k는 0부터 n-2까지 바꾸면서 패스의 수행횟수 의미도 있겠지만, k가 정렬된 데이터의 개수 또는 어느인덱스까지 검사할지를 나타낼 수도 있음.
int j;
int last = n - 1; // 마지막으로 교환을 수행한 위치를 저장하는 변수.
// 아래 포문이 패스
for(j = n - 1; j > k; j--) {
if(a[j - 1] > a[j]) {
swap(int, a[j - 1], a[j]);
last = j;
}
}
k = last; // 마지막으로 교환을 수행한 위치까지 패스가 돌게끔 지정
}
}
버블 정렬 알고리즘 개선(3)
개선(2) + 홀수 번째 패스는 가장 작은 요소를 맨 앞으로, 짝수 번째 패스는 가장 큰 요소를 맨 뒤로 하여 패스의 스캔 방향을 교대로 바꿈
= 양방향 버블 정렬 = 칵테일 정렬 = 쉐이커 정렬
∙ 코드
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
/*--- 양방향 버블 정렬(셰이커 정렬) ---*/
void shaker(int a[], int n)
{
int left = 0;
int right = n - 1;
int last = right;
while (left < right) {
int j;
for (j = right; j > left; j--) {
if (a[j - 1] > a[j]) {
swap(int, a[j - 1], a[j]);
last = j;
}
}
left = last;
for (j = left; j < right; j++) {
if (a[j] > a[j + 1]) {
swap(int, a[j], a[j + 1]);
last = j;
}
}
right = last; // 여기서 left==right 나오면 바로끝나지만, 첫번째 포문에서 나오면 불필요하게 이 문구를 한번 더 가짐(같은값끼리 교환)
}
}
단순 선택 정렬(straight selection sort)
가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘.
아직 정렬하지 않는 부분에서 값이 가장 작은 요소를 선택하고, 아직 정렬하지 않은 부분의 첫 번째 요소와 교환한다. 이 과정을 n - 1회 반복한다.
∙ 큰 틀
for(i = 0; i < n - 1; i++) {
/*
min = a[i], ..., a[n - 1]에서 가장 작은 값을 갖는 요소의 인덱스
a[i]와 a[min]의 값을 교환
*/
}
∙ 코드
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
// 단순 선택 정렬
void selection(int a[], int n)
{
int i, j;
for(i = 0; i < n - 1; i++) {
int min = i; // 최솟값을 찾기 전에 기준값 역할 + 이 위치에 최솟값이 들어갈 자리(범위 내의 가장 앞자리)
for(j = i+1; j < n; j++) {
if(a[j] < a [min])
min = j;
}
swap(int, a[i], a[min]); // i == min 일 경우 불필요하게 실행되긴 함.
}
}
서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않다.
요솟값을 비교하는 횟수는 n(n-1)/2회
( 안쪽 포문 동작을 보면 바깥쪽 포문에 대해 j에 따라 n-1, n-2, ....1회)
단순 선택 정렬 시간 복잡도 : O(n^2)
단순 삽입 정렬(straight insertion sort)
선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입 하는' 작업을 반복하여 정렬하는 알고리즘. 단순 선택 정렬과 비슷하게 보일 수 있지만 단순 선택 정렬은 값이 가장 작은 요소를 선택에 알맞은 위치로 옮긴다는 점이 다르다.
아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입한다. 이 작업을 n - 1회 반복하면 정렬을 마치게 된다.
+ 단순 삽입 정렬은 2번째 요소부터 선택하여 진행한다.
∙ 큰 틀
for(i = 1; i < n; i++) { //i = 1, 두 번째 요소를 기준으로 잡음
/*
tmp = a[i]
a[0], ..., a[i - 1]의 알맞은 곳에 tmp를 삽입한다.
*/
}
∙ 코드
// 단순 삽입 정렬
void insertion(int a[], int n)
{
int i, j;
for(i = 1; i < n; i++) {
int tmp = a[i];
// 정렬된 열 안에서 요소가 tmp보다 큰 경우 밀어내기 반복
for(j = i; j > 0 && a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
단순 삽입 정렬 알고리즘은 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적이다.
요소의 비교 횟수와 교환 횟수는 n^2/2회.
단순 삽입 정렬 시간 복잡도 : O(n^2)
+ 버블 정렬 / 단순 선택 정렬 / 단순 삽입 정렬 세 알고리즘의 시간복잡도는 모두 O(n^2)이다.
Q. 왜 단순 선택 정렬처럼 n(n-1)/2가 아닌진 모르겠음. 그리고 비교문이 두개라 교환횟수랑도 달라야 하지 않나..
-> 다른곳들 알아보니 단순 삽입 정렬의 비교, 교환 횟수도 n(n-1)/2라고 나와있음. 어쨌든 시간복잡도적인 면에선 동일한 값.
단순 삽입 정렬 알고리즘 개선 (1)
배열의 첫 번째 요소(a[0])부터 데이터를 저장하지 않고 a[1]부터 데이터를 저장하면 a[0]을 보초로 하여 삽입을 마치는 조건을 줄일 수 있다. - 보초법 도입
∙ 코드
// 단순 삽입 정렬 & 보초법
void insertion(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int tmp = a[0] = a[i];
for (j = i; a[j - 1] > tmp; j--) {
a[j] = a[j - 1];
}
a[j] = tmp; // 설명에 if(j)로 감싸져있었는데, j가 0인 경우는 실행되는 없으므(j=1일때 a[0] > tmp가 성립이 안되므로 무조건 탈출)로 쓸데없는 것 같아서 지움.
}
}
단순 삽입 정렬 알고리즘 개선 (2)
단순 삽입 정렬은 배열의 요소 개수가 많아지면 많아질수록 요소 삽입에 필요한 비교, 대입 비용이 무시할 수 없을 정도로 커진다.
이때 배열에서 이미 정렬된 부분은 이진 검색을 사용할 수 있다. - 이진 삽입 정렬 (안정적이지 않은 알고리즘)
∙ 코드
// 단순 삽입 정렬 + 이진 검색 = 이진 삽입 정렬(binary insertion sort). 안정적이지 않은 알고리즘(이진검색이 들어가서).
void insertion(int a[], int n) {
int i;
for(i = 1; i < n; i++) {
int tmp = a[i];
// 아래 if문을 만족하지 않을 경우엔 그냥 값을 그대로 냅둠. 책의 이전 예제들처럼 제자리 교환작업(i = j일 때, int tmp = a[i]; a[j] = tmp;)을 불필요하게 수행하지 않음.
if(a[i - 1] > tmp){
int pl = 0; // 검색 범위 맨 앞의 인덱스
int pr = i - 1; // 검색 범위 맨 끝의 인덱스
int pc; // 검색 범위 가운데의 인덱스
do {
pc = (pl + pr) / 2;
if(a[pc] == tmp) { // 같은값이 있을 때
// 흐름을 들어가보니, pl <= pr 을 만족하지 못하고 while문이 종료될 때 pl 자리가 값이 들어갈 자리더라(pl or pr+1). 난 pl로 지정하기로 했으니 여기서도 pl에 넣어줌.
pl = pc; break;
}
else if(a[pc] < tmp)
pl = pc + 1;
else
pr = pc - 1;
} while(pl <= pr);
//분석해보니 while문이 탈출될 때의 pl값이 tmp값이 들어갈 자리인 것을 알게됌. // pl or pr+1
//밀어내는 작업
for(int z=i; z > pl; z--) {
a[z] = a[z-1];
}
// 참고로, 밀어내는 작업을 memmove를 쓰면 더 비용이 절감됨
// memmove(a+pl+1, a+pl, sizeof(int)*(i-pl)); 메모리단위의 데이터 이동 함수, for문을 통해 요소를 뒤쪽으로 미는 작업보다 비용이 적지만 결과는 동일하여 좋음. memmove(dest, src, size) 형식을 갖는다.
a[pl] = tmp; // 책의 이전 예제들과 달리 내 코드는 교환작업이 필요한 이 if문 안에서만 코드를 넣음으로써, a[i - 1] > tmp 가 아닐 경우엔 불필요한 제자리 체인지를 안해줌.
}
}
}
출처 - 'Do it 자료구조와 함께 배우는 알고리즘 C언어편' 도서
'[알고리즘 + 자료구조]' 카테고리의 다른 글
| [알고리즘] 단순 선택 정렬 (Straight Selection Sort) (0) | 2020.11.09 |
|---|---|
| [알고리즘] 버블 정렬/Bubble Sort - 2 (+ 양방향 버블 정렬) (0) | 2020.11.09 |
| [알고리즘] 8퀸 문제 (0) | 2020.11.04 |
| [알고리즘] 하노이의 탑 (0) | 2020.11.04 |
| [ 알고리즘 ] 유클리드 호제법 (0) | 2020.11.04 |