First, write an algorithm that takes in an array of strings, sorts each string, and then sorts the full array. Second, calculate the time complexity (Big O) of this algorithm.
To sort each individual string in the array, we would start by looping through the whole array, sorting each string element, and either replacing the strings in the original array with their sorted versions, or building a new array with the sorted strings.
Then, to sort the whole array, we would perform some sorting function on it.
function sortArrayOfStrings(arr) {
let newArr = []
for (let i = 0; i < arr.length; i++) {
// TODO: Assign the variable "sortedString" to the result of some string sorting function.
newArr.push(sortedString)
}
// TODO: use some array sorting function to sort newArr.
return newArr
}Notice that we need helper functions in a couple of places. We first need a helper function that can take in a string and sort it. We used a version of the quick sort approach, though there are other options as well. In this version, we pick the first character in the string as our pivot value, then evaluate each subsequent character and place it to the "right" or the "left" of that pivot. (We use rightString and leftString to store these characters.) Then we recursively sort the right and left segments.
function stringQuickSort(str) {
if (str.length < 2) {
return str
}
else {
let leftString = ''
let rightString = ''
for (let i = 1; i < str.length; i++) {
if (str[i] >= str[0]) {
rightString = rightString + str[i]
}
else {
leftString = leftString + str[i]
}
}
return stringQuickSort(leftString) + str[0] + stringQuickSort(rightString)
}
}stringQuickSort can serve as our first helper function, but we also need a helper function to sort the array that we built in our for loop. Javascript has an inbuilt sorting function for arrays, but in this case it's good to write our own, since we can then evaluate its time complexity. The example below takes the same quick sort approach we used in to sort a string to sort an array.
function arrayQuickSort(arr) {
if (arr.length < 2) {
return arr
}
else {
let leftArr = []
let rightArr = []
for (let i = 1; i < arr.length; i++) {
// In the next line, we compare two strings.
if (arr[i] >= arr[0])) {
rightArr.push(arr[i])
}
else {
leftArr.push(arr[i])
}
}
return [...arrayQuickSort(leftArr), arr[0], ...arrayQuickSort(rightArr)]
}
}Notice that a crucial step of our arrayQuickSort function is to compare two strings. It looks like a simple one-step process, because Javascript has a built-in way of comparing strings. But we don't necessarily know what Javascript is doing under the hood, so it's helpful to write our own function to decide if one string is "bigger than" another. That way we can evaluate the time complexity. (Remember that the set of all strings, as opposed to the set of all characters encoded in a particular language, is infinite. So you can't necessarily rely on that one-step comparison for strings that you can for characters.)
One simple way to compare strings is to write a loop that iterates through the longer string and compares the characters in each string at the given index. If one character is "bigger" than the other, you can stop looping and return the result.
function isBiggerOrEqualString(str1, str2) {
let longerString = (str1.length >= str2.length) ? str1 : str2
for (let i = 0; i < longerString.length; i++) {
if (!str1[i]) {
return false
}
if (!str2[i]) {
return true
}
if (str1[i] >= str2[i]) {
return true
}
if (str1[i] < str2[i]) {
return false
}
}
}If we plug our new isBiggerOrEqualString function into our array sorting helper function, we get this:
function arrayQuickSort(arr) {
if (arr.length < 2) {
return arr
}
else {
let leftArr = []
let rightArr = []
for (let i = 1; i < arr.length; i++) {
if (isBiggerOrEqualString(arr[i], arr[0])) {
rightArr.push(arr[i])
}
else {
leftArr.push(arr[i])
}
}
return [...arrayQuickSort(leftArr), arr[0], ...arrayQuickSort(rightArr)]
}
}Then we can plus our two main helper functions into the main function, like so:
function sortArrayOfString(arr) {
let newArr = []
for (let i = 0; i < arr.length; i++) {
let sortedString = stringQuickSort(arr[i])
newArr.push(sortedString)
}
newArr = arrayQuickSort(newArr)
return newArr
}Then we can test our function with some examples, including edge cases like an empty array, an array with an empty string inside, and an array with two strings that are almost identical, but one is longer.
console.log(sortArrayOfString(['abc', 'ffe', 'ewu', 'fuiesbvre'])) //=> [ 'abc', 'beefirsuv', 'eff', 'euw' ]
console.log(sortArrayOfString(['', 'ffe', 'ewu', 'fuiesbvre'])) //=> [ '', 'beefirsuv', 'eff', 'euw' ]
console.log(sortArrayOfString(['', 'ffe', 'ffea', 'ewu', 'fuiesbvre'])) //=> [ '', 'aeff', 'beefirsuv', 'eff', 'euw' ]
console.log(sortArrayOfString([])) //=> []
console.log(sortArrayOfString([''])) //=> ['']
console.log(sortArrayOfString(['cba'])) //=> ['abc']
console.log(sortArrayOfString(['bcad', 'bcad'])) //=> [ 'abcd', 'abcd' ]The second part of this prompt is to figure out the time complexity of our final algorithm. Because we were careful to break the problem down into its component pieces, it's easier to figure out the time complexity than if we had just used inbuilt methods.
In the first step of our algorithm, we sort each string in the array. We have to loop through every element in the array (let's call it's length "a"); then at each step we have to sort a string (let's call the length of the longest string "s"). The best sorting algorithms (including the version of quick sort we use here) have a time complexity of s * log(s). And since we have to do that "a" times, that gives us O(a * s * log(s)) for the first step.
For the second step, we have to apply quick sort to the array, giving us another a * log(a), but for each of those steps, we have to compare two strings, which is itself a O(s) operation. So that gives us a total of O(s * a * log(a)) for that step.
Since we do these steps consecutively, we add their time complexities together, getting O(a * s * log(s) + s * a * log(a)), which can also be written as O(s * a * (log(s) + log(a)).
Bravo!!!