Sorting Lab

Construct a series of programs that sort through an array of numerical values utilizing several different sorting techniques. The sorting is displayed in a GUI graph.

When you take a glance at the image above, what do you see? 4 ordinary cans? While that is true, the bins are colored for a reason. Each is used to store objects that fall within a certain category, be it color, composition, density, purpose, etc. Every object to be disposed needs to be added to a specific category before it can be considered organized. That idea is the central theme for this project, the Sorting Lab.

Organization is key, especially when dealing with numerical and objectified data.

Purpose

In agreement with the statement above, organization is vitally important in just about anything you do, be it working at your desk, cooking, or even washing your laundry. Sorting data is just as important as the above mentioned tasks, perhaps even more so. However, there are several different ways to sort data in Java. In this project, we will be exploring 3 different sorting methods - Selection Sort, Insertion Sort, and Bob Sort - as well the difference in speed and complexity for each.

Sorting Quantitative and Qualitative Data is vital in any field

GUI Graph

For each of the algorithms, the array is stored as a DynamicArrayChart object called 'chart'. To better understand how the algorithms work, a few of the methods within DynamicArrayChart must be explained.

DynamicArrayChart, as a class, is an extension of the JFrame class within Java. It serves the purpose of the graphical representation seen in the featured images of the sorting algorithms. The chart itself is essentially a graph with a y-axis (that has a maximum of 50 units) and an x-axis containing 20 numerical elements, almost like a histogram.

The getValueForSwap1 and getValueForSwap2 methods get the values that need to be swapped when sorting. The second method is unique, as it uses the repaint() method to color bars in the graph, which results in the yellow and orange bars seen in later sections. The markAsMin() method simply sets the variable of the class, minIndex, to a specific index. Lastly, the swap method switches the two values obtained by the getvalueForSwap methods and repaints the graph. The above mentioned methods can be found here, at the Github Repository for the project.

Big O Notation

Also known as Landau's Symbol, Big O Notation is used in Computer Science, Mathematics, and Complexity theory to describe the asymptotic behavior (also known as end behavior) of functions. Essentially, Big O Notation explains how fast a function grows or declines.

The table is above is ordered from the slowest to fastest growing functions. Since logarithmic and polylogarithmic functions differ by only a constant, c, they are treated as equivalent in Big O Notation. These formulas of Big O Notation will be used to compare the speed and growth of sorting algorithms in Java, and will be mentioned several times. Reference this section if necessary.

The Values

For this project, the data that needs to be sorted is randomly generated in an array as a group of integers from 1 to 50, inclusive. The code for said generation is shown below, and is identical for all algorithm classes:

/* Create an array of integers named array with 1-20 elements.
* Element values must be from 1-50. */
int[] arr = new int[20];
for (int i = 0; i<arr.length;i++){
    arr[i] = (int)Math.floor(Math.random()*50 + 1);
}

The Math.random() and Math.floor() methods are used to generate random values between 0 and 1 and round down values to the largest integer less than or equal to the provided value, respectively.

Selection Sort

Selection sort organizes data by repeatedly finding the smallest numerical element from an unsorted section of data and placing it at the beginning of the array. To do so, the algorithm maintains two subarrays:

• One subarray that contains sorted values

• Remaining subarray that contains unsorted values

In each iteration, the minimum value within the unsorted subarray is chosen and added to the end of the sorted subarray. This is done until the unsorted subarray is empty, meaning that all the values are sorted. The output of the algorithm is represented in a GUI graph shown below:

The algorithm has chosen 12 as the smallest value (orange bar) in the unsorted subarray, but is still iterating through (yellow bar)

The algorithm has sorted al values below 25, and is about to sort 28 (orange bar), as it is the minimum value currently in the unsorted subarray

Once all values are sorted, the array lights up green

The algorithm utilizes nested for loops in order to loop through all the values except the last one, during which the first element’s value and index are recorded as the lowest value and index, respectively. The nested loops are also used to compare the lowest value to every other value in the array. If a lesser value is found, the old lowest value is replaced with the new lowest value and index. Once the end of the array is reached, the index of the smallest value is compared to the first index in the outer loop. If the two values are unlike, the two values are swapped. The code is shown below:

for (int i=0; i< chart.getArrayLength()-1; i++){
    int min = i;
    chart.markAsMin(i);
    for (int j = i+1; j<chart.getArrayLength(); j++){
        if (chart.getValueForSwap1(j) < chart.getValueForSwap2(min)) {
            min=j;
            chart.markAsMin(j);
        }
    }
    if (min != i){
        chart.swap(i, min);
    }
}

In this case, the array is referred to as chart, since the array has already been implemented as a DynamicArrayChart object (more on that later).

The Selection Sort algorithm has a time complexity of O(n^2), which is quadratic. It is useful when dealing with high-memory operations, as the swaps remain beneath a complexity of O(n), which is linear.

Insertion Sort

The Insertion Sort algorithm is quite different compared to Selection Sort - it slowly moves through the array per iteration, and stops when two values are detected out of order. the value are then placed in the correct order, and a new iteration begins.

For example, suppose an array of 3,7,9,4,15,8,5 is provided. The first iteration results in:

3,4,7,9,15,8,5

as the first out of place comparison was between 9 and 4. The second iteration results in:

3,4,7,8,9,15,5

The third and final iteration results in:

3,4,5,7,8,9,15

An example in a GUI graph is shown below:

The value found to be out of place is 22. A "break" is created where 22 was.

The algorithm continues to create "breaks" as it works it way down the array, eventually finding a spot between 12 and 28.

The array lights up green once sorted.

The code for the Insertion sort is shown below:

for (int i = 1; i < chart.getArrayLength(); i++){
    storeVal = chart.copyToBuffer(i);
    int j = i - 1;
    while(j >= 0 && chart.getValueForMove(j) > storeVal){
        chart.moveIndexElement(j, j+1);
        j--;
    }
    chart.insert(j+1, storeVal);
}

This algorithm function similar to the sorting of a hand of cards: once dealt, the cards are sorted by removing the cards and placing them back in a better-sorted position. Starting at index 1 (the second element of the array) the algorithm loops through all of the remaining values while keeping track of the second element of the array. The second element is compared to each of the preceding values. If the value encountered is greater than the target value, the encountered value is shifted to the right. This is done until a value is encountered that is less than the target value.

The time complexity for Insertion sort is O(n^2). It works the slowest when the values appear in the reverse order, and takes the minimum amount of time (order of n) when the values are already sorted. However, Insertion sort is useful only for small datasets, unlike selection sort, which is applicable for large memory-intensive projects.

Bob Sort

The last algorithm featured in the project is Bob Sort. Bob Sort works by continuously looping through the array without stopping, making necessary swaps along the way, until swaps are no longer needed (the array is sorted). An example run in a GUI graph is shown below:

The value 44 is being compared to the value directly to its right, 35. Since 35 is lesser than 44, the two will be swapped.

The array turns green once the algorithm runs its final iteration without needing to swap

The algorithm loops through all the values, save for one, while comparing each value to its right neighbor. If the value to the right is smaller, then the two values are swapped. The occurrence of a swap is recorded. If a swap does occur, another iteration commences. This is implemented via recursion. As mentioned before, iterations must continue until the algorithm can loop throughout the entire array without having to swap, after which the array is considered sorted. The code is shown below:

int swapCount = 0;
for (int i = 1; i < chart.getArrayLength(); i++){
    if (chart.getValueForSwap1(i) < chart.getValueForSwap2(i-1)){
        chart.swap(i,i-1);
        swapCount++;
    }
}
if (swapCount != 0) runSort();

Also known as Bubble Sort, this algorithm also has a complexity of O(n^2). It performs worst when the data is first presented as reverse sorted. Quite simply, the best case occurs when the data is already sorted, as just one iteration occurs.

Due to the algorithm's simplicity, it is often used to introduce the idea of sorting algorithms. Its ability to detect and quickly fix minute errors in nearly-sorted datasets has made Bob/Bubble Sort quite popular in Computer Graphics, despite it's plain nature.

Final Thoughts

This project was quite entertaining to program. The was due to the results being visually appealing, which made the testing process all the more fun. The DynamicArraychart class took several days (and numerous references to Stack Overflow) to complete. Despite the difficulties it was a very helpful experience, as I learnt how to display visual media via Java, a skill I will need in the near future. In addition, the Selection sort algorithm was the most difficult to implement, as the idea behind process was difficult to grasp. However, the project was successful in the end!