Sorting algorithms

[tabby title=”Task”]

Sort an array of integers in descending order.

Example:

Given an array of 4 elements

 [3,15,1,5]

Produce an array that will look like this:

 [1,3,5,15]

 

[tabby title=”Solution”]

Brute force using the “selection sort” algorithm.

  1. Starting with the first number 3 we assume that this is our smallest number since we don’t know the others.
  2. Then we iterate through the whole array comparing 3 with other numbers.
  3. If we find number that is smaller than 3 (in our case 1) this will become our smallest number, and we continue comparing it to the end of the array.
  4. when we reach the end of the array we swap the first number, that we assumed that is the smallest one with the newly discovered smallest number (in our case number 1 at third position), and the array will look like this now: [1,15,3,5]
  5. Now as we know for sure that the number at the first position (number 1) is the smallest one, we can start from position 2 and repeat steps 2 to 5 till we checked all numbers in the array.

 

function sortArray(list) {
    var smallestIndex;    
    for(var i = 0; i < list.length; i ++) {
        smallestIndex = i;
        for(var ii = i + 1; ii < list.length;ii ++) {
            smallestIndex = list[ii] < list[smallestIndex] ? ii : smallestIndex;
        }
        var larger = list[i];
        list[i] = list[smallestIndex];
        list[smallestIndex] = larger;

    }
    return list;
}

var listArray = [3,15,1,5];
var result = sortArray(listArray);

console.log(result);

 

Better approach:

Merge sort algorithm.

Let’s consider this example with adding more numbers: [3,15,1,5,4,9]

3,15
1,5
--------
9,4


1,3,5,15	| 1
4,9			

3,5,15		| 1,3
4,9			

5,15		
4,9		| 1,3,4

5,15
9		| 1,3,4,5

15
9		| 1,3,4,5,9

15		| 1,3,4,5,9,15

coming soon…

[tabbyending]

Leave a Reply