This is CS5❤️
Think.
Pair.
Share.
Structs
typedef struct
{
string name;
int votes;
}
candidate;
typedef struct
{
string name;
int votes;
}
candidate;
typedef struct
{
string name;
int votes;
}
candidate;
typedef struct
{
string name;
int votes;
}
candidate;
candidate president;
candidate president;
president.name = "Alyssa";
president.votes = 10;
Struct Exercise
Create a struct to represent a candidate in an election that minimally includes:
Add attributes to a candidate and print those out to the user.
Structs and Functions Exercise
Create your own get_candidate function that prompts the user to input attributes for a candidate. You may rely on get_string, get_float, etc., and your function should return a candidate.
Array of Structs
name | Alice | Bob | Charlie |
votes | 2 | 1 | 3 |
name | Alice | Bob | Charlie |
votes | 2 | 1 | 3 |
candidates[0];
name | Alice | Bob | Charlie |
votes | 2 | 1 | 3 |
candidates[0];
name | Alice | Bob | Charlie |
votes | 2 | 1 | 3 |
candidates[0].name;
name | Alice | Bob | Charlie |
votes | 2 | 1 | 3 |
candidates[0].votes;
Arrays of Structs Exercise
Use your get_candidate function to create an array of three candidates, each of which should have attributes input by the user.
Searching
Think.
Pair.
Share.
• When might it make sense to sort before searching?
• When would it make sense to simply search?
Linear Search
Runtime analysis
O(N) — "worst case" definition
In the worst case, I need to do approximately N steps for an input of size N.
O(N) — "scaling" definition
For every new item that gets added to my algorithm's input, the algorithm needs to do a fixed number of new steps. We say "our runtime scales linearly with the size of our input".
Ω(1) — "best case" definition
In the best case, for instance where the element is found at the first index.
Sorting
Some Sorting Algorithms
Bubble Sort
5
3
4
8
2
1
7
6
3
5
4
8
2
1
7
6
3
4
5
8
2
1
7
6
3
4
5
2
8
1
7
6
3
4
5
2
1
8
7
6
3
4
5
2
1
7
8
6
3
4
5
2
1
7
6
8
3
4
5
2
1
7
6
8
3
4
2
5
1
7
6
8
3
4
2
1
5
7
6
8
3
4
2
1
5
6
7
8
3
4
2
1
5
6
7
8
3
2
4
1
5
6
7
8
3
2
1
4
5
6
7
8
3
2
1
4
5
6
7
8
2
3
1
4
5
6
7
8
2
1
3
4
5
6
7
8
2
1
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
Repeat for every element in our list, except last:
Look at each element from first to second-to-last:
If current and next elements out of order:
Swap them
Repeat n - 1 times
For j from 0 to n - 2
If j'th and j + 1'th elements out of order
Swap them
Runtime analysis
O(N2) — "worst case" definition
In the worst case, say when elements are in reverse order, I need to do approximately N2 steps if my input size is N.
O(N2) — "scaling" definition
For every new item that gets added to my input, I need to do approximately N2 new steps.
Ω(N) — "best case" definition
In the best case, say when all elements are already sorted, I need to do approximately N steps if my input size is N.
Selection Sort
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
1
3
4
8
2
5
7
6
1
3
4
8
2
5
7
6
1
3
4
8
2
5
7
6
1
2
4
8
3
5
7
6
1
2
4
8
3
5
7
6
1
2
4
8
3
5
7
6
1
2
3
8
4
5
7
6
1
2
3
8
4
5
7
6
1
2
3
8
4
5
7
6
1
2
3
4
8
5
7
6
1
2
3
4
8
5
7
6
1
2
3
4
8
5
7
6
1
2
3
4
5
8
7
6
1
2
3
4
5
8
7
6
1
2
3
4
5
8
7
6
1
2
3
4
5
8
7
6
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
Runtime analysis
O(N2) — "worst case" definition
In the worst case, I need to do approximately N2 steps if my input size is N.
Ω(N2) — "best case" definition
Even in the best case, I still need to do approximately N2 steps if my input size is N.
Merge Sort
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
4
8
5
3
2
1
7
6
4
8
5
3
2
1
7
6
4
8
5
3
2
1
7
6
4
8
5
3
2
1
7
6
4
8
5
3
2
1
7
6
4
8
5
3
2
1
7
6
4
8
5
3
2
1
7
6
4
8
5
3
2
1
7
6
4
8
5
3
2
1
7
6
4
8
5
3
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4 8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
3
5 4
8
2
1
7
6
5
3
4
8
2
1
7
6
3
4
8
5
2
1
7
6
3
4
8
5
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
7
6
2
1
5
3
4
8
7
6
2
1
5
3
4
8
7
6
2
1
5
3
4
8
7
6
2
1
5
3
4
8
7
6
2
1
5
3
4
8
7
6
2
1
5
3
4
8
7
6
2
1
5
3
4
8
7
6
2
1
5
3
4
8
7
6
2
1
5
3
4
8
7
6
2
1
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
6
7
5
3
4
8
2
1
6
7
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
5
3
4
8
2
1
7
6
5
3
4
2
1
7
6
8
5
3
4
2
1
7
6
8
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
Runtime analysis
5
3
4
8
2
1
7
6
5
3
4
8
2
1
7
6
5
3
4
8
5
3
2
1
7
6
2
1
7
6
4
8
O(N log2(N)) — "worst case" definition
In the worst case, I need to do about log2(N) steps to find my solution, for N elements.
O(N log2(N)) — "scaling" definition
I don't need to take another step/level in my algorithm until I double my input.
Ω(N log2(N)) — "best case" definition
In the best case as well, I need to do about log2(N) steps/levels to find my solution, for N elements.
Time Complexities of the 3 sorting algorithms
Algorithm | Time Complexity | |
Best case | Worst case | |
Bubble sort | Ω(N) | O(N2) |
Selection sort | Ω(N2) | O(N2) |
Merge sort | Ω(N logN) | O(N logN) |
Sort
.txt file used | Real Time Taken for Each Algorithm (in seconds) | ||
sort1 | sort2 | sort3 | |
sorted 5000 | | | |
sorted 10000 | | | |
sorted 50000 | | | |
reversed 5000 | | | |
reversed 10000 | | | |
reversed 50000 | | | |
random 5000 | | | |
random 10000 | | | |
random 50000 | | | |
Plurality
Watch Shorts
Office Hours
This was CS5❤️