Algorithms (Sort)

What is Sorting?
Sorting is the process of rearranging the items in a collection (e.g. an array) so that the items are in some kind of order.
Examples

• Sorting numbers from smallest to largest
• Sorting names alphabetically
• Sorting movies based on release year
• Sorting movies based on revenue

Why do we need to Learn this

• Sorting is an incredibly common task, so it’s good to know how it works
• There are many different ways to sort things, and different techniques have their own advantages and disadvantages
• Sorting sometimes has quirks, so it’s good to understand how to navigate them

JavaScript has built-in sort methods but they don’t always work as expected

The sort above worked well,

The sort below not so well
Telling Javascript how to sort

• The built-in sort method accepts an optional comparator function
• You can use this comparator function to tell JavaScript how you want it to sort
• The comparator looks at pairs of elements (a and b), determines their sort order based on the return value
• If it returns a negative number, a should come before b
• If it returns a positive number, a should come after b,
• If it returns 0, a and b are the same as far as the sort is concerned

Telling Javascript how to sort(Examples)
 
 
Let us talk about two different simple Sorting algorithms

• Bubble Sort
• Selection Sort

Bubble Sort
A sorting algorithm where the largest values bubble up to the top!. We start from the first element and check is the first element greater than the next element, if yes, switch.  We keep doing this till we get it to its rightful spot in the array, then we start again.
Take the array for example

Pseudocode

• Start looping from with a variable called i the end of the array towards the beginning
• Start an inner loop with a variable called j from the beginning until i – 1
• If arr[j] is greater than arr[j+1], swap those two values!
• Return the sorted array

Actual Code  
  
Selection Sort
Similar to bubble sort, but instead of first placing large values into a sorted position, it places small values into a sorted position.
Take the array below.

Pseudocode

• Store the first element as the smallest value you’ve seen so far.
• Compare this item to the next item in the array until you find a smaller number.
• If a smaller number is found, designate that smaller number to be the new “minimum” and continue until the end of the array.
• If the “minimum” is not the value (index) you initially began with, swap the two values.
• Repeat this with the next element until the array is sorted.

Actual Code

Time Complexities of the two sorting algorithms

Algorithm	Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
Bubble Sort	O(n)	O(n  )	O(n  )	O(1)
Selection Sort	O(n  )	O(n  )	O(n  )	O(1)

 
In the next article, we shall look at another basic sorting algorithm and some intermediate ones. Till next time 🙂
 
 

Written by Ebube Okocha