Introduction:
Our project operates on a huge database of objects. All of them have to be dynamically removed, edited, and picked based on their attributes. We had to sort list of PC components placed on the map by their rating, in order for the drone to find and pick the most suitable one. This is the crucial part of our application and for this purpose I had to do a strong research on searching algorithms. Below I will present the results of this research:
Bubble sort:
The bubble sort algorithm, known also as sinking sort algorithm, is probably the most common one due to its simplicity and therefore, ease of implementing. Because of this, the bubble sort is usually slower compared to other algorithms, especially when used to sort large data (Programiz 2014). It works by making multiple passes through an array. With each pass it compares first value with the next one. Assuming we want to sort the array in ascending order, if the first value is bigger than the next one, they will be swapped. Then the algorithm compares the second one with the third and the process iterates until it reaches end of array. Then it repeats these instructions for the second pass, up to the point where no values were swapped – meaning that the array has been sorted. With each pass the number of elements to compare is lower by 1. That’s because each pass should place the highest number in its right position - at the end of array. The algorithm is called „bubble” because each item „bubbles” up to the place where it belongs. (interactivepython.org 2015)
Quicksort:
Known also as partition-exchange sort, Quicksort uses divide-and-conquer, making it relatively faster than bubble or insertion sort. This also means, that it is a recursive algorithm. It is similar to merge sort, as they both are based on divide-and-conquer method. However, in practise, quicksort outperforms merge sort, and it significantly outperforms insertion sort and selection sort. The way it works is that it picks any element in array, that will be called a pivot. The algorithm rearranges all the other elements in array that are equal or smaller to pivot on the left side of it and the rest on the right side of it. This procedure is called partitioning and stands for the divide part of algorithm. Now, the conquer part is recursively sorting all the elements on the left of pivot and then the ones on the right of pivot. The algorithm is recurring up to the point where the whole array is sorted. (Khanacademy.org 2015)
List of references
Programiz.com (2014) Bubble Sort Algorithm in Programming [online] available from
<http://www.programiz.com/algorithm/bubble-sort>
Interactivepython.org (2015) The Bubble Sort [online] available from
<http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html>
Khanacademy.org (2015) Quick-Sort algorithm [online] available from
<https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/>
[3 March 2016]
