Sorting and Search

Содержание и основные понятия

Sorting puts the data in order where the adjacent elements are comparable, and a consistent choice can be made from left to right after checking its correct condition.
substance and practice
Grade 9
EEG No. 17
EEG No. 26
01
How it works.
Sorting brings the data to order. After that, it's easier to choose objects, compare neighbors, and apply a binary search; but you need to know if the source list changes.
sorted.
Creates a new sorted list and leaves the source unchanged.
sort.
Changes the list on the spot and returns None.
key.
Computes the comparison key; the keyboard gives priority to the criteria.
Stability.
The same keys keep the original relative order in Python.
02
One example in execution
Start the short program and go over the lines. The visualiser only shows the code, current line, variables and output.
A binary search only applies to a sorted sequence. At each step, it compares the goal with the middle element and drops out half the range. When sorting lines, the comparison is lexicical: '12' is earlier than '3', so the numerical lines are converted first to in. For the EEG No. 26, the selection condition and rule in equality are important, not just the challenge sort itself.
Algorithm map
Read from left to right, then run the code.
1
Start
2
Create Values
3
Build sort(s)
4
Do not change the reference list
5
Delete both lists
03
Remember
Result = values.sort() will give None, not the list.
Before you search the binary, prove that the data has been sorted.
Clearly ask tie-break what to do with equal price, score, or name.
Syntax of this page
sorted(values, key=None, reverse=False)
Returns a new sorted list.
values.sort(key=None, reverse=False)
Changes the values in place and returns the None.
lambda item: ...
Short function to calculate the sorting key.
key=lambda x: (x[1], x[0])
The motorcade sets the first and second criteria for comparison.
list.reverse()
Changes the list on the spot; does not return the new list.
bisect_left(a, x)
From the bisect module: box position x to sorted a to the left.
range / len
Used in manual implementation of the binary search.
print
Shows order to check.