I have an assignment about practicing the algorithm recursive method, and since I'm new about this, I wanted to ask about, if there's anything I could possibly do to improve the speed of my code here.
So the assignment is about making a program that output the powered of each numbers between two intervals (and let's say that the first interval is from 1, and goes to n). For example, between 1 to n = 5 it should be able to output those powered numbers in between, something like: 1 4 9 16 25. There's a little problem I encountered on my function, but since it's not a really big deal, I can just let it go by incrementing the value of n by 1 (since the default value of n, if n = 5 as in the shown example, it will not starts from 1, rather from 0 and goes to 16 all the way, so I just tricked the program by thinking into going to 25 by n = 6 because of the 0 at the start).
Since my assignment asked me to output the code not in ascending order (must be in descending order), I gotta use another method of sorting, and I chose Quick Sort method in the first place, since I'm hoping it will make the program at least not as slow as using Bubble Sort and other log(n^2) time complexity sorting algorithms. At the end, the performance issue's still there, and even I deleted my Quick Sort, it is still indeed as slow as it can possibly be, and I'm wondering why as the perfomance issue keep worsen at n >= 10... Any help will be much appreciated to improve my understandings of the recursive call algorithm methods.
Here's the code I began to work with:
long long int PoweredSeriesArray[BUFSIZE32];
void SwapLLInt(long long int *X, long long int *Y) { long long int Temp = *X; *X = *Y; *Y = Temp; }
long long int StairsOfPowers(long long int Value) {
long long int Result = 0;
for (int Idx = 0; Idx < Value; Idx++) {
if (Value > 1) { Result = pow(StairsOfPowers(Value - 1), 2); }
PoweredSeriesArray[Idx] = Result;
}
return Value;
}
int Partition(long long int Array[], long long int Low, long long int High, bool Ascending) {
long long int PartitionInTraversevot = Array[High];
long long int i = (Low - 1);
if (Ascending) {
for (long long int j = Low; j < High; j++) {
if (Array[j] <= PartitionInTraversevot) {
i++;
SwapLLInt(&Array[i], &Array[j]);
}
} SwapLLInt(&Array[i + 1], &Array[High]);
} else {
for (long long int j = Low; j < High; j++) {
if (Array[j] >= PartitionInTraversevot) {
i++;
SwapLLInt(&Array[i], &Array[j]);
}
} SwapLLInt(&Array[i + 1], &Array[High]);
}
return (i + 1);
}
void QuickSort(long long int Array[], long long int Low, long long int High, bool Ascending) {
if (Low < High) {
int PartitionInTraverse = Partition(Array, Low, High, Ascending);
QuickSort(Array, Low, PartitionInTraverse - 1, Ascending);
QuickSort(Array, PartitionInTraverse + 1, High, Ascending);
}
}
int main(int argc, char** argv) {
long long int PoweredUpTo;
puts("WARNING: Inserting a number >= 10, resulting in the SLOWER PROCESS because of the recursive call!\n");
printf("Insert a number to be doubled with (max: [2^31] - 1):\n > "); scanf("%lld", &PoweredUpTo);
puts("\nThe following results are the staircase of each integers being powered to the two.");
printf(">>> ");
// Adding by 1 to trick the function, so the result
// is able to get from 0 up to pow(PoweredUpTo + 1, 2).
// Example: if n = 5, then result is 0 1 4 9 16;
// Making sure that the powered by two of n is there,
// not just up to n - 1, trick by adding by 1 more.
// Example: if n = (5 + 1), then result is 0 1 4 9 16 25;
StairsOfPowers((PoweredUpTo + 1));
// Sorting the array in descending order, because of the
// boolean value is set to false, meaning not in ascending order.
QuickSort(PoweredSeriesArray, 0, (PoweredUpTo), false);
for (int i = 0; i < PoweredUpTo; i++) {
printf("%lld ", PoweredSeriesArray[i]);
} return 0;
}
You do not need an array to achieve your goals. You need to implement head recursion as shown in the following Ada language program.
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
procedure Main is
Min : Positive;
Max : Positive;
procedure square (value : Positive) is
begin
if value < Max then
square (value + 1);
end if;
Put_Line (value'Image & " squared is" & Positive'Image (value * value));
end square;
begin
Put ("Enter the minimum value: ");
Get (Min);
Put ("Enter the maximum value: ");
Get (Max);
square (Min);
end Main;
See the following program output for a sample set of results:
Enter the minimum value: 1
Enter the maximum value: 10
10 squared is 100
9 squared is 81
8 squared is 64
7 squared is 49
6 squared is 36
5 squared is 25
4 squared is 16
3 squared is 9
2 squared is 4
1 squared is 1
This algorithm will execute 100 * 100 just as fast as 2 * 2.