Searching and Sorting Algorithms - Chapter 11

Question 1

Blank is a search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached.

Answer 1

Linear search

Question 2

An algorithm’s blank is the time the algorithm takes to execute. If each comparison takes 1 µs (1 microsecond), a linear search algorithm’s runtime is up to 1 second to search a list with 1million elements, 10 s for 10million elements, and so on. Ex: Searching Amazon’s online store, which has more than 200 million items, could require more than 3 minutes.

Answer 2

runtime

Question 3

An algorithm typically uses a number of steps proportional to the size of the input. For a list with 32 elements, linear search requires at most blank comparisons

Answer 3

32

Question 4

Blank checks the middle contact first. If the desired contact comes alphabetically before the middle contact, binary search will then search the first half and otherwise the last half. Each step reduces the contacts that need to be searched by half.

Answer 4

binary search,

Question 5

Blank is a faster algorithm for searching a list if the list’s elements are sorted and directly accessible. Binary search first checks the middle element of the list. If the search key is found, the algorithm returns the matching location. If the search key is not found, the algorithm repeats the search on the remaining left sublist (if the search key was less than the middle element) or the remaining right sublist (if the search key was greater than the middle element).

Answer 5

Binary search

Question 6

In binary search, for an N element list, the maximum number of steps required to reduce the search space to an empty sublist is blank

Answer 6

floor(log2 N) + 1

Question 7

Python has a special blank operator, //, that automatically drops the quotient’s decimal portion, so this operator is used when calculating the middle index: mid = (high + low) // 2.

Answer 7

floor division

Question 8

A blank is an operation that, for a given processor, always operates in the same amount of time, regardless of input values.

Answer 8

constant time operation

Question 9

In practice, designing an efficient algorithm aims to lower the amount of time that an algorithm runs. However, a single algorithm can always execute more quickly on a faster processor. Therefore, the theoretical analysis of an algorithm describes runtime in terms of number of blank, not nanoseconds.

Answer 9

constant time operations

Question 10

The blank being used, as well as the blank running the code, both affect what is and what is not a constant time operation.

Answer 10

programming language
hardware

Question 11

Common constant time operations

Answer 11

Addition, subtraction, multiplication, and division of fixed size integer or floating point values
Assignment of a reference, pointer, or other fixed size data value.
Comparison of two fixed size data values.
Read or write an array element at a particular index.

Question 12

An algorithm with runtime complexity T(N) has a blank and blank.

Answer 12

lower bound and an upper bound

Question 13

Blank A function f(N) that is ≤ the best case T(N), for all values of N ≥ 1.

Answer 13

Lower bound:

Question 14

Blank: A function f(N) that is ≥ the worst case T(N), for all values of N ≥ 1.

Answer 14

Upper bound

Question 15

Given a function T(N), an blank of lower bounds and upper bounds exist. Ex: If an algorithm’s best case runtime is T(N) = 5N + 4, then subtracting any nonnegative integer yields a lower bound: 5N + 3, 5N + 2, and so on.

Answer 15

infinite number

Question 16

Two additional criteria are commonly used to choose a preferred upper or lower bound. The preferred bound:

Answer 16

is a single-term polynomial and
bounds T(N) as tightly as possible.

Question 17

Blank is the classification of runtime complexity that uses functions that indicate only the growth rate of a bounding function.

Answer 17

Asymptotic notation

Question 18

Three asymptotic notations are commonly used in complexity analysis:

Answer 18

O notation
Ω notation
Θ notation provides a growth rate that is both an upper and lower bound.

Question 19

Blank provides a growth rate for an algorithm’s upper bound.

Answer 19

O notation

Question 20

Blank provides a growth rate for an algorithm’s lower bound.

Answer 20

Ω notation

Question 21

Blank provides a growth rate that is both an upper and lower bound.

Answer 21

Θ notation

Question 22

Blank is a mathematical way of describing how a function (running time, or runtime, of an algorithm) behaves in relation to the input size.

Answer 22

Big O notation

Question 23

In Big O notation, all functions that have the same growth rate (as determined by the highest order term) are characterized using the same Big O notation. In essence, all functions that have the same growth rate are considered blank in Big O notation.

Answer 23

equivalent

Question 24

Given a function that describes the runtime of an algorithm, the Big O notation for that function can be determined using the following rules

Answer 24

If f(x) is a sum of several terms, the highest order term (the one with the fastest growth rate) is kept and others are discarded.
If f(x) has a term that is a product of several factors, all constants (those that are not in terms of x) are omitted.

Question 25

c · O(f(x)) Big O notation

Answer 25

O(f(x))

Question 26

c + O(f(x)) Big O notation

Answer 26

O(f(x))

Question 27

g(x) · O(f(x)) Big O notation

Answer 27

O(g(x)·O(f(x)))

Question 28

g(x) + O(f(x)) Big O notation

Answer 28

O(g(x) + O(f(x)))

Question 29

One consideration in evaluating algorithms is that the efficiency of the algorithm is most critical for blank. Small inputs are likely to result in fast runtimes because N is small, so efficiency is less of a concern.

Answer 29

large input sizes

Question 30

O(1) Name

Answer 30

Constant

Question 31

O-type
def find_min(x, y):
if x < y:
return x
else:
return y

Answer 31

O(1) Constant

Question 32

O(log N) Name

Answer 32

Logarithmic

Question 33

O-type
def binary_search(numbers, key):
low = 0
high = len(numbers) - 1

while high >= low:
mid = (high + low) // 2
if numbers[mid] < key:
low = mid + 1
elif numbers[mid] > key:
high = mid - 1
else:
return mid
return -1 # not found

Answer 33

O(log N or Logarithmic

Question 34

O(N) name

Answer 34

Linear

Question 35

O type -
def linear_search(numbers, key):
for i in range(len(numbers)):
if numbers[i] == key:
return i
return -1 # not found

Answer 35

O(N) or Linear

Question 36

O(N log N) name

Answer 36

Log-linear

Question 37

O type -
def merge_sort(numbers, i, k):
if i < k:
j = (i + k) // 2 # Find midpoint
merge_sort(numbers, i, j) # Sort left part
merge_sort(numbers, j + 1, k) # Sort right part
merge(numbers, i, j, k) # Merge parts

Answer 37

O(N log N) or Log-linear

Question 38

O(N^2) name

Answer 38

Quadratic

Question 39

O type -
def selection_sort(numbers):
for i in range(len(numbers)):
index_smallest = i
for j in range(i + 1, len(numbers)):
if numbers[j] < numbers[index_smallest]:
index_smallest = j

    temp = numbers[i]
    numbers[i] = numbers[index_smallest]
    numbers[index_smallest] = temp

Answer 39

O(N^2) or Quadratic

Question 40

O(c^n) Name

Answer 40

Exponential

Question 41

O type -
def fibonacci(N):
if (1 == N) or (2 == N):
return N
return fibonacci(N-1) + fibonacci(N-2)

Answer 41

O(c^n) or Exponential

Question 42

To analyze how runtime of an algorithm scales as the input size increases, we first determine how many operations the algorithm executes for a specific input size, N. Then, the blank for that function is determined. Algorithm runtime analysis often focuses on the worst-case runtime complexity.

Answer 42

big-O notation

Question 43

The blank of an algorithm is the runtime complexity for an input that results in the longest execution. Other runtime analyses include best-case runtime and average-case runtime. Determining the average-case runtime requires knowledge of the statistical properties of the expected data inputs.

Answer 43

worst-case runtime

Question 44

Since constants are omitted in big-O notation, any constant number of constant time operations is blank.

Answer 44

O(1)

Question 45

Runtime analysis for blank requires summing the runtime of the inner loop over each outer loop iteration.

Answer 45

nested loops

Question 46

Blank is typically measured by the algorithm’s computational complexity.

Answer 46

Algorithm efficiency

Question 47

Blank is the amount of resources used by the algorithm.

Answer 47

Computational complexity

Question 48

The most common resources considered for computational complexity are the blank and blank.

Answer 48

runtime and memory usage

Question 49

An algorithm’s blank is a function, T(N), that represents the number of constant time operations performed by the algorithm on an input of size N.

Answer 49

runtime complexity

Question 50

An algorithm’s blank is the scenario where the algorithm does the minimum possible number of operations.

Answer 50

best case

Question 51

An algorithm’s blank is the scenario where the algorithm does the maximum possible number of operations.

Answer 51

worst case

Question 52

A best case or worst case scenario describes contents of the algorithm’s input data only. The input data size must remain a blank. Otherwise, the overwhelming majority of algorithms would have a best case of N=0, since no input data would be processed. In both theory and practice, saying “the best case is when the algorithm doesn’t process any data” is not useful. Complexity analysis always treats the input data size as a variable.

Answer 52

variable, N

Question 53

An algorithm’s blank is a function, S(N), that represents the number of fixed-size memory units used by the algorithm for an input of size N.

Answer 53

space complexity

Question 54

The space complexity of an algorithm that duplicates a list of numbers is blank where k is a constant representing memory used for things like the loop counter and list pointers.

Answer 54

S(N) = 2N + k,

Question 55

Space complexity includes the blank and blank allocated by the algorithm.

Answer 55

input data and additional memory

Question 56

An algorithm’s blank is the space complexity not including the input data

Answer 56

auxiliary space complexity

Question 57

An algorithm to find the maximum number in a list will have a space complexity of S(N) = N + k, but an auxiliary space complexity of blank, where k is a constant.

Answer 57

S(N) = k

Question 58

A blank is an algorithm that breaks the problem into smaller subproblems and applies the algorithm itself to solve the smaller subproblems.

Answer 58

recursive algorithm

Question 59

Because a problem cannot be endlessly divided into smaller subproblems, a recursive algorithm must have a blank: A case where a recursive algorithm completes without applying itself to a smaller subproblem.

Answer 59

base case

Question 60

A blank is a function that calls itself. Recursive functions are commonly used to implement recursive algorithms.

Answer 60

recursive function

Question 61

Factorial, CumulativeSum, and ReverseList

Answer 61

Sample recursive functions

Question 62

The blank is a numerical sequence where each term is the sum of the previous 2 terms in the sequence, except the first 2 terms, which are 0 and 1.

Answer 62

Fibonacci sequence

Question 63

A recursive function can be used to calculate a blank: A term in the Fibonacci sequence.

Answer 63

Fibonacci number

Question 64

FibonacciNumber(termIndex) {
if (termIndex == 0)
return 0
else if (termIndex == 1)
return 1
else
return FibonacciNumber(termIndex - 1) + FibonacciNumber(termIndex - 2)
}

Answer 64

FibonacciNumber recursive function

Question 65

Blank is an algorithm that searches a sorted list for a key by first comparing the key to the middle element in the list and recursively searching half of the remaining list so long as the key is not found.

Answer 65

Binary search

Question 66

The runtime complexity T(N) of a blank will have function T on both sides of the equation. Ex: Binary search performs constant time operations, then a recursive call that operates on half of the input, making the runtime complexity T(N) = O(1) + T(N / 2)

Answer 66

recursive function

Question 67

blank: A function f(N) that is defined in terms of the same function operating on a value < N.

Answer 67

recurrence relation

Question 68

Using O-notation to express runtime complexity of a recursive function requires blank. For simpler recursive functions such as binary search, runtime complexity can be determined by expressing the number of function calls as a function of N.

Answer 68

solving the recurrence relation

Question 69

The runtime complexity of any recursive function can be split into 2 parts: blank and blank. Ex: For binary search’s T(N) = O(1) + T(N / 2), O(1) represents operations directly done by the function and T(N / 2) represents operation done by a recursive call.

Answer 69

operations done directly by the function and operations done by recursive calls made by the function

Question 70

A useful tool for solving recurrences is a blank: A visual diagram of an operation done by a recursive function, that separates operations done directly by the function and operations done by recursive calls.

Answer 70

recursion tree

Question 71

A blank is a sorting algorithm that has an average runtime complexity of O(NlogN) or better

Answer 71

fast sorting algorithm

Question 72

Average case runtime complexity of Selection sort

Answer 72

O(N^2)

Question 73

Average case runtime complexity of Insertion sort

Answer 73

O(N^2)

Question 74

Average case runtime complexity of Shell sort

Answer 74

O(N^1.5)

Question 75

Average case runtime complexity of Quicksort

Answer 75

O(NlogN)

Question 76

Average case runtime complexity of Merge sort

Answer 76

O(NlogN)

Question 77

Average case runtime complexity of Heap sort

Answer 77

O(NlogN)

Question 78

Average case runtime complexity of Radix sort

Answer 78

O(N)

Question 79

Name the three sorting algorithms that aren’t considered fast sorting algorithms

Answer 79

Selection sort, Insert sort, Shell sort

Question 80

Name the four fast sorting algorithms

Answer 80

Quicksort, Merge sort, Heap sort, Radix sort

Question 81

A blank is a sorting algorithm that operates on an array of elements that can be compared to each other. Ex: An array of strings can be sorted with a comparison sorting algorithm, since two strings can be compared to determine if the one string is less than, equal to, or greater than another string.

Answer 81

element comparison sorting algorithm

Question 82

Blank, blank, blank, blank, blank and blank are all comparison sorting algorithms. Blank, in contrast, subdivides each array element into integer digits and is not a comparison sorting algorithm.

Answer 82

Selection sort, insertion sort, shell sort, quicksort, merge sort, and heap sort
Radix sort

Question 83

A fast sorting algorithm’s best or worst case runtime complexity may differ from the blank.

Answer 83

average runtime complexity

Question 84

Quicksort - Best case runtime complexity, Average case runtime complexity, and Worst case runtime complexity

Answer 84

O(NlogN), O(NlogN), O(N^2)

Question 85

Merge sort - Best case runtime complexity, Average case runtime complexity, and Worst case runtime complexity

Answer 85

O(NlogN), O(NlogN), O(NlogN)

Question 86

Heap sort - Best case runtime complexity, Average case runtime complexity, and Worst case runtime complexity

Answer 86

O(N), O(NlogN), O(NlogN)

Question 87

Radix sort - Best case runtime complexity, Average case runtime complexity, and Worst case runtime complexity

Answer 87

O(N), O(N), O(N)

Question 88

Blank is the process of converting a list of elements into ascending (or descending) order.

Answer 88

Sorting

Question 89

Blank is a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.

Answer 89

Selection sort

Question 90

The index variable i denotes the blank. Elements to the left of i are sorted, and elements including and to the right of i are unsorted. All elements in the unsorted part are searched to find the index of the element with the smallest value.

Answer 90

dividing point

Question 91

Selection sort has the advantage of blank, involving one loop nested within another loop

Answer 91

being easy to code

Question 92

The selection sort algorithm runtime is blank

Answer 92

O(N^2).

Question 93

def blank(numbers):
for i in range(len(numbers)-1):

  # Find index of smallest remaining element
  index_smallest = i
  for j in range(i+1, len(numbers)):
     
     if numbers[j] < numbers[index_smallest]:
        index_smallest = j
  
  # Swap numbers[i] and numbers[index_smallest]
  temp = numbers[i]
  numbers[i] = numbers[index_smallest]
  numbers[index_smallest] = temp

Answer 93

selection_sort

Question 94

Blank is a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part.

Answer 94

Insertion sort

Question 95

The index variable i denotes the starting position of the current element in the unsorted part. Initially, the first element (i.e., element at index 0) is assumed to be sorted, so the outer for loop initializes i to blank. The inner while loop inserts the current element into the sorted part by repeatedly swapping the current element with the elements in the sorted part that are larger. Once a smaller or equal element is found in the sorted part, the current element has been inserted into the correct location and the while loop terminates.

Answer 95

1

Question 96

Insertion sort’s typical runtime is blank

Answer 96

O(N^2)

Question 97

For sorted or nearly sorted inputs, insertion sort’s runtime is blank

Answer 97

O(N)

Question 98

A blank contains only a few elements not in sorted order.

Answer 98

nearly sorted list

Question 99

Create a list of unsorted values

def blank(numbers):
for i in range(1, len(numbers)):
j = i

    # Insert numbers[i] into sorted part 
    # stopping once numbers[i] in correct position
    while j > 0 and numbers[j] < numbers[j - 1]:
        # Swap numbers[j] and numbers[j - 1]
        temp = numbers[j]
        numbers[j] = numbers[j - 1]
        numbers[j - 1] = temp
        j -= 1

numbers = [10, 2, 78, 4, 45, 32, 7, 11]

Print unsorted list
print(‘UNSORTED:’, numbers)

Call the insertion_sort function
insertion_sort(numbers)

Print sorted list
print(‘SORTED:’, numbers)

Answer 99

insertion_sort

Question 100

Blank is a sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm.

Answer 100

Shell sort

Question 101

Shell sort uses blank to determine the number of interleaved lists.

Answer 101

gap values

Question 102

A blank is a positive integer representing the distance between elements in an interleaved list. For each interleaved list, if an element is at index i, the next element is at index i + gap value.

Answer 102

gap value

Question 103

Shell sort begins by choosing a gap value K and sorting K interleaved lists in place. Shell sort finishes by performing a standard insertion sort on the entire array. Because the interleaved parts have already been sorted, smaller elements will be close to the array’s beginning and larger elements towards the end. Blank can then quickly sort the nearly-sorted array.

Answer 103

Insertion sort

Question 104

If a gap value of K is chosen, creating K entirely new lists would be blank. Instead of creating new lists, shell sort sorts interleaved lists in-place with a variation of the insertion sort algorithm. The insertion sort algorithm variant redefines the concept of “next” and “previous” items. For an item at index X, the next item is at X + K, instead of X + 1, and the previous item is at X - K instead of X - 1.

Answer 104

computationally expensive

Question 105

Shell sort begins by picking an arbitrary collection of gap values. For each gap value K, K calls are made to the insertion sort variant function to sort K interleaved lists. Shell sort ends with a final gap value of blank, to finish with the regular insertion sort.

Answer 105

1

Question 106

Shell sort tends to perform well when choosing gap values in blank. A common option is to choose powers of 2 minus 1, in descending order

Answer 106

descending order

Question 107

This gap selection technique results in shell sort’s time complexity being no worse than blank

Answer 107

O(N^3/2)

Question 108

def blank(numbers, start_index, gap):
for i in range(start_index + gap, len(numbers), gap):
j = i
while (j - gap >= start_index) and (numbers[j] < numbers[j - gap]):
temp = numbers[j]
numbers[j] = numbers[j - gap]
numbers[j - gap] = temp
j = j - gap

Answer 108

insertion_sort_interleaved

Question 109

Blank is a sorting algorithm that repeatedly partitions the input into low and high parts (each unsorted), and then recursively sorts each of those parts.

Answer 109

Quicksort

Question 110

To partition the input, quicksort chooses a blank to divide the data into low and high parts.

Answer 110

pivot

Question 111

The pivot can be any value within the array, commonly the value of the blank. Ex: For the list [4, 34, 10, 25, 1], the middle element is located at index 2 (the middle of indices 0..4) and has a value of 10.

Answer 111

middle array element

Question 112

Once partitioned, each partition needs to be sorted. Quicksort is typically implemented as a blank using calls to quicksort the low and high partitions. This recursive sorting process continues until a partition has one or zero elements, and thus is already sorted.

Answer 112

recursive algorithm

Question 113

The quicksort algorithm’s runtime is typically blank.

Answer 113

O(N log N)

Question 114

Quicksort has several blank, the first level dividing the input into 2 parts, the second into 4 parts, the third into 8 parts, etc. At each level, the algorithm does at most N comparisons moving the l and h indices. If the pivot yields two equal-sized parts, then there will be log N levels, requiring the N * log N comparisons

Answer 114

partitioning levels

Question 115

For typical unsorted data, such equal partitioning occurs. However, partitioning may yield unequal-sized parts in some cases. If the pivot selected for partitioning is the smallest or largest element, one partition will have just one element, and the other partition will have all other elements. If this unequal partitioning happens at every level, there will be N - 1 levels, yielding (N-1)(N)
, which is blank

Answer 115

O(N^2)

Question 116

def blank(numbers, start_index, end_index):
# Select the middle value as the pivot.
midpoint = start_index + (end_index - start_index) // 2
pivot = numbers[midpoint]

# "low" and "high" start at the ends of the list segment
# and move towards each other.
low = start_index
high = end_index
   
done = False
while not done:
    # Increment low while numbers[low] < pivot
    while numbers[low] < pivot:
        low = low + 1
  
    # Decrement high while pivot < numbers[high]
    while pivot < numbers[high]:
        high = high - 1
  
    # If low and high have crossed each other, the loop
    # is done. If not, the elements are swapped, low is
    # incremented and high is decremented.
    if low >= high:
        done = True
    else:
        temp = numbers[low]
        numbers[low] = numbers[high]
        numbers[high] = temp
        low = low + 1
        high = high - 1
   
# "high" is the last index in the left segment.
return high

Answer 116

partition

Question 117

def blank(numbers, start_index, end_index):
# Only attempt to sort the list segment if there are
# at least 2 elements
if end_index <= start_index:
return

# Partition the list segment
high = partition(numbers, start_index, end_index)

# Recursively sort the left segment
quicksort(numbers, start_index, high)

# Recursively sort the right segment
quicksort(numbers, high + 1, end_index)

Answer 117

quicksort

Question 118

Blank is a sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list. The recursive partitioning continues until a list of one element is reached, as a list of one element is already sorted.

Answer 118

Merge sort

Question 119

The merge sort algorithm uses blank to keep track of the elements to sort for each recursive call. The index variable i is the index of the first element in the list, and the index variable k is the index of the last element. The index variable j is used to divide the list into two halves. Elements from i to j are in the left half, and elements from j + 1 to k are in the right half.

Answer 119

three index variables

Question 120

Merge sort merges the two sorted partitions into a single list by repeatedly selecting the blank from either the left or right partition and adding that element to a temporary merged list. Once fully merged, the elements in the temporary merged list are copied back to the original list.

Answer 120

smallest element

Question 121

The merge sort algorithm’s runtime is blank.

Answer 121

O(N log N)

Question 122

Merge sort requires blank additional memory elements for the temporary array of merged elements. For the final merge operation, the temporary list has the same number of elements as the input. Some sorting algorithms sort the list elements in place and require no additional memory but are more complex to write and understand.

Answer 122

O(N)

Question 123

def blank(numbers, i, j, k):
merged_size = k - i + 1 # Size of merged partition
merged_numbers = [0] * merged_size # Dynamically allocates temporary array
# for merged numbers
merge_pos = 0 # Position to insert merged number
left_pos = i # Initialize left partition position
right_pos = j + 1 # Initialize right partition position

# Add smallest element from left or right partition to merged numbers
while left_pos <= j and right_pos <= k:
    if numbers[left_pos] <= numbers[right_pos]:
        merged_numbers[merge_pos] = numbers[left_pos]
        left_pos += 1
    else:
        merged_numbers[merge_pos] = numbers[right_pos]
        right_pos += 1
    merge_pos = merge_pos + 1
   
# If left partition is not empty, add remaining elements to merged numbers
while left_pos <= j:
    merged_numbers[merge_pos] = numbers[left_pos]
    left_pos += 1
    merge_pos += 1
   
# If right partition is not empty, add remaining elements to merged numbers
while right_pos <= k:
    merged_numbers[merge_pos] = numbers[right_pos]
    right_pos = right_pos + 1
    merge_pos = merge_pos + 1
   
# Copy merge number back to numbers
for merge_pos in range(merged_size):
    numbers[i + merge_pos] = merged_numbers[merge_pos]

def merge_sort(numbers, i, k):
j = 0

if i < k:
    j = (i + k) // 2  # Find the midpoint in the partition

    # Recursively sort left and right partitions
    merge_sort(numbers, i, j)
    merge_sort(numbers, j + 1, k)
        
    # Merge left and right partition in sorted order
    merge(numbers, i, j, k)

Create a list of unsorted values
numbers = [61, 76, 19, 4, 94, 32, 27, 83, 58]

Print unsorted list
print(‘UNSORTED:’, numbers)

Initial call to merge_sort
merge_sort(numbers, 0, len(numbers) - 1)

Print sorted list
print(‘SORTED:’, numbers)

Answer 123

merge

Question 124

Blank is a sorting algorithm designed specifically for integers. The algorithm makes use of a concept called buckets and is a type of bucket sort.

Answer 124

Radix sort

Question 125

Any array of integer values can be subdivided into buckets by using the integer values’ digits. A blank is a collection of integer values that all share a particular digit value. Ex: Values 57, 97, 77, and 17 all have a 7 as the 1’s digit, and would all be placed into bucket 7 when subdividing by the 1’s digit.

Answer 125

bucket

Question 126

Blank is a sorting algorithm specifically for an array of integers: The algorithm processes one digit at a time starting with the least significant digit and ending with the most significant. Two steps are needed for each digit. First, all array elements are placed into buckets based on the current digit’s value. Then, the array is rebuilt by removing all elements from buckets, in order from lowest bucket to highest.

Answer 126

Radix sort

Question 127

In the extension, before radix sort completes, the algorithm allocates two buckets, blank and blank. The algorithm iterates through the array in order, placing negative integers in the negative bucket and non-negative integers in the non-negative bucket. The algorithm then reverses the order of the negative bucket and concatenates the buckets to yield a sorted array.

Answer 127

one for negative integers and the other for non-negative integers

Question 128

Returns the maximum length, in number of digits, out of all list elements
def blank_get_max_length(numbers):
max_digits = 0
for num in numbers:
digit_count = radix_get_length(num)
if digit_count > max_digits:
max_digits = digit_count
return max_digits

Returns the length, in number of digits, of value
def radix_get_length(value):
if value == 0:
return 1

digits = 0
while value != 0:
    digits += 1
    value = int(value / 10)
return digits

def radix_sort(numbers):
buckets = []
for i in range(10):
buckets.append([])

# Find the max length, in number of digits
max_digits = radix_get_max_length(numbers)

pow_10 = 1
for digit_index in range(max_digits):
    for num in numbers:
        bucket_index = (abs(num) // pow_10) % 10
        buckets[bucket_index].append(num)

    numbers.clear()
    for bucket in buckets:
        numbers.extend(bucket)
        bucket.clear()
  
    pow_10 = pow_10 * 10

negatives = []
non_negatives = []
for num in numbers:
    if num < 0:
        negatives.append(num)
    else:
        non_negatives.append(num)
negatives.reverse()
numbers.clear()
numbers.extend(negatives + non_negatives)

Create a list of unsorted values
numbers = [47, 81, 13, 5, 38, 96, 51, 64]

Print unsorted list
print(‘UNSORTED:’, numbers)

Call radix_sort to sort the list
radix_sort(numbers)

Print sorted list
print(‘SORTED:’, numbers)

Answer 128

radix

Question 129

Python has a built-in blank function that takes one list argument, sorts the list’s elements in ascending order using the less than (<) operator, and returns a new list with the sorted elements.

Answer 129

sorted()

Question 130

Python lists also have a blank method to do an in-place sorting of list elements in ascending order, meaning the list is modified and another list is not returned.

Answer 130

sort()

Question 131

sorted() and sort() can both take an optional keyword argument, blank, that when assigned with True sorts a list in descending order.

Answer 131

reverse

Question 132

The sorted() function and sort() method can take an optional blank, which is a function that determines how to sort the list. One common use of the key argument is to sort a list of strings without regard to case. Ex: The list [ “banana”, “Grape”, “Apple” ] by default sorts with uppercase letters coming before lowercase letters: [ “Apple”, “Grape”, “banana” ]. To sort as if all letters are lowercase, sorted() is called with argument key = str.lower. Note: The changed list item (“apple” instead of “Apple”) is only used temporarily during the sorting algorithm; the resulting list still has the original elements.

The argument is key = str.lower, not key = str.lower(), with parentheses. The key variable is assigned with the actual str.lower function itself, not by calling the str.lower() function.

Answer 132

key argument

Question 133

Another common use for the key argument is to sort a list by one of the blank if each element forms a tuple. Ex: List elements that contain both a student name and ID number: [(“Robert”, 135216), (“Amir”, 612901), (“Jennifer”, 194821)]. A key argument can be used to sort such a list by name or by ID number.

Custom key functions must be defined to have only one parameter, a single list element. The function uses that element variable to return whatever the sorting key should be. Note again that the key parameter is assigned with the custom key function’s name only, parentheses are not used.

Answer 133

elements’ values

Question 134

A special function, blank, defined in Python’s operator module, can be used to get a key from an element using an index instead of a custom key function. Ex: key = key_is_name can be replaced with key = operator.itemgetter(0), because the element names are found at index 0. itemgetter() takes an integer value argument and returns a function defined like key_is_name(element). Ex. operator.itemgetter(5) returns a function that takes a list element argument, and the function returns element[5].

Answer 134

itemgetter()

Question 135

Blank is a sorting algorithm that iterates through a list, comparing and swapping adjacent elements if the second element is less than the first element.

Answer 135

Bubble sort

Question 136

Bubble sort uses blank

Answer 136

nested loops

Question 137

Because of the nested loops, bubble sort has a runtime of blank

Answer 137

O(N^2)

Question 138

Blank is an algorithm that selects the kth smallest element in a list. Ex: Running quickselect on the list (15, 73, 5, 88, 9) with k = 0, returns the smallest element in the list, or 5.

Answer 138

Quickselect

Question 139

The best case and average runtime complexity of quickselect are both blank. In the worst case, quickselect may sort the entire list, resulting in a runtime of blank

Answer 139

O(N)
O(N^2)

Question 140

The quickselect() function has some similarities to the blank function: both functions are recursive, and both functions use the partition() function to rearrange a portion of the input list into sections that are less than or greater than a selected pivot. Unlike quicksort(), however, quickselect() is recursively applied to only one of the partitions.

Answer 140

quicksort()

Question 141

def blank(numbers, start_index, end_index, k):
if start_index >= end_index:
return numbers[start_index]

low_last_index = partition(numbers, start_index, end_index)
if k <= low_last_index:
    return quickselect(numbers, start_index, low_last_index, k)
  
return quickselect(numbers, low_last_index + 1, end_index, k)

Answer 141

quickselect

Question 142

Blank is a numerical sorting algorithm that distributes numbers into buckets, sorts each bucket with an additional sorting algorithm, and then concatenates buckets together to build the sorted result.

Answer 142

Bucket sort

Question 143

A blank is a container for numerical values in a specific range. Ex: All numbers in the range 0 to 49 may be stored in a bucket representing this range. Bucket sort is designed for arrays with non-negative numbers.

Answer 143

bucket

Question 144

Bucket sort first creates a list of buckets, each representing a range of blank. Collectively, the buckets represent the range from 0 to the maximum value in the array

Answer 144

numerical values

Question 145

The bucket index is calculated as
blank

Answer 145

floor(number*N/(M+1))