Sorting & Searching

Sorting & Searching 

By: Bismo Asyura Widianto

NIM: 2201785595

Searching Algorithms are crucial parts of any program. They often look for a record or entry in a database. However, there are algorithms that goes through virtual space to look for possible chess moves. Although there are a number of algorithms a programmer can use, they tend to select the the one that best matches the size and structure of the database to give the most user-friendly experience. 

Linear Search 

This type of algorithm is the preferred choice for short lists because of its simplicity and minimalist code implementation.  This algorithm looks at the first list of item to see whether you are searching for it. If the algorithm does not find it in the first index, it will then continue to the next item of data. This process is repeated until an item is found. When using this search, we do not need to arrange the data in order. 

Binary Search
Binary Search is a fundamental and useful algorithm in Computer Science. It is very popular in large databases with records ordered by their numerical key. 

The algorithm starts at the middle of the database. Then, if the target value is greater than the middle value of the database, the search will continue from the upper-half of the database because the rest of the data is not relevant to our target. If the target value is lower than the middle value of the database, it will continue to search only the values the lower-half of the database. This process is repeated until the target is found. This type of search is more complicated but is much more efficient when dealing with large databases. 

Main sections of a binary search:

1. Pre-Processing
1. Before searching, we need to sort the collection into order.
2. Binary Search
1. Here, we use a loop to divide the search space in half after each comparison of a d
3. Post Processing
1. Finally, we determine possible values in the remaining space.

Sorting Algorithms Includes ordering a list of data or information into a certain order that we want. For example, we would want a telephone directory to start according to the alphabet from a to z. There are a number of ways we can sort a data however, the most popular way to sort is through bubble sorting and insertion sorting. 

Bubble Sort

Bubble sort algorithm starts by comparing the first two elements of an array and swapping if necessary, i.e., if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, if the first element is smaller than second, you mustn’t swap the element. To sum up, we perform  basic operation such as  interchanging a larger element with a smaller one following it, starting at the beginning of the list, for a full pass to do a bubble sort correctly.

Insertion Sort
This type of sorting is relatively simple because it builds the final sorted array one item at a time. Therefore it is easy to understand and do but will take a very long time if a large list is presented to the algorithm. Furthermore, if elements are sorted in reverse, it will take a longer amount of time because 

Firstly, the insertion sort begins with the second element and compares it with the first element and inserts it before the first element if it does not exceed the first element and after the first element if it exceeds the first element. At this point, the first two elements are in the correct order. This process is then repeated until it reaches the last element of the collection of data. 

Pseudo-code: