Learn How to Code
  • Welcome
  • Foundations
    • Introduction
      • Becoming a web developer
      • Motivation and mindset
      • Join a supportive community
      • How does the web work?
    • Requirements
      • Prerequisites
      • Text editors
      • Command line basics
      • Setting up Git
      • Setting up Node
    • Git
      • Git basics
      • Project: Practicing Git
    • Frontend
      • HTML and CSS
      • Developer Tools
      • Project: Create a web page
    • JavaScript
      • Strings and Conditionals
      • Using Developer Tools
      • Functions
      • Problem solving
      • Project: Rock paper scissors
      • Writing clean code
      • Arrays and Loops
      • The DOM
      • Project: Etch-A-Sketch
      • Objects and More Arrays
      • Project: Calculator
    • Backend
      • Frameworks
    • Next steps
  • Deep dives
    • Computer Science
      • Pseudocode and algorithms
      • Recursion and algorithms
        • Project: Fibs and sorting
        • More on algorithms
        • Big O
        • Project: Practicing Big O
      • Data structures
        • Maps, Stacks and Queues
        • Project: Stacks and Queues
        • Nodes, Linked Lists and Trees
        • Project: Linked Lists
        • Project: Trees
        • Next steps
    • Databases
      • Databases and SQL
      • Project: SQL Zoo
    • Design / UX
      • Fonts and typography
      • Grids
      • Project: Teardown
      • Responsive design
      • Project: Mobile friendly
      • CSS frameworks
      • Project: Bootstrapping
    • HTML / CSS
      • HTML Basics
        • Linking
        • Images and media
        • Project: Embedding media
        • HTML5
        • Tables
        • Lists
        • Forms
        • Project: Make a form
      • CSS Basics
        • Box model
        • Floats and positioning
        • Flexbox
        • Grids
        • Project: Breaking news
        • Best practices
        • Backgrounds and gradients
        • Project: One more thing
        • CSS3
        • Preprocessors
        • Project: Your own framework
      • Next steps
    • JavaScript
      • Refresher
      • Organization
      • Objects and constructors
      • Project: Library
      • Factory functions and module patterns
      • Project: Tic Tac Toe
      • Classes
      • ES6 Modules
      • Project: Restaurant
      • Object Oriented Programming
      • Project: Todo list
      • Linting
      • Menus and sliders
      • Forms
      • ES6 features
      • JSON
      • Callbacks and promises
      • Using APIs
      • Async and Await
      • Project: Weather
      • Testing
      • Project: Testing 1-2-3
      • Advanced Testing
      • Project: Battleship
      • Backends
      • Project: Where's Waldo?
      • Project: All-Star
      • Next steps
    • NodeJS
      • Project: Going to school
      • Project: Passing the test
      • Express
        • Templates and middleware
        • CRUD and MVC
        • Project: Message board
        • Routes
        • Displaying data
        • Forms and deployment
        • Project: Inventory
      • Authentication
      • Security
      • Project: Clubhouse
      • APIs
      • Securing an API
      • Project: Blog
      • Testing
      • Testing with a database
      • Project: Social network
    • React
      • Props and State
      • Render lists and handle inputs
      • Project: CV
      • Lifecycle methods
      • Hooks
      • Project: Memory card
      • Router
      • Project: Shopping cart
      • Advanced concepts
    • Ruby
      • Installation
      • Data types
      • Variables
      • Input and Output
      • Conditionals
      • Loops
      • Arrays
      • Hashes
      • Methods
      • Enumerables
      • More enumerables
      • Nested collections
      • Blocks
      • Pattern matching
      • Debugging
      • Project: Caesar cipher
      • Project: Substrings
      • Project: Stock picker
      • Project: Bubble sort
      • Object oriented programming
      • Project: Tic Tac Toe
      • Project: Mastermind
      • Serialization
      • Project: Event manager
      • Project: Hangman
      • Computer Science
        • Recursion
        • Project: Merge Sort
        • Data structures and algorithms
        • Project: Linked Lists
        • Project: Binary Search Trees
        • Project: Knight Travails
      • Testing
      • RSpec
      • Project: Four in a row
      • Git
      • Project: Open Source
      • Project: Chess
      • Next steps
    • Ruby on Rails
      • Using Heroku
      • Installing Rails
      • Basics
        • Routing
        • Controllers
        • Views
        • Asset pipeline
        • Deployment
        • Project: Blog
      • Active Record
        • Project: Upvote
      • Forms
        • Cookies, sessions, and authentication
        • Project: Password
      • Advanced forms and Active Record
        • Associations
        • Project: Private Events
        • Callbacks
        • Menus, helpers and nested forms
        • Project: Ticket agent
      • APIs
        • External APIs
        • Project: Animals
        • Project: Photo widget
      • Mailers
        • Project: Confirmation
      • Advanced topics
        • Action Cable
      • Project: Social network
      • Next steps
  • Getting hired
    • Preparing to find a job
      • Plan a strategy
      • What companies want
      • Get yourself together
      • How to prepare
      • Project: Make your website
    • Applying and interviewing
      • Qualifying leads
      • Project: Make your resume
      • Applying for jobs
      • Preparing for an interview
      • Handling an offer
      • Final words
  • Maintained by
    • wbnns
  • License
    • CC BY-NC-SA 4.0 © 2022
Powered by GitBook
On this page
  • Introduction
  • Project Part 1 - Insertion Sort
  • Project Part 2 - Linear and Binary Search
  1. Deep dives
  2. Computer Science
  3. Recursion and algorithms

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.

PreviousBig ONextData structures

Last updated 4 years ago

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

  1. Write a method #insertion_sort which takes an array and returns the sorted array.

    • If you're stuck, .

  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.

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

  1. Write a method #linear_search which takes an array and a desired value, and returns the desired value if found, otherwise false.

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

  3. Write a methond #binary_search which takes the same parameters and returns the same way as your #linear_search,

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

  5. Test both methods against small sorted arrays where you know you will or won't find your wanted value.

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

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

If you unsure, we actually sneakily covered this very algorithm in our .

We also snuck this algorithm in our .

previous project
here is the wiki page for Insertion Sort
previous lesson
previous lesson