Comparing Sorting Algorithms on Rainbow-Colored Bar Charts

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

Sorting algorithms put elements of a list in numerical order. This Demonstration shows how five different sorting algorithms rearrange numerical values shown as vertical bars. We compare the following algorithms in terms of the number of steps they take when rearranging the elements in a list: shell sort, bubble sort, insertion sort, cocktail sort, and bogosort (fixed at seven values because the time complexity demands too many steps for many elements).

Contributed by: Michael Zhou and Karolina Urban (June 2016)
Based on a program by: Jay Warendorff
Special thanks to the University of Illinois NetMath Program and the mathematics department at William Fremd High School.
Open content licensed under CC BY-NC-SA


Snapshots


Details

Shell sort is an algorithm that splits the list into smaller sublists. The mechanism sorts each of the individual groups, which creates a slightly more ordered list. Then, the algorithm uses an insertion sort to quickly order the elements. This is an efficient sorting algorithm.

The bubble sort method works by comparing the first two values of the list. If the first value is greater than the second value, they switch; otherwise they stay as they were. In either case, the current second value is then compared with the next value, and so on.

Insertion sort takes each element one by one from an input list and inserts it into its correct spot in a new output list (often put right before or after the input list). This method is efficient for short lists or for lists that are mostly sorted.

Cocktail sort is similar to bubble sort in the way that it compares two elements of the list at a time, but sorts both ways. The elements are moved back and forth according to whether they are smaller or larger. So it sorts from the left and the right to meet up in the middle.

Bogosort is the most inefficient. The algorithm works by randomizing the order of the list until eventually the elements are placed in the perfect order. This sort could go on for a very long time or take two steps. Based on the randomness of this sort, we created a constant number of seven elements to avoid a computer system crash.

You can randomize the values in the list, but not the number of elements.

References

[1] V. S. Adamchik. "Sorting." (Jun 9 2016) www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20 Algorithms/sorting.html.

[2] Saylor Academy. "Sorting Algorithm." (Jun 9, 2016) www.saylor.org/site/wp-content/uploads/2011/06/Sorting-Algorithm.pdf.

[3] V. Bohush. Visualization and Comparison of Sorting Algorithms [Video]. (Jun 9, 2016) www.youtube.com/watch?v=ZZuD6iUe3Pc.

[4] OJ Reeves. "Sorting Algorithms: The Cocktail Sort," OJ's Perspective (blog). (Jun 9, 2016) buffered.io/posts/sorting-algorithms-the-cocktail-sort.

[5] Rosetta Code. "Category: Sorting Algorithms." (Jun 9, 2016) rosettacode.org/wiki/Category:Sorting_Algorithms.

[6] Runestone Interactive. "The Shell Sort." (Jun 9, 2016) interactivepython.org/runestone/static/pythonds/SortSearch/TheShellSort.html.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send