Lógica de Programação 2020 - Aula 06

example-1.js

function bubbleSort (items) {
  const length = items.length
  for (let i = (length - 1); i >= 0; i--) {
    for (let j = (length - i); j > 0; j--) {
      // Compare the adjacent positions
      if (items[j] < items[j - 1]) {
        // Swap the numbers
        const tmp = items[j]
        items[j] = items[j - 1]
        items[j - 1] = tmp
      }
    }
  }
}

example-2.js

const collection = [3, 2, 6, 10]
collection.sort() // will return sorted array
collection        // won't mutate the variable

example-3.js

function insertionSort (collection) {
  const len = collection.length

  for (let unsortedIndex = 1; unsortedIndex < len; unsortedIndex++) {
    let sortedIndex = unsortedIndex
    const element = collection[unsortedIndex]

    while (sortedIndex > 0 && collection[sortedIndex - 1] > element) {
      collection[sortedIndex] = collection[sortedIndex - 1]
      sortedIndex--
    }

    collection[sortedIndex] = element
  }

  return collection
}

example-4.js

function quicksort (array) {
  if (array.length <= 1) {
    return array
  }

  const pivot = array[0]
  const left = []
  const right = []

  for (let i = 1; i < array.length; i++) {
    array[i] < pivot ? left.push(array[i]) : right.push(array[i])
  }

  return quicksort(left).concat(pivot, quicksort(right))
};

example-5.js

const collection = [5, 12, 8, 130, 44];
const found = collection.find(element => element === 12);

console.log(found) // will print 12

example-6.js

function linearSearch (value, list) {
  let found = false
  let position = -1
  let index = 0

  while (!found && index < list.length) {
    if (list[index] === value) {
      found = true
      position = index
    } else {
      index += 1
    }
  }
  return position
}

example-7.js

function binarySearch (collection, element) {
  let start = 0
  let end = collection.length - 1

  while (start <= end) {
    // Find the middle
    const mid = Math.floor((start + end) / 2)

    // Found the element!
    if (collection[mid] === element) {
      return true
    } else if (collection[mid] < element) {
      start = mid + 1
    } else {
      end = mid - 1
    }
  }

  return false
}