Sorting and Searching

A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.

Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. 



Simple Sorting:

Selection Sort:

Bubble Sort:
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements until they are in the right order, the order can be ascending or descending.

Insertion Sort:
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
Insertion sort takes a lot of time for large data, you must decide wisely which sorting will you use for different types of data.

Intermediate Sort:

Quick Sort:
Quick Sort is a method where it picks an element as pivot and partitions the given array around the picked pivot. There are many ways to pick a pivot. It will put the other element in the right position after being compared with the pivot that was picked.

Merge Sort:
Similar to quick sort, it divides the group of elements into two, and keep dividing until there are 2 elements left in each subgroup, then sort each subgroup and merge and repeat until all elements are in order.

For reference, this is a video comparing quick sort and merge sort.
https://www.youtube.com/watch?v=es2T6KY45cA
(video owned by udiprod)

Searching:

Based on the type of search operation, these algorithms are generally classified into two categories:

Sequential Search: In this, the list or array is traversed sequentially and every element is checked. 
Linear Search is one of the examples of sequential search.

A simple method to perform a linear search, ie
Starting from the leftmost element of arr [  ], compare each element of x and arr [  ] one by one
If x matches the element, the index is returned.

Returns -1 if x does not match any of the elements.

Interval Search: These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half.
Binary Search is one of the examples of binary search.
Search for the sorted array by repeatedly dividing the search interval into two halves. Start with the interval that covers the entire array. If the value of the search key is less than the item in the middle of the interval, the interval is narrowed down to the lower half. Otherwise narrow it to the top half. Repeat the check until the value is found or the interval is empty.

Interpolation Search
Interpolation search is an improvement to the binary search of an instance where the values in the sorted array are evenly distributed. Binary searches always go to the middle element for checking. Interpolation search, on the other hand, can go to different locations depending on the value of the key being searched. For example, if the value of the key is closer to the last element, the interpolated search may begin searching toward the end side.

By :Steven

2201852132

Computer Science and Statistics