Bermudez C Chapter 5 P 2: Using Arrays or Loops in Ascending Order
Walking through the Bermudez C programming tutorial (addition to King King's book) and puzzled by the second question of chapter 5 (Selection statements).
The problem is this: write a program that reads five values and writes them in ascending order.
The very novice programmer is not allowed to use arrays or loops. The only available tools are the "if" and "switch" statements.
Here's my problem: I solved the problem with brute force - it's super inelegant. I suppose I must be upset about this exercise; that is, perhaps Bermudez wants to show the reader what to do 5! permutations when they solely rely on if and / or switch statements.
Another (and probably more likely) guess is that I am doing something really wrong. Something tells me that I can cut this code at least in half.
Any suggestions?
Code link here (warning: 1) brute force apologies and 2) consider all refund statements ... I was lost in brackets):
source to share
This can be really cheating, but it can be done with a small piece of code in the Sorting Net .
#include <stdio.h>
int main()
{
int a, b, c, d, e, temp;
printf("Program 5.2: Ascending Order of Values\n");
printf("======================================\n\n");
printf("Enter first value: ");
scanf("%d", &a);
printf("Enter second value: ");
scanf("%d", &b);
printf("Enter third value: ");
scanf("%d", &c);
printf("Enter fourth value: ");
scanf("%d", &d);
printf("Enter fifth value: ");
scanf("%d", &e);
printf("\nRe-arranged in ascending order: \n");
printf("===============================\n\n");
/* Sorting Network - 9 comparators */
if (a > b) { temp = a; a = b; b = temp; } // 0,1
if (d > e) { temp = d; d = e; e = temp; } // 3,4
if (c > e) { temp = c; c = e; e = temp; } // 2,4
if (c > d) { temp = c; c = d; d = temp; } // 2,3
if (a > d) { temp = a; a = d; d = temp; } // 0,3
if (a > c) { temp = a; a = c; c = temp; } // 0,2
if (b > e) { temp = b; b = e; e = temp; } // 1,4
if (b > d) { temp = b; b = d; d = temp; } // 1,3
if (b > c) { temp = b; b = c; c = temp; } // 1,2
printf("%d %d %d %d %d\n", a, b, c, d, e);
return 0;
}
source to share
I have an algorithm, but it cheats recursion.
it uses stack O(n)
and O(n^2)
time complexity.
#include <stdio.h>
#include <stdbool.h>
bool sorted;
void sort(int a, int b, int c, int d, int e) {
if (sorted) return;
if (a <= b && b <= c && c <= d && d <= e) {
printf("%d %d %d %d %d\n", a, b, c, d, e);
sorted = true;
} else {
if (a > b) sort(b, a, c, d, e);
if (b > c) sort(a, c, b, d, e);
if (c > d) sort(a, b, d, c, e);
if (d > e) sort(a, b, c, e, d);
}
}
int main() {
sorted = false;
sort(5, 4, 2, 3, 1);
return 0;
}
About the BF algorithm, perhaps when comparing two numbers, time can lead to some simplicity. Many algorithms lead to tree traversal, there are many efficiency factors such as pruning, branch selection, etc.
UPD
So, for this very problem, there are general situations 5!=120
. So 120 if else
could solve this problem ...
if (a <= b && b <= c && c <= d && d <= e)...
else (b <= a && b <= c && c <= d && d <= e)...
source to share
My solution is not as elegant as @Blastfurnace's, but I thought you just have to compare each item with all the others and solve its final location using a comparison (sort of like quicksort). This is still quite a lot of code, but I think it is easier to understand and simplify ...
Time complexity: n * (n-1) [count] + n ^ 2 [switch] == 2 * (n ^ 2) - n <n! [for large numbers (eg 5 :))] space complexity: n [initial variables] + n [count] + n [first, second ...] = 3n
int main()
{
int a,b,c,d,e;
scanf("%d",&a);
scanf("%d",&b);
scanf("%d",&c);
scanf("%d",&d);
scanf("%d",&e);
int a_count = 0;
int b_count = 0;
int c_count = 0;
int d_count = 0;
int e_count = 0;
int first,second,third,fourth,fifth;
if(a>b)
++a_count;
if(a>c)
++a_count;
if(a>d)
++a_count;
if(a>e)
++a_count;
if(b>a)
++b_count;
if(b>c)
++b_count;
if(b>d)
++b_count;
if(b>e)
++b_count;
if(c>a)
++c_count;
if(c>b)
++c_count;
if(c>d)
++c_count;
if(c>e)
++c_count;
if (d>a)
++d_count;
if (d>b)
++d_count;
if (d>c)
++d_count;
if (d>e)
++d_count;
if (e>a)
++e_count;
if (e>b)
++e_count;
if (e>c)
++e_count;
if (e>d)
++e_count;
switch(a_count){
case 0:
first = a;
break;
case 1:
second = a;
break;
case 2:
third = a;
break;
case 3:
fourth = a;
break;
case 4:
fifth = a;
break;
}
switch(b_count){
case 0:
first = b;
break;
case 1:
second = b;
break;
case 2:
third = b;
break;
case 3:
fourth = b;
break;
case 4:
fifth = b;
break;
}
switch(c_count){
case 0:
first = c;
break;
case 1:
second = c;
break;
case 2:
third = c;
break;
case 3:
fourth = c;
break;
case 4:
fifth = c;
break;
}
switch(d_count){
case 0:
first = d;
break;
case 1:
second = d;
break;
case 2:
third = d;
break;
case 3:
fourth = d;
break;
case 4:
fifth = d;
break;
}
switch(e_count){
case 0:
first = e;
break;
case 1:
second = e;
break;
case 2:
third = e;
break;
case 3:
fourth = e;
break;
case 4:
fifth = e;
break;
}
printf("%d %d %d %d %d\n", first,second,third,fourth,fifth);
return 0;
}
One last thing: every solution here will not be as simple and elegant as a simple loop. I do think Bermudez intends to show you how to work with such basic language features, but to keep you in mind, this workaround is very awkward :)
source to share