
Writing a Sorting Algorithm
Total points 4
1.
Question 1
Assignment overview
This assignment is an opportunity for you to develop an
algorithm of your own and have someone else execute it to give you
feedback on its correctness and specificity.
You will write an
algorithm that sorts temperature data from least to greatest. To do
this, you will work through the first four of the Seven Steps.
Introduction to the data
NOAA's National Centers for Environmental Information collects global
climate data and aggregates this data to provide information on climate
trends and variability. One product they offer is a monthly regional
analysis. The following table gives "anomaly" data by continent for
January 2017. "Anomaly" means the value is the temperature difference
from the average temperature from years 1910–2000.
Continent
Anomaly (C)
North America
3.18
South America
1.36
Europe
0.12
Africa
0.53
Asia
1.92
Oceania
0.98
Source: https://www.ncdc.noaa.gov/sotc/globalregions/201701
Assignment task
Your task is to develop an algorithm that would sort data such as these
from least to greatest. Specifically, given an unsorted set of N decimal
values, your algorithm should sort them to give an answer of the sorted
data. For this set of N = 6, your algorithm should produce:
0.12
0.53
0.98
1.36
1.92
3.18
Step 1: Work an example by hand
Take the list
of values, and sort them by hand. Sort them the way that comes most
naturally to you. Do not research sorting algorithms or try to figure
out the most efficient method—that is not the point of this assignment.
Step 2: Write down exactly what you did
Think
carefully about how you performed the sort by hand. What values did you
compare? In what order? How did you know when you were done? Write down
these steps exactly.
Step 3: Generalize
Look for patterns in the steps you wrote down for Step 2. If you
repeated sets of steps, how could you count repetitions? If you swapped
certain values under certain conditions, what were they? Are there
variables you need to name in order to reuse? Write down your
stepbystep generalized algorithm.
Step 4: Test your algorithm
Execute
your algorithm for a different set of data, such as a subset of the
given data, data you make up, or another month's climate data, such as
February 2017: https:
Does your algorithm work for any N? Have you thought of corner cases it might need to handle, such as N = 0 or N = 1?
How to submit:
Enter your algorithm in the text box. You can work
in another program and copy/paste into the box, or you can type your
algorithm directly.
Your algorithm should be written in clear English, not C code.
1 point
What do you think?
Your answer cannot be more than 10000 characters.





So, did you have a question or a problem with your code?





I am currently taking a exercise is the shaker sort algorithm.Instead of separating two for loops, I have included a forj loop inside a fori loop. Please check my code.
public static void shakerSort(int array[], int n)
{
boolean swapped = true;
while (swapped)
{
swapped = false;
for (int i = 0; i < n  1; i++)
{
if (array[i] > array[i + 1])
{
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = true;
}
if (i == n  2)
{
if (!swappped)
{
break;
}
else
{
swapped = false;
for (int j = n  1; j > 0; j)
{
if (array[j  1] > array[j])
{
int temp = array[j];
array[j] = array[j  1];
array[j  1] = temp;
swapped = true;
}
}
if (!swapped)
{
break;
}
}
}
}
}
Output:
5
3
5
9
11
12
15
18
I hope you can rate my code .Thank you very much





Member 15233409 wrote: I hope you can rate my code . I give your code a 4.5 rating. You're welcome.
The difficult we do right away...
...the impossible takes slightly longer.





Hi Everyone!
I have an interesting question and I do believe this is the best resource I have for asking this about this type of problem.
I've been a SysAdmin for close to 15 years now and alot has transpired throughout these last few years due to COVID. Alot of situations have been brought to light from a political standpoint in a world where I really did not consider myself involved in (and still not too much now).
It does seem that there's alot of Skepticism on resultsets that don't favor one's position, even going as far as to weaponizing Skepticism as a premise for rejecting results.
These thoughts have lead me down the path of confronting an idea of this possible outcome verification problem that can arise depending on the subject matter and as most of you may be aware with our own US elections (But can apply to anything really). I really want to stay strongly on topic as this is specifically an Algorithm subject for me.
My question I believe is in the neighborhood of the idea of SSL, but I was wondering is there a specific Algorithm or tweak of one that can be used to verify if such a idea is possible.
My example is as follows.
We have over 330,000,000 people that currently live in the united states (maybe a lot more, I originally thought we were around 430,000,000 but should not matter as this needs to scale).
We can treat each person like a node.
If at the start of a public survey, vote, or poll can a "Public key" be published to the public a week before a Poll is rendered.
Each individual at the time of placing their vote would get assigned a HashValue and a position in line. That HashValue is a computed value that is at the time of inception of the Poll/vote/inquiry is being rolled based on the individuals unique ID (if needed) and the value selected they have chosen from the last known hashvalue from the previous vote place by the person inline before them. Once Polling/voting is closed, the ending key is also published to the public.
Now for example if you have a trusted family member in another state where one placed their value near the start of the polling and the other trusted family member placed their own value near the end (It does not have to be this way, they can place it closer), is there a such an algorithm that can be leveraged where both these members can get the publicly documented keys (both start key and the key calculated in the end), enter it into an offline system that can then run the algorithm and determine if any of the data at all or INBETWEEN The two values being placed in the chain have been altered?
I think as I am typing this out I feel like I'm describing a crypto blockchain perhaps?
Any suggestions or ideas would be appreciated! (I apologize if I am burning anyones time asking this question and hope not to trigger anyone on the subject as I specifically would like to maintain this question in the realm of Algorithms)
Thank you!






XxKeldecknightxX wrote: Now for example if you have a trusted family member in another state where one placed their value near the start of the polling and the other trusted family member placed their own value near the end (It does not have to be this way, they can place it closer), is there a such an algorithm that can be leveraged where both these members can get the publicly documented keys (both start key and the key calculated in the end), enter it into an offline system that can then run the algorithm and determine if any of the data at all or INBETWEEN The two values being placed in the chain have been altered? If you use USB sticks, then yes. No one would trust the outcome, but technically doable.
There would not be an in "BETWEEN" on the ledger. Typically, a transaction isn't valid until it is verified by a number of clients with access to the ledger.
edit
Basic idea of how a blockchain works;
Building A Blockchain In .NET Core  Basic Blockchain[^]
Simplest Blockchain in C#[^]
Bastard Programmer from Hell
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics."  Some Bell.
modified 9Feb22 18:20pm.





I'm writing a small routine to match strings using simple wildcards, namely "?" and "*".
So I have this dilemma:
Take the wildcard string "abc*xyz".
In your opinion, do you think that string should match only strings that begin with "abc" and end with "xyz", with any number of characters between?
Or, should that string match anything that begins with "abc" and the "xyz" at the end is irrelevant because the star matches anything that comes after "abc"?
The second case would be easy to code, and I imagine the first case would be more difficult. Which way would YOU expect the matching to work?
The difficult we do right away...
...the impossible takes slightly longer.





Coding an ending mask (xyz) and then having it ignored seems illogical.
To me, * represent 0 or one or many; ? represents any one match.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation."  Napoleon I





Thanks for your opinion. I tend to agree. Happy holidays!
The difficult we do right away...
...the impossible takes slightly longer.





You too! And best in the new year.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation."  Napoleon I





Traditionally, the * wildcard in a regular expression is "zero or more instances of the preceding character", so the regex "abc*def" would match "abcdef", "abccccdef" and even "abdef" (0 c's), but not "abccxccdef". It might even match "Hello abcccdef there", depending on whether the regex is considered to be anchored or not. In a traditional regex the '.' wildcard is to match any character. However, if you're writing your own regex parser, you're free to place any meaning on the wildcard characters you want.
The functionality you seem to be trying to reproduce seems very like unix file globbing. If that's what you're trying to do  and you are on a unix like system, you probably have access to glob(3) , which does all the heavy lifting for you. There's probably similar functionality for windows.
But maybe you're writing a regex parser for your own purposes. In which case you're free to make up the rules you want. Either way, I'd expect any literals in the regex to be present in any matches found.
Keep Calm and Carry On





Thank you for your input. I'm actually not going for regular expressions, just simple wildcard matching like in MSDOS.
Happy holidays!
The difficult we do right away...
...the impossible takes slightly longer.





String must start with abc and end with xyz
I also think that abc*xyz should match these:
abcxyxyz
abcxxyz
abcxyz
abcxxxxyyyyxyz
Add them to your unit tests.
The nice thing with this algorithm is that there is not a lot of state to track.
Very simple to implement in any language.





Slightly more complex if you want to extend it to a path of (back)slash separated directory levels with a directory name '**' indicating zero or more directory levels. I find this so useful that I would recommend that you include it from the very beginning. (Assuming, of course, that your wildcard routine is intended for file names, or similarly structured name strings.)





If * matched any character, then it would already match a slash.
You would have to make * not match a slash to need ** as another symbol.
I have seen and used the ** in a lot of utilities including Ant xml file sets. I have never had to write the logic for it, though.





Try MSDOS 5.0.
That's what I expect. Nothing more. Nothing less.
Bastard Programmer from Hell
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics."  Some Bell.





If you write a matching routine for file/path names, you should at least as an option treat the path separators differently. For a general matching routine, the (set of) separator character(s) should be a parameter, so the same routine can be used in different contexts, e.g. different file systems.
I guess that writing a match for ** that doesn't use recursion would require more effort and the code would be more difficult to comprehend than to do it recursively. I wouldn't ever consider flattening that recursive matching routine I use in my code. (But of course, like in all recursion, I take care to reduce the stack frame to a minimum.)





The original post does not mention file system anywhere.
I was thinking more in terms of a pure programming exercise.
For traversing directory structures, I use a Visitor pattern with methods of beginDir/endDir/foundFile.
This allows easy reuse of the recursive algorithm across a dozen utilities that process file trees.
Keeps the stack lean for the recursion, any bloat ends up in the Visitor’s heap memory. (Including a few utilities that needed their own stack data structure to perform their job)





Here edges is a String array representing a set of space separated integer pair elements e.g. "e1 e2" where 0 < e1!=e2 <= n
n is an integer, let's say ranging 0 < n <= 100000
public int sumSqrtCeil(int n, String[] edges){
...
List<Set<Integer>> edgeSetList = "converted first edges element to set of Integer"
for(int i=1;i<edges.length;i++){
Set<Integer> nodeDuo = "converted this edges element to set of Integer"
boolean found = false;
for(Integer e : nodeDuo){
for (Set<Integer> edgeSet : edgeSetList) {
found = edgeSet.contains(e);
if (found) {
break;
}
}
if(found) break;
}
if(!found){
indexOfEdgeSetList++;
edgeSetList.add(nodeDuo);
}
else{
edgeSetList.get(indexOfEdgeSetList).addAll(nodeDuo);
}
}
Set<Integer> linkedNodes =
for(int i=1;i<=n;i++){
if(!linkedNodes.contains(i)) output+=1;
}
output += edgeSetList.stream().mapToInt(integers > (int) Math.ceil(Math.sqrt(integers.size()))).sum();
return output;
}
As per my understanding (updated) complexity should be
O( O(A) * O(B) * O(C) + O(D) + O(E) )
O( O(edges.length) * O(2) * O(n/2) + O(n) + O(edges.length) )
O( O(edges.length) * O(n) + O(n) + O(edges.length) ) //constant removed
O( O(n*edges.length) + O(n) + O(edges.length) ) //evaluate
O( O(n^3) + O(n) + O(n^2) ) //evaluate
O( O(n^3) ) //taking biggest factor
O(n^3)  Final Time Complexity.
where,
O(edges.length) = O( n! / 2! * (n2)! ) = O( ( n * (n1)) / 2 ) = O( n^2  n / 2) ==> O(n^2)
Please feel free to share also consider me a complete noob for Algorithm. Just started learning formally.
modified 24Nov21 1:01am.





You might have a better chance of getting a response if you stated the algorithm in the more general style of most textbooks rather than in C#, which not all readers understand.





Thanks for advise.
I am not a computer science grad, Let me have a look at an Algo book to study to update my question.
Perhaps I may not need this forum to answer this question in the process.





Tried to update and make simpler to understand





Micronaut here (Microverse Student)
To get the complexity of this algorithm is actually quite simple, just check if there is an existing nested for loops and if those for loops actually depend on the input.
For example:
for(... input.length) {
for(...input2.length) {
}
}
this code's complexity will be the length of input1 * length of input2. and if they are the same, it will be the length^2. which is what we note by n².





Is there any fast algorithm for this:
K people sit at a table. Each person holds a number (hi) which means: some of his neighbour has a cap of height (hi). I want to count the number of combinations for setting people up at the table according to their height of their cups.
Example:
in:
6
2 6 4 5 3 5
out:
2
(We have two combinations which are 1 2 6 4 5 3 and 6 2 1 4 5 3)
Explanation:
We know that first person points on the second person and last person points on the penultimate person. The neighbour of the second person on the left is two, so his neighbour with height 4 should be on the right. Next we know that left neighbour of fifth person is 4, so his neighbour with height 3 should be on the right. We have two combinations to place 1, 6 cups (1,6 and 6, 1):
Visualisation:
2 6 4 5 3 5
X 2 X X 5 X
X 2 X 4 5 3
Possibilities: 1 2 6 4 5 3 or 6 2 1 4 5 3
Any suggestions or help would be greatly appreciated.



