CS50x – Week 3

Written by on September 15, 2017 in Coding, CS50

Sort and Search

Last week we discovered strings are a data structure called an array. Arrays are contingent blocks in memory that we can use to store information. This week we will look at sorting arrays and searching arrays. There are several techniques to sorting data and searching data and each one takes a certain amount of time to complete. We use this to measure the efficiency of the algorithm. These levels of efficiency are more commonly known as Computational Complexity.

Computational Complexity

Computational Complexity or Time Complexity is the measurement of the runtime of an algorithm. The runtime is defined by the number of computational operations have to be made up until completion of the algorithm against the number of elements in the data structure. Each algorithm has a best runtime and worst runtime and average runtime. We usually look at the worst runtime often referred to the Big-O notation. From worst to best the big-o notation list consists of this:

O(n^2)
O(n log n)
O(n)
O(log n)
O(1)

O(1) is the best case runtime scenario because it does not matter how many element are in the array we can find it with only 1 operation. The worst case runtime scenario is O(n^2) as everytime an element is added to array it exponentially increases the number of operations needed.

Below is a graph visualising this concept.

Graph showing the time complexity of Big-O notation. The number of operations over the number of elements.

Searching Algorithms

We use searching algorithms to find data within a data structure. There are quite a few different searching algorithms but the two of the most common are the Linear search and Binary search.

Linear Search

Linear search is a simple searching algorithm. You iterate through the array 1 element at a time until you find what what you are looking for.

int linearsearch(int values[], int value, int n)
{
    for (int i=0; i<n; i++)
    {
        if (values[i] == value)
        {
             return i;
        }
    }
    return -1;
}

Linear Search is O(n) because the number of times we loop through the array is ‘n’ times. If x is not in the array we will have only looped through ‘n’ times.

Binary Search

Binary Search is an algorithm where you attempt to half the amount of data you need to search through each time. Back in week 0 there was the example of looking through a phone book to find a name. That example used a binary search to do so.
0. pick up phone book
1. open to middle of phone book
2. look at names
3. if Smith is among names
4. call Mike
5. else if Smith is earlier in book
6. open to middle of left half of book
7. go back to step 2
8. else if "Smith" is later in book
9. open to middle of right half of book
10. go back to step 2
11. else
12. quit

bool search(int value, int values[], int n)
{
    int start, end, mid;
    if(value <0)
    {
        return false;
    }
    else
    {
        start = 0;
        end = n;
        do
        {
            mid = ((start + end)/2);
            if (value == values[mid])
            {
                return true;
                break;
            }
            else if(value < values[mid]) 
            { 
                end = mid-1; 
            } 
            else if(value > values[mid])
            {
                start = mid +1;
            }
            n = end - start;
        }
        while ( n >= 0 );
        return false;
    }
}

The code above returns true or false whether the given value is present in the array. With binary search we are halving the amount of data we need to search with every pass of the loop, so it does not matter how many elements we add to the array the number of operations does not increase significantly. Binary search therefore has the notation of O(log n) making it a lot more efficient than a linear search. There is only one caveat to using binary search. The data in the array must be sorted in some order, which leads us on to sorting algorithms.

Sorting Algorithms

Sorting algorithms are as the name suggest, their function is to arrange data in order. There are many ways of sorting data but three of the most common are the bubble sort, selection sort and insertion sort.

Bubble Sort

The bubble sort is as its name suggests, where the highest value in the array bubbles its way to the top. It involves checking two adjacent value and if they are not in order, swap them, then move onto the next adjacent pair. This way the highest number is pushed to the top and the lower values are moved down.

 

 

GIF

Selection Sort

The selection sort involves splitting the array into 2 sub-lists, a sorted list and unsorted list. The algorithm finds the smallest value and moves it to the front of unsorted list, the boundary of the unsorted list is then moved to the right by 1 element thus creating the sorted list.

 

 

GIF

 

Insertion Sort

Insertion sort works similarly to selection sort in that its uses two lists. Insertion sort compares two values and moves out of the list and put it into the new list. It then checks the next pair of values and removes the smaller one and checks it against the sorted list and inserts it into the place it is supposed to go.

 

 

GIF

 

 

The animations above show how the algorithm sorts the data. The algorithms can be faster or slower than one another depending on the data set itself, i.e. how much of it is already sorted and the size of the data set. All three of these sorting algorithms have a run time of O(n^2). There are other sorting algorithms that have better run times but these were not covered in the lecture.

Problem Set 3

This weeks problems set asks us to implement 2 tasks.

  1. Implement either of:
    • Find, less comfortable
    • Find, more comfortable
  2. Implement Game of Fifteen

This is the first time the psets have provided us with source code that we must alter to complete the tasks. This is also the first time that we have to use pre-written code to help us generate data for us to use with our implementations. This is also the first time we are shown that we can use run one program and use the output data for that as the input for another program, whilst running it in the same command. We are also able to feed input into our program from an external source such a file.

Find

With Find there are two versions, less and more. The only difference between the two is the algorithms we need to implement as per the specification. The specification for the less version requires a O(log n) search algorithm and a O(n^2) sort algorithm. So we can use the binary search algorithm and either of the three sorting algorithms. The specification for the more version requires a O(log n) search algorithm, a binary search, and a O(n) sorting algorithm. Other sorting algorithms were not covered in the lecture, however in the supplementary walkthroughs that are provided with the psets the counting sort algorithm, which happens to be O(n) is briefly explained. The Counting sort is an algorithm that is of O(n). The counting sort requires you to know the highest and lowest values in your array and you create a new array size to that difference. You then iterate through the array and increment at the array index of the value in the original array. Once you have gone through the array, the indexes for the counting array should have values that correspond to the number of values in the original array. You then create a new array iterating through the counting array and adding values based on the index of the counting array.

I won’t go into too much details about the source code provided and I’ll only show my implementation of the problem.

 

see source
/**
* helpers.c
*
* Helper functions for Problem Set 3.
*/
#include <cs50.h>
#include "helpers.h"
/**
* Returns true if value is in array of n values, else false.
*/
//Binary Search O(log n)
bool search(int value, int values[], int n)
{
int start, end, mid;
if(value <0)
{
return false;
}
else
{
start = 0;
end = n;
do
{
mid = ((start + end)/2);
if (value == values[mid])
{
return true;
break;
}
else if(value < values[mid])
{
end = mid-1;
}
else if(value > values[mid])
{
start = mid +1;
}
n = end - start;
}
while ( n >= 0 );
return false;
}
}
/**
* Sorts array of n values.
*/
//Counting Sort O(n)
void sort(int values[], int n)
{
int MAX = 65536;
int count[MAX];
//Reset the array to 0 to avoid null values;
for (int i=0; i<MAX; i++)
{
count[i] = 0;
}
//Increment the count array value at the index of the values array
for (int i=0; i<n; i++)
{
count[values[i]]++;
}
//We can now fill the values array with the index value of the count array
//and decrement the count array values until they are empty
int index = 0;
for (int i=0; i<MAX; i++)
{
while (count[i] > 0)
{
values[index] = i;
index++;
count[i]--;
}
}
}
view raw helpers.c hosted with ❤ by GitHub

Game of Fifteen

Game of Fifteen is a game where you need to rearrange the numbers in a grid so that they are in sequential order. You can move one number at a time and only when a number is next to the empty space. This task first introduces us to game logic.

Game logic is usually broken down into 3 main categories:

Initialisation is as you would expect, it is setting up our game variables . Update is where the bulk of our game logic lies. It is where all the calculations of our game takes place. Update is usually called indefinitely until some condition is met (win or lose). Rendering is actually drawing our game to the screen and relaying user information. This usually takes place after update as to show the latest information.

This pset asks us to implement 4 functions. These 4 functions are:

Init

The init function serves to create the game board. We take the dimensions given from the user when starting the game and begin to fill a 2D array with numbers from the dimension squared to 1. We also have to check if the board has an even or odd number of tiles. If it is even we have to swap the 3rd to last and 2nd to last tile and keep the last tile blank.

/**
* Initializes the game's board with tiles numbered 1 through d*d - 1
* (i.e., fills 2D array with values but does not actually print them).
*/
void init(void)
{
// Find highest value for the board.
int value = (d*d)-1;
//Fill the board up with numbers
for (int i = 0; i < d; i++)
{
for (int j = 0; j < d; j++)
{
board[i][j] = value;
value--;
}
}
//If the board has even number of tiles swap the 3rd to last and 2nd to last tiles whilst the last tile is blank
if ((d*d) % 2 == 0)
{
int temp = board[d-1][d-3];
board[d-1][d-3] = board[d-1][d-2];
board[d-1][d-2] = temp;
}
//Record blank tile info
blank_row = d-1;
blank_col = d-1;
}
view raw fifteen.c hosted with ❤ by GitHub

 

Draw

Our draw function prints our game board to the screen. For this game it is relatively simple. We iterate through our 2D array and print the value. We also add some formatting and styling to make it look more appealing.

/**
* Prints the board in its current state.
*/
void draw(void)
{
//Go through the grid printing the value at that point
for(int i = 0; i <d; i++)
{
for (int j = 0;j < d; j++)
{
if(board[i][j] == 0)
{
printf(" _");
}
else
{
printf("%2i", board[i][j]);
}
//Prints a | between the numbers to improve visual appearance
if (j < d - 1)
{
printf(" |");
}
}
printf("\n");
}
}
view raw fifteen.c hosted with ❤ by GitHub

Move

This function returns a boolean value. It basically checks to see if the user input is valid and if so then swap the tiles.

/**
* If tile borders empty space, moves tile and returns true, else
* returns false.
*/
bool move(int tile)
{
//Check if tile is valid
if((tile < 1) || (tile > (d*d) - 1) )
{
return false;
}
//Search through grid to find the tile.
for (int i = 0; i<d; i++)
{
for (int j = 0; j <d; j++)
{
if (board[i][j] == tile)
{
tile_row = i;
tile_col = j;
}
}
}
//Check to see if it is a legal move.
//Check top, bottom, left and right to see if it is a blank space,if so swap.
//top
if(tile_row > 0 && board[tile_row - 1][tile_col] == 0)
{
swap();
return true;
}
//bottom
else if(tile_row < d - 1 && board[tile_row + 1][tile_col] == 0)
{
swap();
return true;
}
//left
else if(tile_col > 0 && board[tile_row][tile_col - 1] == 0)
{
swap();
return true;
}
//right
else if(tile_col < d - 1 && board[tile_row][tile_col + 1] == 0)
{
swap();
return true;
}
return false;
}
view raw fifteen.c hosted with ❤ by GitHub

Won

This function also returns a boolean value. We check every update to see if the conditions for winning the game have been met. This conditions in this case are if the 2D array is in sequential order and the last tile is blank. Once these conditions have been met the function will return true and the game will prompt us that we have won.

/**
* Returns true if game is won (i.e., board is in winning configuration),
* else false.
*/
bool won(void)
{
//initialise a counter
int count = 1;
//increment the counter if the board is in numerical order
for(int i = 0; i < d; i++)
{
for(int j = 0; j<d; j++)
{
if(board[i][j] == count)
{
count++;
}
}
}
//check that the count is correct and that the last space in the grid is blank
if(count == d*d && board[d-1][d-1] == 0)
{
return true;
}
else
{
return false;
}
}
view raw fifteen.c hosted with ❤ by GitHub

You can see a video of the game in action below.

see source
/**
* fifteen.c
*
* Implements Game of Fifteen (generalized to d x d).
*
* Usage: fifteen d
*
* whereby the board's dimensions are to be d x d,
* where d must be in [DIM_MIN,DIM_MAX]
*
* Note that usleep is obsolete, but it offers more granularity than
* sleep and is simpler to use than nanosleep; `man usleep` for more.
*/
#define _XOPEN_SOURCE 500
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
// constants
#define DIM_MIN 3
#define DIM_MAX 9
// board
int board[DIM_MAX][DIM_MAX];
// dimensions
int d;
// prototypes
void clear(void);
void greet(void);
void init(void);
void draw(void);
bool move(int tile);
bool won(void);
void swap();
//tile information
int blank_row;
int blank_col;
int tile_row;
int tile_col;
int main(int argc, string argv[])
{
// ensure proper usage
if (argc != 2)
{
printf("Usage: fifteen d\n");
return 1;
}
// ensure valid dimensions
d = atoi(argv[1]);
if (d < DIM_MIN || d > DIM_MAX)
{
printf("Board must be between %i x %i and %i x %i, inclusive.\n",
DIM_MIN, DIM_MIN, DIM_MAX, DIM_MAX);
return 2;
}
// open log
FILE *file = fopen("log.txt", "w");
if (file == NULL)
{
return 3;
}
// greet user with instructions
greet();
// initialize the board
init();
// accept moves until game is won
while (true)
{
// clear the screen
clear();
// draw the current state of the board
draw();
// log the current state of the board (for testing)
for (int i = 0; i < d; i++)
{
for (int j = 0; j < d; j++)
{
fprintf(file, "%2i", board[i][j]);
if (j < d - 1)
{
fprintf(file, "|");
}
}
fprintf(file, "\n");
}
fflush(file);
// check for win
if (won())
{
printf("ftw!\n");
break;
}
// prompt for move
printf("Tile to move: ");
int tile = get_int();
// quit if user inputs 0 (for testing)
if (tile == 0)
{
break;
}
// log move (for testing)
fprintf(file, "%2i\n", tile);
fflush(file);
// move if possible, else report illegality
if (!move(tile))
{
printf("\nIllegal move.\n");
usleep(500000);
}
// sleep thread for animation's sake
usleep(500000);
}
// close log
fclose(file);
// success
return 0;
}
/**
* Clears screen using ANSI escape sequences.
*/
void clear(void)
{
printf("\033[2J");
printf("\033[%d;%dH", 0, 0);
}
/**
* Greets player.
*/
void greet(void)
{
clear();
printf("WELCOME TO GAME OF FIFTEEN\n");
usleep(2000000);
}
/**
* Initializes the game's board with tiles numbered 1 through d*d - 1
* (i.e., fills 2D array with values but does not actually print them).
*/
void init(void)
{
// Find highest value for the board.
int value = (d*d)-1;
//Fill the board up with numbers
for (int i = 0; i < d; i++)
{
for (int j = 0; j < d; j++)
{
board[i][j] = value;
value--;
}
}
//If the board has even number of tiles swap the 3rd to last and 2nd to last tiles whilst the last tile is blank
if ((d*d) % 2 == 0)
{
int temp = board[d-1][d-3];
board[d-1][d-3] = board[d-1][d-2];
board[d-1][d-2] = temp;
}
//Record blank tile info
blank_row = d-1;
blank_col = d-1;
}
/**
* Prints the board in its current state.
*/
void draw(void)
{
//Go through the grid printing the value at that point
for(int i = 0; i <d; i++)
{
for (int j = 0;j < d; j++)
{
if(board[i][j] == 0)
{
printf(" _");
}
else
{
printf("%2i", board[i][j]);
}
//Prints a | between the numbers to improve visual appearance
if (j < d - 1)
{
printf(" |");
}
}
printf("\n");
}
}
/**
* If tile borders empty space, moves tile and returns true, else
* returns false.
*/
bool move(int tile)
{
//Check if tile is valid
if((tile < 1) || (tile > (d*d) - 1) )
{
return false;
}
//Search through grid to find the tile.
for (int i = 0; i<d; i++)
{
for (int j = 0; j <d; j++)
{
if (board[i][j] == tile)
{
tile_row = i;
tile_col = j;
}
}
}
//Check to see if it is a legal move.
//Check top, bottom, left and right to see if it is a blank space,if so swap.
//top
if(tile_row > 0 && board[tile_row - 1][tile_col] == 0)
{
swap();
return true;
}
//bottom
else if(tile_row < d - 1 && board[tile_row + 1][tile_col] == 0)
{
swap();
return true;
}
//left
else if(tile_col > 0 && board[tile_row][tile_col - 1] == 0)
{
swap();
return true;
}
//right
else if(tile_col < d - 1 && board[tile_row][tile_col + 1] == 0)
{
swap();
return true;
}
return false;
}
/**
* Returns true if game is won (i.e., board is in winning configuration),
* else false.
*/
bool won(void)
{
//initialise a counter
int count = 1;
//increment the counter if the board is in numerical order
for(int i = 0; i < d; i++)
{
for(int j = 0; j<d; j++)
{
if(board[i][j] == count)
{
count++;
}
}
}
//check that the count is correct and that the last space in the grid is blank
if(count == d*d && board[d-1][d-1] == 0)
{
return true;
}
else
{
return false;
}
}
void swap()
{
int temp = board[tile_row][tile_col];
board[tile_row][tile_col] = board[blank_row][blank_col];
board[blank_row][blank_col] = temp;
blank_row = tile_row;
blank_col = tile_col;
}
view raw fifteen.c hosted with ❤ by GitHub

 

This was CS50x Week 3. Next week is about strings, memory and image manipulation.

Leave a Reply

Your email address will not be published. Required fields are marked *

Comments«