ryanalameddine/sortingtest

A test of the speed of different sorting algorithms (tested on an Asus FX503VD)

SortingTest

Idea by: Ryan Alameddine, Nolan Costin, Andrew Zerby

Programmed by: Ryan Alameddine

Selected Bio project:

Question: What is the most efficient (in terms of speed) sorting algorithm?

Background: When creating a computer program, you often need to sort a large list of items into a specific order. However, in some applications, such as games or network protocols, memory efficiency and speed is vital to the success of the application. Because of this, various computer scientists and mathematicians have developed a variety of algorithms for sorting sets of data. However, it can be hard to know which ones are actually going to perform better in specific situations, so doing these tests could be very beneficial.

Possible Algorithms: 

---

• Quicksort

• Algorithm Summary:

• Quicksort uses a divide and conquer approach described below:

1. Select an element from A[0 : n – 1] to be the pivot.
2. Rearrange the elements of A to partition A into a left subarray and a right subarray, such that no element in the left subarray are larger than the pivot and no element in the right subarray is smaller than the pivot.
3. Recursively sort the left and the right subarrays.

• Expected Efficiency:

Worst Case	Average Case	Best Case

• Source: https://web.stanford.edu/class/archive/cs/cs339/cs339.2002/qsort.pdf

---

• Mergesort

• Algorithm Summary:

• Mergesort uses a divide and conquer approach described below:

1. Divide the array repeatedly into two halves
2. Stop dividing when there is single element left. By definition, single elements are already sorted.
3. Continue merging the two already sorted subarrays into sorted subarrays until they are all merged into one sorted array.

• Expected Efficiency:

Worst Case	Average Case	Best Case

• Source: https://pdfs.semanticscholar.org/6804/987ab63d1879aa55ba68224dced142ce8774.pdf

---

• Bubble Sort

• Algorithm Summary:

• This set of instructions repeats until the correct order has been found:

1. Mark the first element in the array.
2. If marked value is higher than the next value, swap them.
3. Move the marker up one.
4. Repeat step two until you hit the end of the array.
5. If the array is not sorted, go back to step two.

• Expected Efficiency:

Worst Case	Average Case	Best Case

• Source: https://users.cs.duke.edu/~ola/bubble/bubble.pdf 

---

• Insertion Sort

• Algorithm Summary:

• This algorithm works by inserting values into their respective spots in a list

1. Move the first value into a new list.
2. Check the next value, and search through the new list until you find the spot the value should be inserted.
3. Insert the value.
4. Repeat step two until the original is empty.

• Expected Efficiency:

Worst Case	Average Case	Best Case

• Source: https://www.irjet.net/archives/V3/i12/IRJET-V3I12115.pdf 

---

• Heapsort

• Algorithm Summary:

• This algorithm works by creating a heap tree with the data. It then swaps the top and bottom nodes on the tree until the list is sorted.

• Expected Efficiency:

Worst Case	Average Case	Best Case

• Source: https://file.scirp.org/pdf/JCC_2017102715100595.pdf 

---

• Selection sort

• Algorithm Summary:

1. Put a “sorted” marker at the beginning of the array.
2. Find the lowest value in the array, and swap it with the first value after the sorted marker.
3. Move the sorted marker up by one.
4. Repeat step two until the marker reaches the end of the array.

• Expected Efficiency:

Worst Case	Average Case	Best Case

• Source: https://www.irjet.net/archives/V3/i12/IRJET-V3I12115.pdf 

Materials: Computer

Procedure summary: Create a C# program in which the computer generates 1000 random numbers between 0 and 1000 inclusive (duplicates are not prohibited). Then, run multiple the test set through multiple sorting algorithms and record time elapsed. The program will then repeat this process 1000 times, and record output data in chart.

Hypothesis: Heapsort and Mergesort will tie for the highest speed efficiency, because their best and worst case performance is O(n log n).

---

BIO INDEPENDENT PROJECT