Sorting Algorithms

Starting my journey off with topics that I find most interesting seems like a good way to begin. Let’s dive in to a short discussion on some basic algorithms. Algorithms generally insight alot of fear and so it is my hope to ease some of the pain for those not very hip to the matter. Coming from a science background my general way of getting to know things of complexity is by starting with the most empirical examples and then kind of gradually building up from there.

Linear Search

Linear search is by far the best first step in any learning of algorithms, based off of its simplicity. Linear Search is a search through a sorted or unsorted list, checking one element at a time in a Linear fashion in order to find a match for some desired element.
Its Worst Case run time is: O(n2)
Its Best Case run time is: Omega(1)
O(n2) means that this search will take an increase in time in a parabolic fashion as the search proceeds in steps. In code this search will translate into no more than 8 lines of code.

[lang: ruby]
1
2
3
4
5
6
7
8
arr = [1,2,3,4,5,6,7,8,9]
target = 5
    while i < arr.length 
      if  arr[i] == target 
        return i 
      end 
    i += 1
    end

As you can see, this method is mostly brute force and not much complex searching is going on. Lets build from this, onto a more complex algorithm.

Bubble Sort

Bubble sort isn’t an algorithm with many moving parts but it is a bit more complex than a Linear Search. In Bubble Sort you will iterate through a list of numbers and each pair of numbers, you will need to compare them. If the number to the left(n) is bigger than the number to the right(n+1), you will need to swap the larger number for the lesser number. Eventually all the larger numbers will bubble up to the right and the lesser numbers will move to the left. In order to know when to break the sort you need to keep track of swaps. In the end the sort will know to stop when it made a run an no swap was made.

Its Worst Case Run time is: O(N2)
Its Best Case run time is: Omega(1)

[lang: ruby]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
array = [1,4,5,6,8,9,3,7]

 n = array.length
  while true   #run an infinite loop
    swapped = false

    (n-1).times do |i|
      if array[i] > array[i+1] 
        array[i], array[i+1] = array[i+1], array[i] # set the left to the right and the right to the left 
        swapped = true #keep track of swaps
      end
    end

    break if !swapped 
  end

  print array

This algorithm was a bit more complex but in only one of two ways. First and foremost you have to know how to properly use an infinite loop.

Binary Search

A binary search follows the logic that: If given an array of values that are randomly sorted, Check the middle of the array and see if it is the value you are looking for. If it is, return the value. If it is not, Check if it is bigger than the value you are looking for and then throw away the right half and search through the left half from the middle value. If it is not bigger than the value you are searching for, throw away the left half and search through the right half from the middle value.

Binary Search follows a Big O or Asymptotic Complexity of: O(LogN) and it only works if: array is sorted, and that you actually have an array to search

//Set values for the top and bottom of the search lower = 0 upper = n-1

//Binary Search def binary_search(arr, value) while lower <= upper

//Find The Middle
 middle = (arr.length)/2 

//Compare the middle to the value you want
 if arr[middle] == value
 return true
 elsif arr[middle] < value
 lower = middle + 1
 else arr[middle] > value
 upper = middle - 1
 end 

end end