Sorting Algorithms

Question 1

Bubble sort

Answer 1

Can take one array of unsorted values. Has one loop with a nested loop inside. it checks elements of the array two by two and swaps them if the first value is bigger than the second. One important thing is that the nested loop is likefor(let j = 0; j < array.length - i; j++) { which as i increases, it will ignore the last element/s in the array.

2,5,1,7,3
2,5,1,3,7
2,1,3,5,7
1,2,3,5,7

Question 2

Merge sort

Answer 2

The main function splits an array into two arrays and keeps splitting until there is only one number is left in the array then it will compare arrays two by two and sort values.

function merge(array) {

if(array.length <= 1) return array;

const middle = Math.floor(array.length / 2);
const left = merge(array.slice(0, middle));
console.log(left)
const right = merge(array.slice(middle));

return merger(left, right)
}

Question 3

Insertion sort

Answer 3

1* Start by picking the second element in the array
2* Now compare the second element with the one before it and swap if necessary.
3* Continue to the next element and if it is in the incorrect order, iterate through the sorted portion (i.e. the left side) to place the element in the correct place.
4.Repeat until the array is sorted.
[ 5, 3, 4, 1, 2 ]
[ 3, 5, 4, 1, 2 ]
[ 3, 4, 5, 1, 2 ]
[ 1, 3, 4, 5, 2 ]
[ 1, 2, 3, 4, 5 ]

function insertionSort(arr) {
for(let i = 1; i < arr.length; i++) {
let currentEl = arr[i]
let j = i - 1;

while(j >= 0 && arr[j] > currentEl) {
  arr[j + 1] = arr[j]
  console.log(j)
  console.log(i)
  j--
}

arr[j + 1] = currentEl;   }

return arr;
}

Question 4

Selection sort

Answer 4

• 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.
  [ 5, 3, 4, 1, 2 ] // iterate through array set 5 as min
  [ 1, 3, 4, 5, 2 ] // find the lowest value and swap with 5
  // 1 is now in its sorted position
  [ 1, 3, 4, 5, 2 ] // repeat starting at 3
  [ 1, 2, 4, 5, 3 ] // find the lowest value and swap with 3
  // 2 is now in its sorted position

function selectionSort(arr) {

for(let i = 0; i < arr.length - 1; i++) {
let minIndex = i;

// Find the index of the minimum element in the unsorted part of the array
for(let j = i + 1; j < arr.length; j++){
  if(arr[j] < arr[minIndex]) {
    minIndex = j
  }
}

// Swap the found minimum element with the first element
if(minIndex !== i) {
  let temp = arr[i];
  arr[i] = arr[minIndex];
  arr[minIndex] = temp;
}   }

return arr;
}

Question 5

Radix sort

Question 6

Pivot algorithm

Answer 6

• It will help to accept three arguments: an array, a start index, and an end index (these can default to 0 and the array length minus 1, respectively)
  
  • Grab the pivot from the start of the array
  • Store the current pivot index in a variable (this will keep track of where the pivot should end up)
  • Loop through the array from the start until the end
  • If the pivot is greater than the current element, increment the pivot index variable and then swap the current element with the element at the pivot index
  • Swap the starting element (i.e. the pivot) with the pivot index
    Return the pivot index