Understanding Sorting Algorithms and Search Techniques
1. Different sorting algorithms vary in their efficiency. A more efficient algorithm will be faster and consume fewer resources (memory). The ordered data can be stored in main memory or mass storage. If the data is stored in lists and in small quantities, it is usually temporarily stored in arrays and records. This data is stored exclusively for internal treatments used for massive data management. There are two fundamental management techniques in data management: managing lists and file management. Methods are known as internal or external organization, depending on whether the ordered items are in main memory (MP) or secondary memory (M). 1.1. Bubble Sort is the least efficient. The bubble gradually moves smaller values (up) to the top of the array, while higher values sink to the bottom of the array. It requires n-1 passes. For each pass, adjacent elements (pairs of elements) are compared, and their values are exchanged when the first element is greater than the second. At the end of each pass, the largest element has bubbled to the tail of the sublist. For example, after the last pass, the bottom of the list V[n-1] is sorted, while the front of the list remains disordered. 1.2. Exchange Sort is the simplest sorting algorithm. It sorts the elements of a list or vector in ascending order. The algorithm compares the bottom element of the list with the others and exchanges positions when the order resulting from the comparison is incorrect. 1.3. Insertion Sort divides the array into two parts: one ordered and one unordered. The first element of the unordered part is taken and advanced to its proper place within the ordered part. It begins by considering the first item ordered and continues ordering the second element relative to the first, either moving forward or staying in place. After the index is advanced, marking the first unordered element, the third element is taken and placed in its proper position among the two previous ones. The index is advanced, and the process is repeated until all elements are in their proper places, resulting in a sorted array. 1.4. Shell Sort compares non-contiguous items, unlike the bubble method, and separated by a distance. If items are out of order, they are exchanged. The algorithm begins by specifying a range or gap, comparing elements separated by this interval and exchanging them if necessary. The starting gap is usually considered equal to half the total interval between the first and last elements, with the middle term as the first reference. 1.5. Quicksort, invented by C. Hoare, is considered the best sorting algorithm currently available. It is based on the exchange method. It involves selecting an item from a list and rearranging all other elements in the sublist so that all elements smaller than the given element are placed in one sublist, while all elements larger than the given element are placed in a second sublist. 2.1. Sequential Search finds an item in a list or vector using a value called a key. Vector elements are examined sequentially. The algorithm compares each element of the vector with the search key. Since the vector is unordered, on average, the program must compare the search key with half of the elements of the array. 2.2. Binary Search takes advantage of the fact that stored data is sorted. It compares each element of the array with the search key, starting in the middle of the list and checking if the key matches the value of the central element. If it does not match, the search continues in either the upper or lower half of the list. 2.3. Binary Search Tree allows for searching a value in an ordered binary tree by eliminating, whenever a node is examined, one of the two subtrees that cannot contain the desired value (all values below or all above). The process continues by discussing the root of the selected subtree and recursively searching one of the subtrees of the root. The process ends when a node matches the sought value or when it reaches a leaf of the tree and can no longer continue. The following example implements the search using recursion.