Sorting and Searching Algorithms

Selection Sort

Begins by finding the smallest value in the list and moves it to index zero.

Next, it looks for the second smallest value in the list, and moves it to index zero.

This process continues until the list completely sorted.

Insertion Sort

Begins by comparing the first two values in the list, the smaller value will be swapped to go infront of the larger value. Swapping won’t happen if the first value is smaller than the second.

Next, the larger number from the last comparison will be compared to the value to its right. The smaller value will be moved infront of the larger number. Swapping doesn’t occur for the same conditions above.

Thirdly, the smaller value from this second comparison will be compared to the smaller number of the last comparison.

This process continues until the list completely sorted.

Merge Sort

Begins by splitting an array into two parts until each value is seperated.

Next, the algorithm reassembles the list by working on one side of the list. The first two values of the list get compared, and the smallest will be placed infront of the larger one. As each value gets added to one side of the list, it gets compared to the largest value of that side of the list. If it’s smaller, it proceeds ito be placed nfront of that number.

Once both sides are sorted, the arrays will merge, and values from both sides are compared.

Linear Search

Iterates through the ENTIRE list, and compares each value with the target value

Binary Search

This search algorithm requires the list to be sorted.

This compares the target value with the middle value in the list.

Depending if the value is less than or greater than, half of the list will be eliminated.

What equation can we use to estimate the number of iterations a binary search will take?

2^x , where x is the number of values in the list