Sorting Algorithms
Introduction
Imagine that someone hands you a deck of playing cards and that you are going to play a game requiring them to be in a sorted order.
Is there any particular method you would use to sort them?
Now, imagine that all of the playing cards are flipped upside down, and you are only allowed to have 2 cards facing up at a time.
How would this change the way you sort them?
In computer science, we often have to sort items just like this. Consider when you shop online and you can sort items by price, name, type, etc. The computer needs to be able to filter everything you request quickly and correctly, and this is made harder by the fact that computers can only compare 2 items at a time. To solve this problem, we devise software called sorting algorithms.
What does a sorting algorithm do?
Sorting algorithms do exactly what it sounds like: they sort a list of items. They can do this in a multitude of ways, but there are several recurring themes, methods, and terminology that is shared between most if not all sorting algorithms.
For example, a comparison is when we compare two items to see which one is greater than the other. Additionally, a swap is when we take two items and switch their positions in a list.
Why are there so many sorting algorithms?
There are many sorting algorithms, and even more being developed all the time. This is due to a few reasons, but the simplest answer is just that people have thought of new ways to sort things as time has gone on. Additionally, there are sorting algorithms that are objectively better than others.
What makes one sorting algorithm better than another?
There are a couple major factors to a sorting algorithm we need to consider:
Obviously, we want our algorithm to run as fast as possible. If you think about sorting 1,000 decks of playing cards by hand, we can see that speed is a major factor in how we decide to sort them. In the computer world, we call this time complexity.
Another problem that might come up in our scenario is the physical space required to lay out all 1,000 decks of cards. For a computer, there is a set amount of "space" that can be used, so we need to make sure that it is being used efficiently. We will call this space complexity.
Given these factors, we may now devise different strategies to sort our data and compare them with these criteria to find the best algorithm(s).