Algorithms

Question 1

What is insertion sort?

Answer 1

The natural question is, how can we place into our array while still keeping it sorted?

This operation is known as an insertion

Question 2

What are the steps for insertion sort?

Answer 2

Place x at the end of the array.
Compare to the element on its left. There are three possibilities:

If there is no element to the left, then we are done, since x will be the smallest element and it is already at the start of the array.

If x is greater than or equal to it, then we are done; x is on the right of all smaller elements and on the left of all larger elements, so the array is once again sorted.

If x is smaller, then it should be before the other element. Switch the two to put x on front.

Repeat step two until finished.

Question 3

What are the steps to the FULL insertion sort algorithm?

Answer 3

Designate the leftmost element of the array as the only element of the sorted side. This side is guaranteed to be sorted by default, since it now contains only one element.

Insert the first element of the unsorted side into the sorted side, increasing the number of sorted elements by one.

Repeat step two until there are no unsorted elements left.

Question 4

What must be tracked during a full insertion sort?

Answer 4

All we have to do is keep track of how much of the original array is sorted.

Question 5

What is the formula for the number of comparisons in the worst case for an array?

Answer 5

n( n - 1 ) / 2

Question 6

What is the formula for the number of comparisons in the best case for an array?

Answer 6

n - 1

Question 7

What is the goal of the divide and conquer method?

Answer 7

The goal of this method is to

divide a problem into equal sized sub-problems recursively;

conquer each problem separately, solving them recursively;

combine results.

Question 8

What are the three steps of a merge sort algorithm?

Answer 8

1) Divide: Split the list into two (approximately) equally sized lists.
2) Conquer: Sort each of the two lists separately (using mergesort itself!).
3) Combine: Given two sorted lists of approximately the same size, merge them into one big sorted list.

Question 9

What is the code for mergesort?

Answer 9

def merge(left, right):
result = []
left_idx, right_idx = 0, 0
while left_idx < len(left) and right_idx < len(right):
# change the direction of this comparison to change the direction of the sort
if left[left_idx] <= right[right_idx]:
result.append(left[left_idx])
left_idx += 1
else:
result.append(right[right_idx])
right_idx += 1

    if left:
        result.extend(left[left_idx:])
    if right:
        result.extend(right[right_idx:])
    return result

def merge_sort(m):
    if len(m) <= 1:
        return m

middle = len(m) // 2
left = m[:middle]
right = m[middle:]

    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

Question 10

What is the advantage of mergesort?

Answer 10

The mergesort algorithm takes advantage of the fact that two sorted lists can be merged into one sorted list very quickly.

Question 11

What is the best runtime on average?

Answer 11

It turns out that the runtime of O(NlogN) is the best we can do, on average, for a comparison-based sorting algorithm.

Question 12

What is Quicksort?

Answer 12

Quicksort, just like mergesort, is a “divide-and-conquer” sorting algorithm that runs in O(NlogN) time in the average case.

Question 13

What is the worst case for Quicksort?

Answer 13

Although it has a worst case runtime of O(n**2), overall quicksort tends to outperform mergesort in the real world, making it an attractive choice for many programmers.

Question 14

What is partitioning in Quicksort?

Answer 14

Pick a pivot element (typically the last item in the array). All numbers lower than this value go to the left and all elements higher to the right. For quicksort, this step is commonly known as partitioning.

Question 15

What is the key to Quicksort?

Answer 15

The key to a successful sort is picking the right pivot point.

Question 16

What is the “median of three” method in Quicksort?

Answer 16

“Median of three” method–pick out the first, middle, and last elements and choose the median of the three.

pivot = sorted([arr[0],arr[arr_length // 2],arr[-1]])[1]

Question 17

What is the code for Quicksort?

Answer 17

def quickSort(arr):
    less = []
    pivotList = []
    more = []
    arr_length = len(arr)
    if arr_length <= 1:
        return arr
    else:
        pivot = arr[0] # Change this line
        for i in arr:
            if i < pivot:
                less.append(i)
            elif i > pivot:
                more.append(i)
            else:
                pivotList.append(i)
        less = quickSort(less)
        more = quickSort(more)
        return less + pivotList + more