Insertion Sort

Definition

Definition

Horner's method is an efficient algorithm for evaluating polynomials. It reduces the number of multiplications required to evaluate a polynomial by factoring out common factors, resulting in a faster computation process

Explanation

Horner's method works by evaluating a polynomial in a nested fashion, starting from the highest degree term and gradually working towards the lowest degree term. At each step, it factors out the current term and multiplies the result by the variable, accumulating the sum as it progresses through the polynomial

Guidance

• Start with the highest degree term of the polynomial
• Multiply the coefficient of this term by the variable (x), and add the next lower degree term
• Repeat this process until you reach the constant term
• The final sum is the value of the polynomial at the given point

Tips

• keep track of the intermediate result as you iterate through the terms
• utilize a single loop to iterate through the polynomial terms to improve efficiency

Practice

Practice

evaluatePolynomial(coefficients[], x):
  n = length(coefficients)
  result = coefficients[0] // Initialize result with the constant term
  for i from 1 to n - 1:
    result = result * x + coefficients[i] // Multiply result by x and add the next coefficient
  return result

Solution

package main

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j = j - 1
        }
        arr[j+1] = key
    }
}

public class InsertionSort {

  public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
      int key = arr[i];
      int j = i - 1;
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
      }
      arr[j + 1] = key;
    }
  }
}

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

fun insertionSort(arr: IntArray) {
    val n = arr.size
    for (i in 1 until n) {
        val key = arr[i]
        var j = i - 1
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
}

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

fn insertion_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 1..n {
        let mut j = i;
        while j > 0 && arr[j - 1] > arr[j] {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}

function insertionSort(arr: number[]): void {
  const n: number = arr.length;
  for (let i: number = 1; i < n; i++) {
    let key: number = arr[i];
    let j: number = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}