CS50 Problem Set 3#

1
sort1 uses: bubble sort
2

3
How do you know?: When sorting the sorted numbers, bubble sort's time complexity is omega(n); while sorting the random numbers, bubble sort's time complexity is O(n^2).
4

5
sort2 uses: merge sort
6

7
How do you know?: the time sort2 uses to sort every kind of txt is the least between the three sorts.
8

9
sort3 uses: selection sort
10

11
How do you know?: the time it uses to sort three kinds of txt is almost the same, but it cost more time than sort2.

1
#include <cs50.h>
2
#include <stdio.h>
3
#include <string.h>
4

5
// Max number of candidates
6
#define MAX 9
7

8
// Candidates have name and vote count
9
typedef struct
10
{
11
    string name;
12
    int votes;
13
} candidate;
14

15
// Array of candidates
16
candidate candidates[MAX];
17

18
// Number of candidates
19
int candidate_count;
20

21
// Function prototypes
22
bool vote(string name);
23
void print_winner(void);
24

25
int main(int argc, string argv[])
26
{
27
    // Check for invalid usage
28
    if (argc < 2)
29
    {
30
        printf("Usage: plurality [candidate ...]\n");
31
        return 1;
32
    }
33

34
    // Populate array of candidates
35
    candidate_count = argc - 1;
36
    if (candidate_count > MAX)
37
    {
38
        printf("Maximum number of candidates is %i\n", MAX);
39
        return 2;
40
    }
41
    for (int i = 0; i < candidate_count; i++)
42
    {
43
        candidates[i].name = argv[i + 1];
44
        candidates[i].votes = 0;
45
    }
46

47
    int voter_count = get_int("Number of voters: ");
48

49
    // Loop over all voters
50
    for (int i = 0; i < voter_count; i++)
51
    {
52
        string name = get_string("Vote: ");
53

54
        // Check for invalid vote
55
        if (!vote(name))
56
        {
57
            printf("Invalid vote.\n");
58
        }
59
    }
60

61
    // Display winner of election
62
    print_winner();
63
}
64

65
// Update vote totals given a new vote
66
bool vote(string name)
67
{
68
    for (int i = 0; i < candidate_count; i++)
69
    {
70
        if (strcmp(candidates[i].name, name) == 0)
71
        {
72
            candidates[i].votes += 1;
73
            return true;
74
        }
75
    }
76
    return false;
77
}
78

79
// Print the winner (or winners) of the election
80
void print_winner(void)
81
{
82
    int highest = 0;
83
    string name;
84
    for (int i = 0; i < candidate_count; i++)
85
    {
86
        if (candidates[i].votes > highest)
87
        {
88
            highest = candidates[i].votes;
89
        }
90
    }
91
    for (int i = 0; i < candidate_count; i++)
92
    {
93
        if (candidates[i].votes == highest)
94
        {
95
            printf("%s\n", candidates[i].name);
96
        }
97
    }
98
    return;
99
}

1
#include <cs50.h>
2
#include <stdio.h>
3
#include <string.h>
4

5
// Max voters and candidates
6
#define MAX_VOTERS 100
7
#define MAX_CANDIDATES 9
8

9
// preferences[i][j] is jth preference for voter i
10
int preferences[MAX_VOTERS][MAX_CANDIDATES];
11

12
// Candidates have name, vote count, eliminated status
13
typedef struct
14
{
15
    string name;
16
    int votes;
17
    bool eliminated;
18
} candidate;
19

20
// Array of candidates
21
candidate candidates[MAX_CANDIDATES];
22

23
// Numbers of voters and candidates
24
int voter_count;
25
int candidate_count;
26

27
// Function prototypes
28
bool vote(int voter, int rank, string name);
29
void tabulate(void);
30
bool print_winner(void);
31
int find_min(void);
32
bool is_tie(int min);
33
void eliminate(int min);
34

35
int main(int argc, string argv[])
36
{
37
    // Check for invalid usage
38
    if (argc < 2)
39
    {
40
        printf("Usage: runoff [candidate ...]\n");
41
        return 1;
42
    }
43

44
    // Populate array of candidates
45
    candidate_count = argc - 1;
46
    if (candidate_count > MAX_CANDIDATES)
47
    {
48
        printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
49
        return 2;
50
    }
51
    for (int i = 0; i < candidate_count; i++)
52
    {
53
        candidates[i].name = argv[i + 1];
54
        candidates[i].votes = 0;
55
        candidates[i].eliminated = false;
56
    }
57

58
    voter_count = get_int("Number of voters: ");
59
    if (voter_count > MAX_VOTERS)
60
    {
61
        printf("Maximum number of voters is %i\n", MAX_VOTERS);
62
        return 3;
63
    }
64

65
    // Keep querying for votes
66
    for (int i = 0; i < voter_count; i++)
67
    {
68

69
        // Query for each rank
70
        for (int j = 0; j < candidate_count; j++)
71
        {
72
            string name = get_string("Rank %i: ", j + 1);
73

74
            // Record vote, unless it's invalid
75
            if (!vote(i, j, name))
76
            {
77
                printf("Invalid vote.\n");
78
                return 4;
79
            }
80
        }
81

82
        printf("\n");
83
    }
84

85
    // Keep holding runoffs until winner exists
86
    while (true)
87
    {
88
        // Calculate votes given remaining candidates
89
        tabulate();
90

91
        // Check if election has been won
92
        bool won = print_winner();
93
        if (won)
94
        {
95
            break;
96
        }
97

98
        // Eliminate last-place candidates
99
        int min = find_min();
100
        bool tie = is_tie(min);
101

102
        // If tie, everyone wins
103
        if (tie)
104
        {
105
            for (int i = 0; i < candidate_count; i++)
106
            {
107
                if (!candidates[i].eliminated)
108
                {
109
                    printf("%s\n", candidates[i].name);
110
                }
111
            }
112
            break;
113
        }
114

115
        // Eliminate anyone with minimum number of votes
116
        eliminate(min);
117

118
        // Reset vote counts back to zero
119
        for (int i = 0; i < candidate_count; i++)
120
        {
121
            candidates[i].votes = 0;
122
        }
123
    }
124
    return 0;
125
}
126

127
// Record preference if vote is valid
128
bool vote(int voter, int rank, string name)
129
{
130
    for (int i = 0; i < candidate_count; i++)
131
    {
132
        if (strcmp(candidates[i].name, name) == 0)
133
        {
134
            preferences[voter][rank] = i;
135
            return true;
136
        }
137
    }
138
    return false;
139
}
140

141
// Tabulate votes for non-eliminated candidates
142
void tabulate(void)
143
{
144
    for (int i = 0; i < voter_count; i++)
145
    {
146
        for (int j = 0; j < candidate_count; j++)
147
        {
148
            if (!candidates[preferences[i][j]].eliminated == true)
149
            {
150
                candidates[preferences[i][j]].votes += 1;
151
                break;
152
            }
153
        }
154
    }
155
    return;
156
}
157

158
// Print the winner of the election, if there is one
159
bool print_winner(void)
160
{
161
    int limit = voter_count / 2;
162
    for (int i = 0; i < candidate_count; i++)
163
    {
164
        if (!candidates[i].eliminated && (candidates[i].votes > limit))
165
        {
166
            printf("%s\n", candidates[i].name);
167
            return true;
168
        }
169
    }
170
    return false;
171
}
172

173
// Return the minimum number of votes any remaining candidate has
174
int find_min(void)
175
{
176
    int min = 0;
177
    for (int i = 0; i < candidate_count; i++)
178
    {
179
        if (!candidates[i].eliminated)
180
        {
181
            if (i == 0)
182
            {
183
                min = candidates[i].votes;
184
            }
185
            if (candidates[i].votes < min)
186
            {
187
                min = candidates[i].votes;
188
            }
189
        }
190
    }
191
    return min;
192
}
193

194
// Return true if the election is tied between all candidates, false otherwise
195
bool is_tie(int min)
196
{
197
    for (int i = 0; i < candidate_count; i++)
198
    {
199
        if (!candidates[i].eliminated && candidates[i].votes != min)
200
        {
201
            return false;
202
        }
203
    }
204
    return true;
205
}
206

207
// Eliminate the candidate (or candidates) in last place
208
void eliminate(int min)
209
{
210
    for (int i = 0; i < candidate_count; i++)
211
    {
212
        if (!candidates[i].eliminated && candidates[i].votes == min)
213
        {
214
            candidates[i].eliminated = true;
215
        }
216
    }
217
    return;
218
}