Young Coders: Week 4 Notes

-

Sorting and Searching

  • Bubble Sort, Insertion Sort, Selection Sort
  • Linear Search, Binary Search

How to swap two elements

We first looked at how to swap two elements. Let's say we have 

int a = 2;
int b = 3;

and we want to switch their values, so that a = 3 and b = 2. 

Remember, we can't just say:

a = b;
b = a;

As we saw on the whiteboard yesterday, this will make both a and b equal to 3, instead of switching their values: 


One way to switch a and b's values is by using a "temp" variable: 

int temp = a;
a = b;
b = temp; 

And the corresponding diagram we drew: 

a is now 3 and b is now 2 ... this works! 

Sorting 

We went over three algorithms for sorting a list of elements (in ascending order). 

Bubble Sort

Here is our method for bubble sort. We are comparing every pair of elements, and if the second one is smaller than the first one, we swap them. You can try simulating this by taking a few cards from a deck and sorting them. 

 public static int[] bubble(int[] array) {
    int temp; 
    
    for(int i = 0; i < array.length; i++) {
      for(int j = i+1; j < array.length; j++) {
        if(array[i] > array[j]) {
          temp = array[i]; 
          array[i] = array[j];
          array[j] = temp; 
        }
      }
    }
    
    return array; 
  }

That wasn't too efficient...can we do better? 

Insertion Sort

This algorithm divides the array into parts: a sorted part and an unsorted part. Each time around, it takes the next element in the unsorted part and moves that element to its correct place in the sorted part. 

  public static int[] insertion(int[] array) {
    int temp; 
    
    for(int i = 1; i < array.length; i++) {
      int j = i; 
      while((j>0) && (array[j] < array[j-1])) {
        temp = array[j];
        array[j] = array[j-1]; 
        array[j-1] =temp;
        j--; 
      }
    }
    
    return array; 
  }

Selection Sort

Selection sort also divides the array into a sorted part and an unsorted part. Each time, it takes the smallest element in the unsorted part and moves it to the end of the sorted part. 

  public static int[] selection(int[] array) {
    int min; //index of minimum
    int temp; 
    
    for(int i = 0; i < array.length; i++) {
      min = i; 
      
      for(int j = i+1; j < array.length; j++) 
        if(array[j] < array[min]) 
          min = j; 
         
      temp = array[i];
      array[i] = array[min];
      array[min] = temp;
    }
    
    return array; 
  }

Searching

Linear Search

Linear search is pretty straightforward. One way to search an array for an element is just going in order (proceeding linearly). Here is our code from yesterday. We tested our linear search method with the array {1,10,5,-4} and looked for 5 (our "key"). Our method returns the index of our key, 2. If our key had been 100, our method would have returned -1. 

public class SearchingIsFun {
  public static int linearSearch(int[] array, int key) {
    for(int i = 0; i < array.length; i++) 
      if(array[i] == key)
       return i;
    
    return -1; 
  }
  
  public static void main(String[] args) {
    System.out.println(linearSearch(new int[] {1, 10, 5, -4}, 5));
  }
}

Binary Search

Another searching algorithm is called a "binary search". Before talking about it, imagine a game of "Guess The Number"...

"I'm thinking of a number between 1 and 100."

"Is your number 50?"

"It is higher than 50."

"Is your number 75?"

"It is lower than 75." 

"Is your number 62?"

"It is higher than 62."

"Is your number 68?"

"It is lower than 68."

"Is your number 65?"

"You got it! My number is 65!"

One strategy for "Guess the Number" is always guessing the middle number in the possible range. As a result, the possible range also halves each time. That's what the binary search algorithm does. 

Let's go over binary search in an array of ints. Note: Make sure the array is already sorted before you perform a binary search! 

In our example, we searched for 551, the "key". The arrows "low" and "high" keep track of the range in where our key could be. I took the images from the following website:

http://www.cdf.toronto.edu/~ajr/104/diary/06/binarysearchslides/

What if our key is not in the array? Suppose the key is 552: 

Finally, here is our binary search method from yesterday: 
import java.util.Arrays; 

 public class BinarySearch {
  public static int binSearch(int[] a, int key) {
    int lo = 0;
    int hi = a.length-1; 
    
    while(lo <= hi) {
      int mid = lo + (hi-lo)/2; 
      
      if(key < a[mid]) 
        hi = mid-1; 
      else if(key > a[mid])
        lo = mid+1;
      else
        return mid; 
    }
    
    return -1; 
  }
  
  public static void main(String[] args) {
    int[] test = {30, 40, 2}; 
    Arrays.sort(test); 
    
    System.out.println(binSearch(test, 40)); 
  }
}



Popular posts from this blog

Space Race: a simple Rust game built on the Bevy framework

-
Image
When I saw a post announcing the release of the Bevy framework  (an open source game engine written in Rust), I thought it'd be a fun way to learn Rust.  So I made Space Race , a 2 player game on top of the Bevy framework. How to Play The Astronaut moves around collecting jewels (using WASD keys). The Alien moves around trying to catch the Astronaut (using arrow keys).  The Astronaut wins if they collect at least 5 jewels and make it back to home base before the Alien catches them.  The Alien wins otherwise.  Things I learned about Rust  I had a lot of fun making & playing this game, and also got some hands on experience with Rust like working with structs enums vectors iterators traits dyn trait vs impl trait  dyn trait is used for trait objects, which are fat pointers made up of 1) a pointer to the value 2) a pointer to a vtable. A vtable is a table of methods, where each method points to its implementation, generated once at compile time. Each i...
Read more

Building a Toy Language Compiler in Go

-
Image
A follow-up to my previous post about building a toy language interpreter in Go. Throughout this post, I'll be referencing my repo . We'll go over a compiler which translates source code to machine code, and then a VM to execute this machine code. What is a compiler?  A compiler takes source code and translates it to executable machine code . (See my previous post for more details.) The figure below shows the high-level architecture of a simple compiler. Like the interpreter we built previously, our compiler has a lexer and a parser which turn our source code into an AST . This is our compiler's frontend . However, that's where a compiler diverges.  The compiler may translate the AST into at least one internal representation (IR) . The IR(s) may be represented using any data structure (even another AST!), but they should follow two rules: (1) be easy to produce, (2) be easy to translate into the target machine code. The IR can also be optimized...
Read more

tldr: Raft + Implementation Tips

-
Image
Part of the tldr series , which summarizes papers I'm currently reading. Inspired by the morning paper . Raft (Extended Version) + Implementation Tips [2014] Ongaro et al. Note: For implementation tips, see the end of this blog post.  Introduction Consensus algorithms The r eplicated state machine approach  is useful for providing fault-tolerance in distributed systems. It lets a cluster of unreliable machines continue operating even when some of its members fail. In this approach, machines   usually use a replicated log to stay in sync. As shown in the figure below, each server's log stores the same commands in the same order. Every state machine executes commands from its own log in order. State machines are deterministic, so each produces the same order of outputs. Once the majority of machines have responded, the command is done executing. Consensus algorithms ensure that the replicated log stays consistent. In the figure above, clients s...
Read more