# Week 4

## Last Time

• Last time we looked at numbers and how we might search them and sort them, with algorithms like:

• linear search

• binary search

• bubble sort

• selection sort

• insertion sort

• merge sort

• We started using basic terms to describe running time (in units of steps taken), like:

• n2

• n log n

• n

• log n

• 1

• …​

• The notation for running time includes:

• O, worst-case running time

• Ω, best-case running time

• Θ, if both of those are the same

## Strings

• Now we’ll take a closer look at strings and how they are actually stored by the computer.

• Let’s look at `compare0.c`:

``````#include <cs50.h>
#include <stdio.h>

int main(void)
{
printf("s: ");
string s = get_string();

printf("t: ");
string t = get_string();

if (s == t)
{
printf("same\n");
}
else
{
printf("different\n");
}
}``````
• It looks like this program takes two strings from the user and compares them.

• But it doesn’t work, when we put in two strings that look the same.

• Hm, mysterious. Let’s try to copy the string:

``````#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
printf("s: ");
string s = get_string();
if (s == NULL)
{
return 1;
}

string t = s;

if (strlen(t) > 0)
{
t[0] = toupper(t[0]);
}

printf("s: %s\n", s);
printf("t: %s\n", t);

return 0;
}``````
• Now we’re getting a string `s` from the user, copying it to a string called `t`, and then making the first letter of `t` uppercase.

• But when we run the program, it again doesn’t behave like we might expect. Both `s` and `t` are capitalized!

• Another example we can look at:

``````#include <stdio.h>

void swap(int a, int b);

int main(void)
{
int x = 1;
int y = 2;

printf("x is %i\n", x);
printf("y is %i\n", y);
printf("Swapping...\n");
swap(x, y);
printf("Swapped.\n");
printf("x is %i\n", x);
printf("y is %i\n", y);
}

void swap(int a, int b)
{
int tmp = a;
a = b;
b = tmp;
}``````
• We have a function called `swap` that’s supposed to take two values, `a` and `b`, and swaps them. It takes `a`, puts the value into a temporary variable called `tmp`, and then stores the value of `b` into `a`. Then the value of `tmp`, which is the original `a`, is stored into `b`.

• But when we run this program, too, it doesn’t swap the values of `x` and `y` in `main`.

• So we open our debugger, and step over each line of our program: