Searching and Sorting Algorithms - Chapter 11 Flashcards
1
Q
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.
A
Linear search
2
Q
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.
A
runtime
3
Q
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
A
32
4
Q
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.
A
binary search,
5
Q
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).
A
Binary search
6
Q
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
A
floor(log2 N) + 1
7
Q
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.
A
floor division
8
Q
A blank is an operation that, for a given processor, always operates in the same amount of time, regardless of input values.
A
constant time operation
9
Q
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.
A
constant time operations
10
Q
The blank being used, as well as the blank running the code, both affect what is and what is not a constant time operation.
A
programming language
hardware
11
Q
Common constant time operations
A
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.
12
Q
An algorithm with runtime complexity T(N) has a blank and blank.
A
lower bound and an upper bound
13
Q
Blank A function f(N) that is ≤ the best case T(N), for all values of N ≥ 1.
A
Lower bound:
14
Q
Blank: A function f(N) that is ≥ the worst case T(N), for all values of N ≥ 1.
A
Upper bound
15
Q
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.
A
infinite number
16
Q
Two additional criteria are commonly used to choose a preferred upper or lower bound. The preferred bound:
A
is a single-term polynomial and
bounds T(N) as tightly as possible.
17
Q
Blank is the classification of runtime complexity that uses functions that indicate only the growth rate of a bounding function.
A
Asymptotic notation
18
Q
Three asymptotic notations are commonly used in complexity analysis:
A
O notation
Ω notation
Θ notation provides a growth rate that is both an upper and lower bound.
19
Q
Blank provides a growth rate for an algorithm’s upper bound.
A
O notation
20
Q
Blank provides a growth rate for an algorithm’s lower bound.
A
Ω notation
21
Q
Blank provides a growth rate that is both an upper and lower bound.
A
Θ notation
22
Q
Blank is a mathematical way of describing how a function (running time, or runtime, of an algorithm) behaves in relation to the input size.
A
Big O notation
23
Q
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.
A
equivalent
24
Q
Given a function that describes the runtime of an algorithm, the Big O notation for that function can be determined using the following rules
A
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.
25
c · O(f(x)) Big O notation
O(f(x))
26
c + O(f(x)) Big O notation
O(f(x))
27
g(x) · O(f(x)) Big O notation
O(g(x)·O(f(x)))
28
g(x) + O(f(x)) Big O notation
O(g(x) + O(f(x)))
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.
large input sizes
30
O(1) Name
Constant
31
O-type
def find_min(x, y):
if x < y:
return x
else:
return y
O(1) Constant
32
O(log N) Name
Logarithmic
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
O(log N or Logarithmic
34
O(N) name
Linear
35
O type -
def linear_search(numbers, key):
for i in range(len(numbers)):
if numbers[i] == key:
return i
return -1 # not found
O(N) or Linear
36
O(N log N) name
Log-linear
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
O(N log N) or Log-linear
38
O(N^2) name
Quadratic
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
O(N^2) or Quadratic
40
O(c^n) Name
Exponential
41
O type -
def fibonacci(N):
if (1 == N) or (2 == N):
return N
return fibonacci(N-1) + fibonacci(N-2)
O(c^n) or Exponential
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.
big-O notation
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.
worst-case runtime
44
Since constants are omitted in big-O notation, any constant number of constant time operations is blank.
O(1)
45
Runtime analysis for blank requires summing the runtime of the inner loop over each outer loop iteration.
nested loops
46
Blank is typically measured by the algorithm's computational complexity.
Algorithm efficiency
47
Blank is the amount of resources used by the algorithm.
Computational complexity
48
The most common resources considered for computational complexity are the blank and blank.
runtime and memory usage
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.
runtime complexity
50
An algorithm's blank is the scenario where the algorithm does the minimum possible number of operations.
best case
51
An algorithm's blank is the scenario where the algorithm does the maximum possible number of operations.
worst case
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.
variable, N
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.
space complexity
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.
S(N) = 2N + k,
55
Space complexity includes the blank and blank allocated by the algorithm.
input data and additional memory
56
An algorithm's blank is the space complexity not including the input data
auxiliary space complexity
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.
S(N) = k
58
A blank is an algorithm that breaks the problem into smaller subproblems and applies the algorithm itself to solve the smaller subproblems.
recursive algorithm
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.
base case
60
A blank is a function that calls itself. Recursive functions are commonly used to implement recursive algorithms.
recursive function
61
Factorial, CumulativeSum, and ReverseList
Sample recursive functions
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.
Fibonacci sequence
63
A recursive function can be used to calculate a blank: A term in the Fibonacci sequence.
Fibonacci number
64
FibonacciNumber(termIndex) {
if (termIndex == 0)
return 0
else if (termIndex == 1)
return 1
else
return FibonacciNumber(termIndex - 1) + FibonacciNumber(termIndex - 2)
}
FibonacciNumber recursive function
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.
Binary search
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)
recursive function
67
blank: A function f(N) that is defined in terms of the same function operating on a value < N.
recurrence relation
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.
solving the recurrence relation
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.
operations done directly by the function and operations done by recursive calls made by the function
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.
recursion tree
71
A blank is a sorting algorithm that has an average runtime complexity of O(NlogN) or better
fast sorting algorithm
72
Average case runtime complexity of Selection sort
O(N^2)
73
Average case runtime complexity of Insertion sort
O(N^2)
74
Average case runtime complexity of Shell sort
O(N^1.5)
75
Average case runtime complexity of Quicksort
O(NlogN)
76
Average case runtime complexity of Merge sort
O(NlogN)
77
Average case runtime complexity of Heap sort
O(NlogN)
78
Average case runtime complexity of Radix sort
O(N)
79
Name the three sorting algorithms that aren't considered fast sorting algorithms
Selection sort, Insert sort, Shell sort
80
Name the four fast sorting algorithms
Quicksort, Merge sort, Heap sort, Radix sort
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.
element comparison sorting algorithm
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.
Selection sort, insertion sort, shell sort, quicksort, merge sort, and heap sort
Radix sort
83
A fast sorting algorithm's best or worst case runtime complexity may differ from the blank.
average runtime complexity
84
Quicksort - Best case runtime complexity, Average case runtime complexity, and Worst case runtime complexity
O(NlogN), O(NlogN), O(N^2)
85
Merge sort - Best case runtime complexity, Average case runtime complexity, and Worst case runtime complexity
O(NlogN), O(NlogN), O(NlogN)
86
Heap sort - Best case runtime complexity, Average case runtime complexity, and Worst case runtime complexity
O(N), O(NlogN), O(NlogN)
87
Radix sort - Best case runtime complexity, Average case runtime complexity, and Worst case runtime complexity
O(N), O(N), O(N)
88
Blank is the process of converting a list of elements into ascending (or descending) order.
Sorting
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.
Selection sort
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.
dividing point
91
Selection sort has the advantage of blank, involving one loop nested within another loop
being easy to code
92
The selection sort algorithm runtime is blank
O(N^2).
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
selection_sort
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.
Insertion sort
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.
1
96
Insertion sort's typical runtime is blank
O(N^2)
97
For sorted or nearly sorted inputs, insertion sort's runtime is blank
O(N)
98
A blank contains only a few elements not in sorted order.
nearly sorted list
99
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
# Create a list of unsorted values
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)
insertion_sort
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.
Shell sort
101
Shell sort uses blank to determine the number of interleaved lists.
gap values
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.
gap value
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.
Insertion sort
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.
computationally expensive
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.
1
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
descending order
107
This gap selection technique results in shell sort's time complexity being no worse than blank
O(N^3/2)
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
insertion_sort_interleaved
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.
Quicksort
110
To partition the input, quicksort chooses a blank to divide the data into low and high parts.
pivot
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.
middle array element
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.
recursive algorithm
113
The quicksort algorithm's runtime is typically blank.
O(N log N)
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
partitioning levels
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
O(N^2)
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
partition
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)
quicksort
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.
Merge sort
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.
three index variables
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.
smallest element
121
The merge sort algorithm's runtime is blank.
O(N log N)
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.
O(N)
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)
merge
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.
Radix sort
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.
bucket
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.
Radix sort
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.
one for negative integers and the other for non-negative integers
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)
radix
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.
sorted()
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.
sort()
131
sorted() and sort() can both take an optional keyword argument, blank, that when assigned with True sorts a list in descending order.
reverse
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.
key argument
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.
elements' values
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].
itemgetter()
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.
Bubble sort
136
Bubble sort uses blank
nested loops
137
Because of the nested loops, bubble sort has a runtime of blank
O(N^2)
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.
Quickselect
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
O(N)
O(N^2)
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.
quicksort()
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)
quickselect
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.
Bucket sort
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.
bucket
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
numerical values
145
The bucket index is calculated as
blank
floor(number*N/(M+1))
