Have you ever stopped to think of what kind of searches you use in a day to day basis? Looking for that certain number by using the name as a sort key, searching through the latter half of your room for a particular item, or going through your closet one article at a time to find the skirt you want. Those are examples of searches. There are some definitions which may be new here, so click on the link to make sure you understand what I'm saying. There are two types of searches that will be covered - a binary and a sequential search. Before any collection must be searched, it should be sorted. Otherwise, how would you keep track of what you'd gone through in comparison to what you hadn't? That would be pretty time consuming. The sorts that will be covered here in brief are selection, insertion, bubble, and merge sort.

Searching

      Walls and Mirrors Definition: A process that locates a certain item in a collection of data.

      Sequential Search

      Remember going through your entire drawer of items to find that one special shirt? Tedious, isn't it? That's one reason why people choose binary searching in real life and in the world of programming. It's easier to find things faster if they're ordered in some way - later on, we'll cover sorting - and it's not so annoying. Sequential searches can be applied to both linked lists and arrays - a for loop can be used to traverse through each element or node because it will increment the index for you, or it will go through each node slowly and methodically, depending on what data structure you're using.

      Binary Search

      Sequential searches can get rather annoying sometimes, if you're going through a huge array of sorted elements. The faster alternative to this is a binary search. The algorithm for a binary search is found at Recursion, where Bunnies Meet Trekkers. Because this algorithm is recursive, it is more efficient. It splits the database of elements that you have several times before they find the item that you are searching for. This search requires the following steps:

1. Inspect the middle item of an array of size N.
2. Inspect the middle item of an array of size N/2.
3. Inspect the middle item of an array of size N/2^2,

Can you see the recursive nature of this type of search? That's one reason why it is more efficient than a sequential search. However, not always is recursion better than iteration.

Sorting

      Walls and Mirrors Definition: Is a process that organizes a collection of data into either ascending or descending order.

      Before we go on, we should differentiate between an external sort and an internal sort. Keep in mind that at all times, the only difference is where the data is stored. For an external sort, the data resides in both the computer's memory and on a secondary memory, such as a disk. For an internal sort, all the data resides on the computer's memory. All the sorts covered here are internal.

      Selection Sort

      An understandable analogy of this may be picking up a hand of cards, and ordering it by selecting cards one at a time until they are in order. For the selection sort, the first item is considered with the last item, found to be larger and then swapped; the second item is considered with the second last item, found to be larger and swapped; the pattern continues with the third, fourth... until the entire array is sorted in ascending order.

Together, a selection sort of N items requires
N * (N-1)/2 + 3 * (N - 1)
= N^2/2 +5 * N/2 - 3 comparisons.

      Bubble Sort

      What a bubble sort does is that it compares two adjacent items and then swaps them if the first one is larger than the second one. This is not effective, because it takes a few runs, which can consist of 2 or more swaps. Even though the array is not completely sorted after the first run, the first item has bubbled to the appropriate spot in the array. It starts with the first pair, and then goes on to analzye the next pair and the next.

Together, a bubble sort of N items requires
2 * N * (N-1)
2 * N^2 - 2 * N comparisons.

      Insertion Sort

      This time, when you pick up the same hand of cards, you will pick up another one and insert it into the appropriate position. Here, it takes an item in the array, and compares it to the one next to it. If it is larger than the one next to it, it copies the smaller item, moves the larger item into it's spot, and inserts it into the position before the larger item.

Together, an insertion sort of N items requires
N * (N-1) + 2 * (N-1)
= N^2 + N - 2 comparisons.

      Merge Sort

      A mergesort behaves very similiarily to a binary search, except that the purpose in halving the array is not to find a specific item, but to sort an array. The base case for this recursive algorithm is one element per subarray. After they have reached this base case, they merge the elements back together step by step until the sorted array is formed. Finally it is written into a temporary array before it is written into the original array. The only flaw in this efficient algorithm is that a temporary array is required.

Therefore, the mergesort of N items requires
3 * N- 2^m comparisons.   *Note that M is the level of the recursion.

      Any set of data should be ordered before they are searched by the binary method. Any type of sort can be used, but mostly the one with the best efficiency is chosen because time and money matter. As time is short, I will try to get some sort of code up on this page a little later, so you can see for yourself exactly what each function can do in C++.