Python - Thuật toán sắp xếp

Sắp xếp đề cập đến việc sắp xếp dữ liệu theo một định dạng cụ thể. Thuật toán sắp xếp chỉ định cách sắp xếp dữ liệu theo một thứ tự cụ thể. Hầu hết các đơn đặt hàng phổ biến là theo thứ tự số hoặc từ điển.

Tầm quan trọng của việc sắp xếp nằm ở chỗ, việc tìm kiếm dữ liệu có thể được tối ưu hóa ở mức rất cao, nếu dữ liệu được lưu trữ theo cách được sắp xếp. Sắp xếp cũng được sử dụng để thể hiện dữ liệu ở các định dạng dễ đọc hơn. Dưới đây, chúng tôi thấy năm cách triển khai sắp xếp trong python.

• Sắp xếp bong bóng
• Hợp nhất Sắp xếp
• Sắp xếp chèn
• Shell Sort
• Sắp xếp lựa chọn

Sắp xếp bong bóng

Nó là một thuật toán dựa trên so sánh, trong đó từng cặp phần tử liền kề được so sánh và các phần tử được hoán đổi nếu chúng không theo thứ tự.

def bubblesort(list):

# Swap the elements to arrange in order
    for iter_num in range(len(list)-1,0,-1):
        for idx in range(iter_num):
            if list[idx]>list[idx+1]:
                temp = list[idx]
                list[idx] = list[idx+1]
                list[idx+1] = temp


list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

[2, 6, 11, 19, 27, 31, 45, 121]

Hợp nhất Sắp xếp

Merge sort đầu tiên chia mảng thành các nửa bằng nhau và sau đó kết hợp chúng theo cách đã sắp xếp.

def merge_sort(unsorted_list):
    if len(unsorted_list) <= 1:
        return unsorted_list
# Find the middle point and devide it
    middle = len(unsorted_list) // 2
    left_list = unsorted_list[:middle]
    right_list = unsorted_list[middle:]

    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)
    return list(merge(left_list, right_list))

# Merge the sorted halves

def merge(left_half,right_half):

    res = []
    while len(left_half) != 0 and len(right_half) != 0:
        if left_half[0] < right_half[0]:
            res.append(left_half[0])
            left_half.remove(left_half[0])
        else:
            res.append(right_half[0])
            right_half.remove(right_half[0])
    if len(left_half) == 0:
        res = res + right_half
    else:
        res = res + left_half
    return res

unsorted_list = [64, 34, 25, 12, 22, 11, 90]

print(merge_sort(unsorted_list))

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

[11, 12, 22, 25, 34, 64, 90]

Sắp xếp chèn

Sắp xếp chèn liên quan đến việc tìm đúng vị trí cho một phần tử nhất định trong danh sách đã sắp xếp. Vì vậy, ban đầu chúng tôi so sánh hai yếu tố đầu tiên và sắp xếp chúng bằng cách so sánh chúng. Sau đó, chúng tôi chọn phần tử thứ ba và tìm vị trí thích hợp của nó trong số hai phần tử đã được sắp xếp trước đó. Bằng cách này, chúng tôi dần dần tiếp tục thêm nhiều phần tử vào danh sách đã được sắp xếp bằng cách đặt chúng vào vị trí thích hợp của chúng.

def insertion_sort(InputList):
    for i in range(1, len(InputList)):
        j = i-1
        nxt_element = InputList[i]
# Compare the current element with next one
		
        while (InputList[j] > nxt_element) and (j >= 0):
            InputList[j+1] = InputList[j]
            j=j-1
        InputList[j+1] = nxt_element

list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

[2, 11, 19, 27, 30, 31, 45, 121]

Shell Sort

Shell Sort liên quan đến việc sắp xếp các phần tử cách xa ech khác. Chúng tôi sắp xếp một danh sách con lớn của một danh sách nhất định và tiếp tục giảm kích thước của danh sách cho đến khi tất cả các phần tử được sắp xếp. Chương trình dưới đây tìm khoảng trống bằng cách cân bằng nó với một nửa chiều dài của kích thước danh sách và sau đó bắt đầu sắp xếp tất cả các phần tử trong đó. Sau đó, chúng tôi tiếp tục đặt lại khoảng trống cho đến khi toàn bộ danh sách được sắp xếp.

def shellSort(input_list):
    
    gap = len(input_list) // 2
    while gap > 0:

        for i in range(gap, len(input_list)):
            temp = input_list[i]
            j = i
# Sort the sub list for this gap

            while j >= gap and input_list[j - gap] > temp:
                input_list[j] = input_list[j - gap]
                j = j-gap
            input_list[j] = temp

# Reduce the gap for the next element

        gap = gap//2

list = [19,2,31,45,30,11,121,27]

shellSort(list)
print(list)

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

[2, 11, 19, 27, 30, 31, 45, 121]

Sắp xếp lựa chọn

Trong sắp xếp lựa chọn, chúng tôi bắt đầu bằng cách tìm giá trị nhỏ nhất trong một danh sách nhất định và chuyển nó vào danh sách đã sắp xếp. Sau đó, chúng tôi lặp lại quy trình cho từng phần tử còn lại trong danh sách chưa được sắp xếp. Phần tử tiếp theo vào danh sách đã sắp xếp được so sánh với các phần tử hiện có và được đặt ở vị trí chính xác của nó. Vì vậy, ở cuối tất cả các phần tử từ danh sách không được sắp xếp được sắp xếp.

def selection_sort(input_list):

    for idx in range(len(input_list)):

        min_idx = idx
        for j in range( idx +1, len(input_list)):
            if input_list[min_idx] > input_list[j]:
                min_idx = j
# Swap the minimum value with the compared value

        input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]


l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

[2, 11, 19, 27, 30, 31, 45, 121]