Project Description
Background
In this project, you’ll learn how to implement a couple of different sorting algorithms and visualize how they sort by using computer graphics! Sorting algorithms are algorithms that have been created to solve the sorting problem. The sorting problem can be defined as follows:
Input: given a sequence of n values {a1, a2, a3, …, an}
Output: produce as a permutation (reordering) {a’1, a’2, a’ 3, …, a’n} of the input sequence such that a’1 <= a’2 <= a’3 <= … <= a’n
For example, if we are given the sequence of numbers {21, 43, 5, 12, 82} as input for our sorting algorithm, we should produce the permutation {5, 12, 21, 43, 82} as output. Similarly, if we are given the sequence of letters {T, P, A, E, R, L} as input for our sorting algorithm, we should produce the permutation {A, E, L, P, R, T} as output.
Sorting Algorithm Applications
There are many different real-world situations where sorting algorithms are used. Some more obvious applications include contact lists, spreadsheets, and music playlists. Another, maybe less obvious application, has to do with computer graphics. For images or graphics to be rendered correctly, the geometry must be sorted somewhere before they are rendered to the user. If not properly sorted, then distant geometry can appear in front of near geometry, creating completely wrong imagery.
Your Task
In the first exercise, you’ll implement the Bubble Sort algorithm and sort line graphic objects from smallest to largest. In general, if we can compare two or more elements or objects by any of their attributes, it means that they can be sorted by that attribute. In our case, we are going to be looking at the elements (integers in this case) of an array and sorting them using the Bubble Sort algorithm.
Bubble Sort is an algorithm that goes through an array and swaps pairs of values. The algorithm works as follows:
- Starting with the first element, compare it to its neighbor, the second element. If the left number (element 1) is greater than the right number (element 2), swap them.
- Compare the 2nd and 3rd elements in the same way. Then the 3rd and 4th, etc. Until you’ve gone through the whole array. At the first pass, you should end up with the largest element at the end of the array.
Repeat this process N times, where N is the number of elements in the array.
In the second exercise, you’ll be tasked to implement the Insertion Sort algorithm. Insertion sort is the type of sorting most people do if you give them a set of 7 playing cards, out of order, and ask them to sort them in their hand. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part. The algorithm works as follows:
- In each iteration, i, take the element in the ith position and compare it to the one before until you find the place where it belongs. (In other words, while it is less than the one behind it, keep moving it backward.)
As a final activity, you can use either of the sorting algorithms to create a graphical visualization of the sorting process!
