Searching and Sorting

Searching Algorithms

Search algorithm is an algorithm which solves the problem of retrieving store information.

Discuss

How to solve the problem of searching billions pieces of data?

Linear Search

One of the simplest searches.

Find an item with a particular value in a sorted sequence.

Find 'J' in sequence:
[4, 5, J, 10, Q, K, A]

J is the 3rd element (index 2).

Linear Search

Exercise

Writing Linear Search

Algorithm Solving Strategies

• Use iteration to move over a data structure
• Use comparison of values
• Use a large, diverse enough data set

Binary Search

Find an item by repeatedly halving the search space.

Binary Search:

Visualized

Binary Search: Steps

To find the index of element e with a certain value:

• Start with an array sorted in descending order.
• In each step:
  • Pick the middle element of the array m and compare it to e.
  • If element values are equal, then return index of m.
  • If e is greater than m, then e must be in left subarray. If m is greater than e, then e must be in the right subarray.
• Repeat those steps on new subarray.

Exercise:

Binary Search Simulation

• Sort your cards by number.
• Now let's find a card with a particular number using binary search.

Exercise:

Writing Binary Search

Algorithm Solving Strategies

• Use variables as a pointers to 'track' data during an algorithm
• Inside the algorithm, try to make your data set smaller such that you are comparing smaller sets of data to each other - called the 'base case'

Time/Space Complexity

Binary Search vs Linear Search:

What factors determine time?

N = number of items in sequence.

Since binary search algorithm splits array in half every time, at most log₂N steps are performed.

Other Searching Algorithms

Performance varies depending on sequence characteristics (distribution)

• Interpolation search

Sorting

Sorting

Sorting

Selection Sort

1. Iterate over the unsorted array, keeping track of the minimum value as you go


2. When you get to the end of the array, you know which element is the minimum


3. Swap the minimum element and the first element in the unsorted array


4. The first element is now considered sorted


5. Repeat until the rest of the array is sorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

1. Find minimum
2. Swap in front
3. Repeat with unsorted

Selection Sort Code

function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

function selectionSort(array) {
  for(var i = 0; i < array.length; i++) {
    var min = i;
    for(var j = i + 1; j < array.length; j++) {
      if(array[j] < array[min]) {
        min = j;
      }
    }
    if(i !== min) {
      swap(array, i, min);
    }
  }
  return array;
}
            

Selection Sort:

Time Complexity

Selection Sort:

Space Complexity

Only requires 1 extra temporary variable. O(1)

More Sort Algorithms

All differ in performance, and performance often depends on data characteristics.

• Insertion sort
• Selection sort
• Merge sort
• Bubble sort

Wikipedia: Comparison of algorithm performance, Sorting Algorithms Visualization

Which sort is best?

A great resource to help visualize the different sorting algorithms:

Insertion Sort

When is it best?

• Good for incremental sorting.


• When you need elements sorted, but you only get them a few at a time


• You run a calendar app. People insert events into the app one at a time and you need to sort the events

Bubble Sort

When is it best?

• When you are in computer science class


• When the values are mostly sorted

Merge Sort

When is it best?

• When you are combining already sorted arrays


• Two companies are merging and they each have seniority lists based on hire dates. They need to combine these lists into one sorted list.

What if...

You have 6 stacks of mostly sorted papers. How would you sort them all together?

1. Use bubble sort or selection sort to sort each pile


2. Use merge sort to combine the sorted piles

Explore more!

I focused on which type of data is good or bad for each sorting example, but each sorting algorithm also has its own space trade offs as well.

• Quick Sort
• Quick3 Sort
• Heap Sort
• Shell Sort

Searching with other data structures

Matrices

Arrays of arrays

Exercise

Linear search for matrices

Find maximum element of each row in a matrix

                    
Input :  [1, 2, 3]
         [1, 4, 9]
         [76, 34, 21]
Output :
[3, 9, 76]

Input : [1, 2, 3, 21]
        [12, 1, 65, 9]
        [1, 56, 34, 2]
Output :
[21, 65, 56]
                    
                

Solution

Searching with matrices

What is the time complexity?

O(n*m)

What is the space complexity?

O(n)

Linked Lists

Linked Lists

Linked lists wikipedia

Linked list implementation

class Node(object):

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next_node

    def set_next(self, new_next):
        self.next_node = new_next
                

Example in python

Exercise

Writing find max with Linked Lists

Complexity of linked lists

Other searching and sorting

Trees - breadth first and depth first search

Trees - binary search

Resources

• Khan Academy algorithms course - good review of material in this course
• Code Wars
• Bubble Sort Dance
• Intro to Whiteboarding (Amelia Downs)
• Project Euler - list of mathematical problems
• Practice!

Thank you!