Algorithms in JavaScript
Create a Selection Sort Function in JavaScript
While not the fastest sorting algorithm, the selection sort function sorts an array by first creating a new array, calling a function that loops over a list and returns the location of the max/min element, and then pushes that returned indexed value into the newly created array. After the value is added it is then removed from the original list and the process continues until there is nothing left.
Instructor: [00:00] Let's define an array of items we need to sort. Inside of it, we'll give it a three, two, four, one, and six. Now, we before we create and our selection and sort function, we need to first write a function that loops through this array, and gives us the index and the largest number.
[00:16] Then once we have that, we can use our selection sort function to create a new list, call this function, and then remove it from the original list. For that first function, we'll do function findLargestValue, which will take a list.
[00:31] Then we'll do let large E equals list of zero. Let index of large equal zero. We'll do a for loop, where we start with one, and while our I is less than our list.length, we're going to increment our I. If large E is less than list at I, then we're going to update our large value with that list at I, and update our index of large as well.
[00:59] Then finally, we'll return this function, returning the index of large. To recap, this findLargestValue function takes an array of items, loops through that list, and then returns the index location of the largest value within this list.
[01:14] We start out defining the index and the item with the first item, and then if anything appears largest inside of our loop, we update it. Now, with that ready to go, we can create our selection sort function. We'll do that function, selectionSort. It takes a list.
[01:29] Inside of that, we'll create a new array called newList. We'll define our new large item. Then we'll create a while loop where as long as our list has values inside of it, we're going to update that large item, equal to calling our findLargestValue function, passing in this list.
[01:48] That's going to return, and we're going to push onto our new list the return value from our findLargestValue function. Once we've found the largest value from our list, we want to remove it, so we don't count it again as we push values into this new list that we've created.
[02:09] After we remove this, we're going to return our function, which is returning the new list that we've created. With that in place, we can call this function, inside of a console.log. We'll pass in our items to sort, which we created earlier.
[02:24] We'll see that our array is now sorted, six, four, three, two, one, which is correct. Now, let's go back and review this function one more time. The first thing we do is create a new array. This is the array that we're going to return with this function that we see printed here in the console.log.
[02:41] The second thing we do is use this while loop, where we call our findLargestValue function, passing in the current list that we have been provided. Once this findLargestValue function returns, it gives us the index location of the current largest item.
[02:56] Which we push onto this new array, and then we also remove it right after that. Because we need to call our findLargestValue function for N number of times -- or in other words, we have to call our function a total of however long our list is -- this gives our selectionSort function a beginning big O notation of O(n).
[03:19] Then if we remember our findLargestValue function also has a loop inside of it, stepping through another N times with its provided list, this makes our big O notation O(n*n), or n². selectionSort gets the job done, but it's not very fast. Quick sort and merge sort are more efficient, and have a notation of O(n)log(n).
Shouldn't the second statement of the for loop inside the 'findLargestValue' function be 'i < list.length' instead of 'i <= list.length'? Even though it doesn't change the functionality, it seems to me like a bug.
I thought returning 2 values from findLargestValue might make it a bit easier to read:
while (list.length) {
let {largest, iOfLargest} = findLargestValue(list)
sorted.push(largest)
list.splice(iOfLargest, 1)
}
renaming findLargestValue to findIndexOfLargestValue would be much clearer because that's what it does. It does not find the largest value in an array: just it's index.
would the splice also has some impact in this complexity ? as it take 0(n) time to delete the item, n * 2n = 2n^2 in the end still N^2 because we can drop 2, right ?
Thanks