Sorting & Searching

Sorting

Sorting is the process of placing elements from a collection in some kind of order.

Types:

• Ascending
• Descending

Algorithms:

• Internal Sorting, where the data is loaded into the RAM
• External Sorting, where the data is stored in a secondary storage

Bubble Sort

The bubble sort makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. In essence, each item “bubbles” up to the location where it belongs.

Selection Sort

The selection sort improves on the bubble sort by making only one exchange for every pass through the list. In order to do this, a selection sort looks for the largest value as it makes a pass and, after completing the pass, places it in the proper location. As with a bubble sort, after the first pass, the largest item is in the correct place. After the second pass, the next largest is in place.

Insertion Sort

While similar to the two previous sorts, the insertion sort works slightly differently. It always maintains a sorted sub-list in the lower positions of the list. Each new item is then “inserted” back into the previous sub-list such that the sorted sub-list is one item larger.

Shell Sort

The shell sort, sometimes called the “diminishing increment sort,” improves on the insertion sort by breaking the original list into a number of smaller sub-lists, each of which is sorted using an insertion sort. The unique way that these sub-lists are chosen is the key to the shell sort. Instead of breaking the list into sub-lists of contiguous items, the shell sort uses an increment i, sometimes called the gap, to create a sub-list by choosing all items that are i items apart.

Merge Sort

Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.

Quick Sort

The quick sort uses divide and conquer to gain the same advantages as the merge sort, while not using additional storage. As a trade-off, however, it is possible that the list may not be divided in half. When this happens, we will see that performance is diminished.

A quick sort first selects a value, which is called the pivot value. Although there are many different ways to choose the pivot value, we will simply use the first item in the list. The role of the pivot value is to assist with splitting the list. The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.

Searching

Searching is the process of finding a particular element of an array.

Types:

• Linear Search, compares each element of the array with the search key.
• Binary Search, if the array sorted, the high-speed binary search technique can be used.
• Interpolation Search,  performed on the sorted data. Similar with binary search technique, searching technique is done with the approximate location of data