Algorithms

Question 1

Insertion Sort Code

Answer 1

import java.io.;
import java.util.;

public class Solution {

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

    printArray(A);
}

}

Question 2

import java.io.;
import java.util.;

public class Solution {

public static void \_\_\_\_\_\_\_\_\_\_(int[] A){
    for(int i = 1; i < A.length; i++){
        int value = A[i];
        int j = i - 1;
        while(j >= 0 &amp;&amp; A[j] > value){
            A[j + 1] = A[j];
            j = j - 1;
        }
        A[j+1] = value;
    }

    printArray(A);
}

}

Answer 2

Insertion Sort

Question 3

Insertion Sort Pseudocode

Answer 3

Consider 1st item sorted
Compare next item with previous
Swap if necessary keeping subarray sorted
Continue up array until all are sorted

Question 4

Quicksort Code

Answer 4

import java.io.;
import java.util.;

public class Solution {

 public static int[] quickSort(int[] ar, int lo, int hi){
    if(lo

Question 5

Quicksort Steps

Answer 5

Take first element of the array as the partition
Break up the list into left, equal, and right elements
If left or right is greater than 1 element, continue to partition
Merge the left, equal, and right arrays
Continue until array is sorted

Question 6

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

Answer 6

Quicksort

Question 7

Binary Search Steps

Answer 7

1. Choose lo = 0, hi = n-1
2. Find mid point (lo+hi)/2 and check if mid value is equal to target
3. If mid value is less than, set lo = mid + 1 and repeat step 4. if mid value is greater than, set hi = mid - 1 and repeat.
4. Return target index = mid

Question 8

Binary Search Code

Answer 8

public class Solution {
public static int binarySearch(int[] arr, int target){
int lo = 0, hi = arr.length -1, mid = 0;
while(lo < hi){
mid = (lo + hi)/2;
if(arr[mid]