Searching and Sorting
Linear Search vs Binary Search
Linear search
A linear search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.
Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching.
Binary search
Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.
Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search. So therefore we should explore sorting algorithms.
Sorting Algorithms
There are many sorting algorithms so we will focus on a few and analyze their performance.
Bubble Sort
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The comparison is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements “bubble” to the top of the list. This simple algorithm performs poorly in real world use and is used primarily as an educational tool.
Bubble sort has a worst-case and average complexity of О(n^2), where n is the number of items being sorted.
Selection Sort
The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
Selection sort has a worst-case and average complexity of О(n^2), where n is the number of items being sorted.
Merge Sort
Merge Sort is an efficient, general-purpose, and comparison-based sorting algorithm.
Conceptually, a merge sort works as follows:
- Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
Merge sort has a worst-case and average complexity of O(n log n), where n is the number of items being sorted.
Quick Sort
Quick sort is an in-place sorting algorithm. Quick sort is a divide-and-conquer algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
On average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though this behavior is rare.
