Sorting and Searching in Python

Imagine that you have a piece of paper in your hand with 1,000 names listed and you need to find one of them, but this list is not in alphabetical order. It would be very frustrating, isn't it? While it takes a long time to sort out this list, it makes finding names much easier. So sorting things is our human natural desire, and searching for sorted lists is obviously more labor-saving than searching for unordered lists.

In the computer world, the list of searches can be very large, and even fast computers, performance may be affected. In this case, a suitable sorting and search algorithm would be the solution to such problems. Sort is the process of sorting a list of values ​​in order, while search is the process of finding the position of values ​​in the list.

To illustrate the importance of this issue, let me show you what the great American computer scientist Donald Knuth said:

Computer manufacturers in the 1960s estimated that, given all customers, more than 25% of their computer runtime was spent on sorting. In fact, in many installation cases, the sorting task takes up more than half of the calculation time. From these statistics, we can conclude that (i) sorting has many important applications, or (ii) many people sort when they shouldn't, or (iii) inefficient sorting algorithms have been widely used. ——"The Art of Computer Programming" Volume 3: Sort and Search, Page 3

In this tutorial, I will show you how to implement the selection sorting algorithm and the linear search algorithm.

But before we get started, if you just want to sort and search in your Python code, I'll show you the built-in method.

Built-in sorting methods and functions in Python

You can create many sorting algorithms using Python. This is a good learning exercise, but for production applications you should stick with built-in stored functions and methods in Python.

Python has a list.sort() method that you can use to sort the list in-place. The sorting algorithm used behind the scenes of Python is called Timsort. It is a hybrid sorting algorithm based on insert sorting and merge sorting that provides excellent performance in many real-life lives. Here is an example of how to use these two functions and methods:

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

You may notice some of the situations in the above code. The sorted() function returns a new sorted list without changing the original list marks_a. However, the original list remains the same. On the other hand, when we call the marks_b method on sort(), it returns None.

You can pass some parameters to modify the sorting behavior. For example, pass a function to the reverse parameter, which sorts our list of words alphabetically without any parameters. In the second case, we use sorted() to reverse the order of sorted words. reverse=True

Select sorting algorithm

Select sortThe algorithm is based on continuous selection of the minimum or maximum value. Suppose we have a list that we want to sort in ascending order (small to large). The smallest element will be at the beginning of the list and the largest element will be at the end of the list.

Suppose the original list looks like this:

| 7 | 5 | 3.5 | 4 | 3.1 |

The first thing we have to do is find the

minimum value in the list, in this case . 3.1

When the minimum value is found, exchange the minimum value with the first element in the list

. That is, exchange with . The list will now look like this: 3.1 7

| 3.1 | 5 | 3.5 | 4 | 7 | Now that we determine the correct position of the first element in the list, we repeat the above steps (find the minimum value) from the second

element of the list. We can find that the minimum value in the list (starting from the second element) is

. So we will now exchange with . The list now becomes: 3.5 3.55

At this point, we make sure that the first element and the second element are in their correct position. | 3.1 | 3.5 | 5 | 4 | 7 |

Now, we check the minimum value in the rest of the list, i.e. starting with the third element

. The minimum value in the rest of the list is

, which we now swap with

. Therefore, the list becomes: 5 45

Therefore, we now determine that the first three | 3.1 | 3.5 | 4 | 5 | 7 | elements are in the correct position and the process continues in this way.

Let's see how to implement the selection sorting algorithm in Python (based on Isai Damier):

Let's test the algorithm by adding the following statement at the end of the above script:

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

In this case you should get the following output:

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k

        swap(aList, least, i)

def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp

Linear search algorithm

[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]

Linear search

Algorithm is a simple algorithm in which each item in the list is checked (starting from the first item) until the desired item is found or the end of the list is reached.

The linear search algorithm is implemented in Python as follows (based on Python School):

Let's test the code. Enter the following statement at the end of the above Python script:

When entering

my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5]
selectionSort(my_list)
print(my_list)

, make sure it is between single or double quotes (i.e.

). For example, if you type

, you should get the following output:

def linearSearch(item,my_list):
    found = False
    position = 0
    while position < len(my_list) and not found:
        if my_list[position] == item:
            found = True
        position = position + 1
    return found

input'pencil' 'pencil' And if you enter

as input, you will get the following output:

Oops, your item seems not to be in the bag

Conclusion

As we have seen, Python proves itself again as a programming language that is easy to program the concept of algorithms, just like we deal with sorting and search algorithms here.

It should be noted that there are other types of sorting and search algorithms. If you want to dig deeper into these algorithms using Python, you can refer to the free Python object-oriented programming textbook.

The above is the detailed content of Sorting and Searching in Python. For more information, please follow other related articles on the PHP Chinese website!