Sorting And Efficiency

If I were given a list of numbers from 1-10, in mixed order, what could I do with the list?

For one, I could sort it if I had nothing better to do. I would easily skim through the list until I found the smallest number, and place that in the far left side of the list.

[10, 4, 2, 3, 9, 8, 1, 5, 6, 7] would become [1, 10, 4, 2, 3, 9, 8, 5, 6, 7]

I could sort this entire list in mere seconds and not give it anymore thought, moving on with more important things in my life such as procrastination. But I were to find myself given another list, this time with numbers ranging from 1-1000000, would I even bother to sort it?

If I had dedicated more attention for the previous list, would that have helped in sorting a list, especially with a large range of numbers?

It turns out it would, and I could determine whether sorting a list of a million numbers would be worth the extra 3% on my final grade, or taking that time to studying for the upcoming exam.

Almost at the end of the first iteration
of sorting a list of a million elements,
Timmy decides he should probably start studying
 for his exam tomorrow instead.

In order to sort the list posted above, I took the smallest number and moved it to the far left, then moved everything else one to the right.

Sorting the list this way, I'd have to check every element, find the smallest, move it to the left, then shift everything else to the right.

Once I discovered that it takes approximately n² steps to sort the list using my method, and each step takes me ¼ seconds to process, a list with 10 elements would take me 25 seconds to sort.

With a list of a million elements, it would take me approximately 7927 years. Good thing we have computers and good thing there are more efficient sorting methods.

Finally, time to earn that 3% in CSC148.

"It's helpful to see how an algorithm's run-time grows."

Big O, big omega, big theta, all of which can be utilized to model the run-time of code, showing just how long it would take to complete for any size input.

But is it really helpful? I'm just over here with my simple list shifting numbers to one side, also mixed up in all of this recursion and trees and linked lists and more trees.

Or the greater question, is this the stepping stone? Can I no longer mindlessly crunch blocks of if-statements? Is it no longer appropriate to write if some_variable == True?

I think I'm starting to get the picture, the slightest taste of the realm of computer science and it's not fun and games like I thought it would be. There is great potential to be found within, not just for self accomplishment and not just to secure a job at some start-up company, but to propel advancement, and our capability to evolve as a civilization.

Coming across the problem P=NP, it really demonstrates how much computer science is interconnected with contemporary society. Soon we'll be able to figure out what is worth researching, how fast we can make discoveries, and by then robots will have taken most if not all of our jobs.

Recursion

The definition of recursion (from Google) is as follows: the repeated application of a recursive procedure or definition.

That doesn't explain too much, so what is it exactly, and what is its purpose? Is it something that provides us with another means to insult our peers?

While some may choose the path of impertinence, the role recursion plays in the world of coding is quite significant, almost vital to the entire process.

It is something that can be written in a simple line of code, yet capable of complex output. Who would have ever thought to call a function inside a function? Someone who probably didn't want to repeat several blocks of code. So then is recursion the product of laziness and apathy? Absolutely not. It is in fact, fundamental to computer science, providing a powerful means to control algorithms and approaches the possibility of self-automation robots similar to the ones in the film I, Robot. Just imagine what would happen if a computer possessed the potential to solve all of its own problems.

Since a recursive function calls upon itself infinitely many times, they require a 'base case', where the code is able to step out from a never-ending loop.

In this instance, the base case lies within "else x". Without the base case, the function would execute repeatedly, until eventually the program ran out of memory.

It's similar to two mirrors facing one another, and without a base case, you'd end up with infinite reflections reaching to the point where they become so minuscule, they are no longer visible.

At some point, you would need to step out.

It is interesting to ponder if the base case itself was a recursive function, for a recursive function defined within another recursive function. Being able to manipulate the concept of infinity is something far more sophisticated than making a 'yo mama' joke, but tracing recursion and trying to figure out how to implement it can often be difficult. Sometimes we just need to step back and crack a joke to realize what we were aiming for all along.