Home  >  Article  >  Backend Development  >  How to sort in python

How to sort in python

DDD
DDDOriginal
2023-08-29 14:54:363453browse

Python sorting methods include bubble sort, selection sort, insertion sort, quick sort, merge sort, heap sort, radix sort, etc. Detailed introduction: 1. Bubble sorting, sorting by comparing adjacent elements and exchanging their positions; 2. Selection sorting, sorting by finding the smallest element in the list and placing it at the end of the sorted part ; 3. Insertion sort, sorting by inserting each element into the appropriate position of the sorted part; 4. Quick sort, using the divide and conquer method to divide the list into smaller sublists, etc.

How to sort in python

Operating system for this tutorial: Windows 10 system, Python version 3.11.4, Dell G3 computer.

Python is a powerful programming language that provides a variety of sorting methods to sort data. In this article, we'll cover at least 7 different sorting methods, with detailed code examples.

1. Bubble Sort:

Bubble sort is a simple sorting algorithm that sorts by comparing adjacent elements and exchanging their positions. It iterates through the list repeatedly until no swaps occur.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

2. Selection Sort:

Selection sort is a simple sorting algorithm that finds the smallest element in the list and places it in the sorted part. Sort at the end.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

3. Insertion Sort:

Insertion sort is a simple sorting algorithm that sorts by inserting each element into the appropriate position of the sorted part.

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i-1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

4. Quick Sort:

Quick sort is an efficient sorting algorithm that uses the divide-and-conquer method to divide the list into smaller sublists and then recursively Sort a sublist.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

5. Merge Sort:

Merge sort is an efficient sorting algorithm that uses the divide-and-conquer method to divide the list into smaller sublists and then recursively Sort the sublists and finally merge them into an ordered list.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

6. Heap Sort:

Heap sort is an efficient sorting algorithm that uses a binary heap data structure for sorting.

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
def heap_sort(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

7. Radix Sort:

Radix sort is a non-comparative sorting algorithm that sorts elements based on the number of digits.

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
    for i in range(1, 10):
        count[i] += count[i-1]
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    for i in range(n):
        arr[i] = output[i]
def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr

This is a detailed code example of 7 different sorting methods. According to different data sets and performance requirements, choosing a suitable sorting algorithm can improve the efficiency and performance of the code

The above is the detailed content of How to sort in python. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn