# 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.

## Introduction

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!

## Project Part 1 - Insertion Sort

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...

Write a method

`#insertion_sort`

which takes an array and returns the sorted array.If you're stuck, here is the wiki page for Insertion Sort.

Check that it works against smaller arrays.

Set a variable

`sorted_arr`

which will be the result of your`#insertion_sort`

against an array of 100000 or more values.Grab a cup of tea/coffee, it'll take a while.

Use

`#insertion_sort`

against the sorted_arr and observe how long it takes to complete.Do the same with your previously written

`#merge_sort`

, and compare the two in both situations.

## Project Part 2 - Linear and Binary Search

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...

Write a method

`#linear_search`

which takes an array and a desired value, and returns the desired value if found, otherwise false.If you unsure, we actually sneakily covered this very algorithm in our previous lesson.

Test this method against small arrays to ensure you've got it right.

Write a methond

`#binary_search`

which takes the same parameters and returns the same way as your`#linear_search`

,We also snuck this algorithm in our previous lesson.

Test this method against small

*sorted*arrays to ensure you've got it right.Test both methods against small sorted arrays where you know you will or won't find your wanted value.

Test both methods against small, deliberately unsorted arrays. Do they both work? Why, or why not?

Test both methods against a very large, sorted array. Are their discrepancies in performance? Why, or why not?

Last updated