Searches & Sorts:

Searches:

/

• Since search methods use a district formula to search through arrays, they are commonly referred to as search algorithms

• When writing algorithms that traverse arrays, programers often implement the enhanced-for loop, which is designed specifically for traversing entire arrays

• It is important to note that the enhanced-for loop provides a variable that will hold each element of the array. It will NOT automatically provide the index of that element, NOR will the array be modified if the variable created to hold each element is modified in any way

• Binary search:

  • “Divide and conquer” mechanism

  • Only works when there is an inherent order in the data (MUST BE SORTED)

  • Typically more efficient

  • Requires more than one comparison if the target is not in the middle, whereas a linear search (also called a sequential search) will need only one comparison if the target is first in line

  • Adjustment of middle value so that the algorithm searches to the left or right

  • If an element is not in the array, binary search will return -1

  • After just one comparison, the binary search algorithm ignores one half of the array elements; this is true for both the iterative and recursive versions

  • When low and high values cross, there are no more elements to examine, and the key is not in the array

Example: 

Suppose 5 is the key to be found in the following array:

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]

  1   4   5   7   9 12 15 20 21

First pass: low is 0, high is 8 mid = (0 + 8) / 2 = 4 Check a[4]

Second pass: low is 0, high is 3 mid = (0 + 3) / 2 = 1 Check a[1]

Third pass: low is 2, high is 3 mid = (2 + 3) / 2 = 2 Check a[2]

• In the best case, the key is found on the first try (i.e., (low + high) / 2) is the index of key)

• In the worst case, the key is not in the array or is at an endpoint of the array

  • An easy way to find the number of comparisons in the worst case is to round n up to the next power of 2 and take the exponent

  • If n is an exact power of 2, the number of comparisons in the worst case equals the exponent plus one

• The maximum number of comparisons will either have the key at an endpoint of the array, or be equal to a value that’s not in the array; however, if the key is at an endpoint, or a value not in the array, it is not necessarily a worst case situation

• Sequential search:

  • Starts at the first element and compares the key to each element in turn until the key is found or there are no more elements to examine in the list

  • The best case has the key in the first slot

  • The worst case occurs if the key is in the last slot or not in the list; in the worst case, all n elements must be examined

  • On average, there will be n / 2 comparisons

Sorts:

• Selection sort:

  • Search-and-swap algorithm
    

1. Finds the smallest element in the array and exchanges it with a[0], the first element

2. Now, finds the smallest element in the subarrat a[1]...a[n-1] and swap it a[1], the second element in the array

3. Continue this process until just the last two elements remain to be sorted, a[n-2] and a[n-1]

4. The smaller of these two elements is placed in a a[n-2]; the larger, in a[n-1]

5. The sort is complete

• For an array of n elements, the array is sorted after n - 1 passes

• After the kth pass, the first k elements are in their final sorted position

• Inefficient for large n

• Insertion sort:

  • Rather than traversing the entire array, the insertion sort compares the first two elements and, depending on the comparison, inserts the second value “in front” of the first value into index 0, moving the first value to index 1; the first two elements are now sorted; then the third element is checked, and the inserting continues

  • ALREADY SORTED ELEMENT WILL REMAIN IN ITS POSITION

• First element in the array, a[0] is thought to be sorted with respect to itself.

• Array consists of two parts, a sorted list followed by an unsorted list

• The idea of insertion sort is to move elements from the unsorted list to the sorted list one at a time; as each item is moved, it is inserted into its correct position in the sorted list

• In order to place the new item, some elements may need to be moved to create a slot
  

• For an array of n elements, the array is sorted after n - 1 passes

• After the kth pass, a[0], a[1], …,a[k] are sorted with respect to each other but not necessarily in their final sorted positions

• The worst case occurs if the array is initially sorted in reverse order, since this will lead to the maximum possible number of comparisons and moves

• The best case occurs if the array is already sorted in increasing order, as in this case, each pass through the array will involve just one comparison, which will indicate that “it” is in its correct position with respect to the sorted list (NO ELEMENTS WILL NEED TO BE MOVED)

• Inefficient for large n

• Merge sort

  • Divide and conquer

  • Employs recursion (uses a method to call upon itself)

1. Break the array into two halves

2. Merge sort the left half

3. Merge sort the right half

4. Merge the two subarrays into a sorted array

• Uses a merge method to merge two sorted pieces of an array into a single sorted array

1. Start with an unsorted list of n elements

2. The recursive calls beak the list into n sublists, each of length 1 (these n arrays, each containing just one element, are sorted)

3. Recursively merge adjacent pairs of lists; there are then approximately n / 2 lists of length 2; then, approximately n / 4 lists of approximate length 4, and so on, until there is just one list of length n

Example:

5 -3 2 4 0 6

5 -3 2 4 0 6

5 -3 2 4 0 6

5 -3 2 4 0 6

-3 5 2 0 4 6

-3 5 2 0 4 6

-3 0 2 4 5 6

• Disadvantage of merge sort is that it needs a temporary array that is as large as the original array to be sorted; this could be a problem if space is a factor

• Not affected by the initial ordering of the elements; the best, worst, and average cases have similar run times