-
Notifications
You must be signed in to change notification settings - Fork 0
/
Source.cpp
71 lines (56 loc) · 2.16 KB
/
Source.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;
const int MAX = 26;
void sortByAlgorithm(string& s);
void sortByHash(string& s);
int main() {
string letters;
string lettersSorted;
cout << "Welcome\n\n";
cout << "Please enter a string of letters to be alphabetized\n";
cout << "Note: do not use spaces between letters\n";
cout << "Letters: ";
cin >> letters;
cout << endl;
sortByAlgorithm(letters);
cout << "Sorted Letters (Using built-in sort): ";
cout << letters;
cout << "\n\nTime Complexity: O(n * log n), where n is the length of the string\n\n";
cout << "Note: Notice how uppercase letters are not sorted properly\n";
cout << "This is because the built-in sorting algorithm works by comparing the ascii values ";
cout << "associated with each character and uppercase letters have relatively lower values than ";
cout << "their lowercase equivalents\n\n";
cout << "Enter another string of letters to be alphabetized\n";
cout << "Letters: ";
cin >> letters;
cout << endl;
cout << "Sorted Letters (Using hash): ";
sortByHash(letters);
cout << "\n\nTime Complexity: O(n), where n is the length of the string\n\n";
cout << "Note: Notice how uppercase letters are ignored\n";
return 0;
}
void sortByAlgorithm(string& s) {
sort(s.begin(), s.end());
}
void sortByHash(string& s) {
// Purpose: This hash array simply keeps track of the occurances of a given letter.
// Initialize it to zero to avoid unwanted address values in unused indexes.
int count[MAX] = { 0 };
// Traverse string and increment character count
// Subtract the ASCII code of the character 'a' from the ASCII code of the current character to determine
// its position in the count array (since the lowercase letters are contiguous in the ASCII table.
for (int i{ 0 }; i < s.length(); i++) {
count[s[i] - 'a']++;
}
// Traverse the hash array and print each letter sequentially the number of times it appeared in the original string.
// Cast the result of the expression ('a' + i) to a char datatype using (char)(expression)
for (int i{ 0 }; i < MAX; i++) {
for (int j{ 0 }; j < count[i]; j++) {
cout << (char)('a' + i);
}
}
}