3-2-6 Searching and Sorting

Linear Search: this method starts at beginning of a list and compares each element in turn with the required value until a match is found or the end of the list is reached.

Bubble Sort: during a pass through the list, neighbouring values are compared & swapped if they are not in the correct order. Several passes are made until one pass does not require any further swaps.

 

Binary Search Example





















Binary Search: the algorithm is quite simple. It can be done either recursively or iteratively:

1. get the middle element;
2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:
• searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
• searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

Insertion Sort Example

Insertion Sort: An O(n²) sorting algorithm which moves elements one at a time into the correct position. The algorithm consists of inserting one element at a time into the previously sorted part of the array, moving higher ranked elements up as necessary. To start off, the first (or smallest, or any arbitrary) element of the unsorted array is considered to be the sorted part.