Project: Practicing Big O
In this project, you'll be using your language of choice for writing an insertion sort and a merge sort and testing them against large unsorted and sorted arrays.
You've learned a lot a different
algorithms
and Big O
notation. You may still feel a bit nervous about navigating your way around Big O
; but this project should give you some practical experience in how algorithms behave!In this project, you'll be using your language of choice for writing an
insertion sort
and a merge sort
(if you haven't done the previous project), and testing them against large unsorted and sorted arrays.You will then be implementing a
Linear Search
and Binary Search
algorithm to tackle finding an element in these arrays; keeping in mind how long it takes each algorithm to complete it's search. So let's start with the sorting!First, we shall explore sorting arrays in a more practical and sensible fashion, let us start by comparing
insertion sort
with our previously made merge sort
.In your language of choice...
- 1.Write a method
#insertion_sort
which takes an array and returns the sorted array. - 2.Check that it works against smaller arrays.
- 3.Set a variable
sorted_arr
which will be the result of your#insertion_sort
against an array of 100000 or more values. - 4.Grab a cup of tea/coffee, it'll take a while.
- 5.Use
#insertion_sort
against the sorted_arr and observe how long it takes to complete. - 6.Do the same with your previously written
#merge_sort
, and compare the two in both situations.
Now that we figured out how to bring order to the chaos that is our data; let us be able to find what we want within said data with
linear search
and binary search
.In your language of choice...
- 1.Write a method
#linear_search
which takes an array and a desired value, and returns the desired value if found, otherwise false. - 2.
- 3.Test this method against small arrays to ensure you've got it right.
- 4.Write a methond
#binary_search
which takes the same parameters and returns the same way as your#linear_search
, - 5.
- 6.Test this method against small sorted arrays to ensure you've got it right.
- 7.Test both methods against small sorted arrays where you know you will or won't find your wanted value.
- 8.Test both methods against small, deliberately unsorted arrays. Do they both work? Why, or why not?
- 9.Test both methods against a very large, sorted array. Are their discrepancies in performance? Why, or why not?
Last modified 2yr ago