Week 6

Question 1

are fundamental algorithms

Answer 1

Searching data and sorting through data

Question 2

involves going through elements in a data structure to find specific data,

Answer 2

Searching

Question 3

involves arranging elements in a particular order.

Answer 3

while sorting

Question 4

is the task of looking for a specific element inside a data structure.

Answer 4

As mentioned, searching

Question 5

works by going through each element of the array one index after another sequentially.

Answer 5

A linear search

Question 6

Sequentially checks each element in a list until the target value is found or the list ends.

Answer 6

Linear Search Code

Question 7

Is a searching algorithm that works on sorted data. Unlike the linear search algorithm, in which every element of the array is checked,

Answer 7

Binary Search

Question 8

can check the middle value to see whether the desired value is greater or smaller than it. If the desired value is smaller, this algorithm can search through the smaller parts, or it can search through the bigger parts if the desired value is bigger

Answer 8

binary searches

Question 9

is one of the most important topics in computer science; it is faster and easier to locate items in a sorted array than in an unsorted sorted array.

Answer 9

Sorting

Question 10

is the simplest sorting algorithm. It simply iterates over the entire array and swaps elements if one is bigger than the other.

Answer 10

Bubble sorting

Question 11

is the worst type of sort because it compares every pair possible, whereas other sorting algorithms take advantage of the presorted parts of the array. Because bubble sort uses nested loops, it has a time complexity of O(n2).

Answer 11

Bubble sort

Question 12

works by scanning the elements for the smallest element and inserting it into the current position of the array. This algorithm is marginally better than bubble sort.

Answer 12

Selection sorting

Question 13

works similarly to selection sort by searching the array sequentially and moving the unsorted items into a sorted sublist on the left side of the array.

Answer 13

Insertion sort

Question 14

works by obtaining a pivot and partitioning the array around it (bigger elements on one side and smaller elements on the other side) until everything is sorted. The ideal pivot is the median of the array since it will partition the array evenly but getting the median of an unsorted array linear time to compute. Hence, a pivot is typically obtained by taking the median value of the first, middle, and last elements in the partition. This sort is a recursive one and uses the divide-and-conquer methodology to break the quadratic complexity barrier and get the time complexity down to O(nlog2(n)). However, with a pivot that partitions everything on one side, the time complexity is worse case: O(n2).

Answer 14

Quicksort

Question 15

is a selection algorithm to find the kth smallest element in an unordered list. Quickselect uses the same approach as a quicksort algorithm. A pivot is chosen, and the array is partitioned. Instead of recursing both sides like quicksort, however, it recurses only the side for the element. This reduces the complexity from O(nlog2(n)) to O(n)

Answer 15

Quickselect

Question 16

works by dividing the array into subarrays until each array has one element. Then, each subarray is concatenated (merged) in a sorted order.

Answer 16

Mergesort

Question 17

can be done in O(k+n) because it does not compare values. It works only for numbers and given a certain range. Instead of sorting by swapping elements, this count works by counting occurrences of each element in the array. Once occurrences of each element are counted, the new array can be created using those occurrences. This sorts the data without having to swap elements

Answer 17

Count sort