Mengisih Algoritma dalam Python

Apakah Pengisihan?

Isih merujuk kepada proses menyusun data dalam susunan tertentu, biasanya dalam tertib menaik atau menurun, berdasarkan hubungan linear antara item data.

Mengapa Kita Perlu Isih?

Isih adalah penting apabila bekerja dengan data berstruktur kerana ia membolehkan pengambilan data yang cekap, memudahkan analisis data dan meningkatkan pengurusan data secara keseluruhan.

Isih Algoritma

Siaran ini merangkumi algoritma pengisihan berikut: Isih Buih, Isih Pilihan, Isih Sisipan, Isih Gabung dan Isih Pantas.

Isih Buih

Isih Gelembung berulang kali melangkah melalui tatasusunan, membandingkan elemen bersebelahan dan menukarnya jika ia berada dalam susunan yang salah. Proses ini berterusan sehingga tatasusunan diisih, dengan elemen yang lebih besar "bergelembung" hingga akhir.

Algoritma

Langkah 1: Mulakan
Langkah 2: i = 0
Langkah 3: jika saya < length(array) - 1, pergi ke Langkah 4; lain pergi ke Langkah 10
Langkah 4: j = 0
Langkah 5: jika j < length(array) - i - 1, pergi ke Langkah 6; lain pergi ke Langkah 3
Langkah 6: jika tatasusunan[j] > tatasusunan[j + 1], pergi ke Langkah 7; lain pergi ke Langkah 8
Langkah 7: Tukar tatasusunan[j] dan tatasusunan[j + 1]
Langkah 8: kenaikan j; pergi ke Langkah 5
Langkah 9: kenaikan i; pergi ke Langkah 3
Langkah 10: Tamat

Kod

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

Kerumitan Masa

Kes Terbaik : O(n)
Purata Kes : O(n^2)
Kes Terburuk : O(n^2)

Isih Pemilihan

Isih Pilihan mencari nilai terkecil dalam bahagian tatasusunan yang tidak diisih dan meletakkannya pada permulaan bahagian itu.

Algoritma

Langkah 1 : Mulakan
Langkah 2 : i = 0
Langkah 3 : jika saya < length(array) - 1, pergi ke Langkah 4; lain pergi ke Langkah 10
Langkah 4 : nilai_minimum = i; j = i + 1
Langkah 5 : jika j < length(array), goto Langkah 6; lain pergi ke Langkah 9
Langkah 6 : jika tatasusunan[nilai_minimum] > tatasusunan[j], pergi ke Langkah 7; lain pergi ke Langkah 8
Langkah 7 : nilai_minimum = j
Langkah 8 : kenaikan j; pergi ke Langkah 5
Langkah 9 : tukar tatasusunan[nilai_minimum] dan tatasusunan[i]
Langkah 10 : kenaikan i; pergi ke Langkah 3
Langkah 11 : Tamat

Kod

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_val]:
                min_val = j

        arr[i], arr[min_val] = arr[min_val], arr[i]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
selection_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

Kerumitan Masa

Kes Terbaik : O(n^2)
Purata Kes : O(n^2)
Kes Terburuk : O(n^2)

Isih Sisipan

Isih Sisipan membina tatasusunan yang diisih satu elemen pada satu masa dengan mengambil setiap elemen daripada bahagian yang tidak diisih dan memasukkannya ke kedudukan yang betul dalam bahagian yang diisih.

Algoritma

Langkah 1: Mulakan
Langkah 2: i = 1
Langkah 3: jika saya < len(arr), pergi ke Langkah 4; lain pergi ke Langkah 12
Langkah 4: kunci = arr[i]
Langkah 5: j = i - 1
Langkah 6: jika j >= 0 dan arr[j] > kunci, pergi ke Langkah 7; lain pergi ke Langkah 10
Langkah 7: arr[j + 1] = arr[j]
Langkah 8: susut j sebanyak 1
Langkah 9: pergi ke Langkah 6
Langkah 10: arr[j + 1] = kunci
Langkah 11: kenaikan i sebanyak 1; pergi ke Langkah 3
Langkah 12: Tamat

Kod

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)

Kerumitan Masa

Kes Terbaik : O(n)
Purata Kes : O(n^2)
Kes Terburuk : O(n^2)

Gabung Isih

Merge Sort ialah algoritma bahagi-dan-takluk yang membahagikan tatasusunan secara rekursif kepada sub-tatasusunan yang lebih kecil, mengisihnya dan kemudian menggabungkannya semula.

Algoritma

Algoritma Isih Gabung

Langkah 1: Mulakan
Langkah 2: Jika panjang(tatasusunan) <= 1, Kembalikan tatasusunan; pergi ke Langkah 9
Langkah 3: titik_tengah = panjang(tatasusunan) // 2
Langkah 4: left_half = array[:mid_point]
Langkah 5: right_half = tatasusunan[mid_point:]
Langkah 6: sorted_left = merge_sort(left_separuh)
Langkah 7: sorted_right = merge_sort(kanan_separuh)
Langkah 8: cantumkan kembali(diisih_kiri, diisi_kanan)
Langkah 9: Tamat

Fungsi Gabung

Langkah 1: Mulakan
Langkah 2: sorted_merge = []
Langkah 3: l = 0, r = 0
Langkah 4: jika l < len(kiri) dan r < len(kanan), pergi ke Langkah 5; lain pergi ke Langkah 9
Langkah 5: jika kiri[l] <= kanan[r], pergi ke Langkah 6; lain pergi ke Langkah 7
Langkah 6: tambah kiri[l] ke sorted_merge; kenaikan l sebanyak 1
Langkah 7: tambah kanan[r] pada sorted_merge; kenaikan r sebanyak 1
Langkah 8: pergi ke Langkah 4
Langkah 9: jika l < len(kiri), pergi ke Langkah 10; lain pergi ke Langkah 12
Langkah 10: tambah kiri[l] ke sorted_merge; kenaikan l sebanyak 1
Langkah 11: pergi ke Langkah 9
Langkah 12: jika r < len(kanan), pergi ke Langkah 13; lain pergi ke Langkah 15
Langkah 13: tambah kanan[r] pada sorted_merge; kenaikan r sebanyak 1
Langkah 14: pergi ke Langkah 12
Langkah 15: Kembalikan sorted_merge
Langkah 16: Tamat

Kod

def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            sorted_merge.append(left[l])
            l += 1
        else:
            sorted_merge.append(right[r])
            r += 1

    while l < len(left):
        sorted_merge.append(left[l])
        l += 1

    while r < len(right):
        sorted_merge.append(right[r])
        r += 1

    return sorted_merge

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid_point = len(arr) // 2
    left_half = arr[:mid_point]
    right_half = arr[mid_point:]

    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)

    return merge(sorted_left, sorted_right)

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
arr = merge_sort(arr)
print("Array After Sorting:", arr)

Kerumitan Masa

Kes Terbaik : O(n log n)
Kes Purata : O(n log n)
Kes Terburuk : O(n log n)

Quick Sort

Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.

Algorithm

Quick Sort

Step 1: Begin
Step 2: If low < high, goto Step 3; else goto Step 6
Step 3: pivot_index = partition(arr, low, high)
Step 4: quicksort(arr, low, pivot_index - 1)
Step 5: quicksort(arr, pivot_index + 1, high)
Step 6: End

Partition Function

Step 1: Begin
Step 2: pivot = arr[high]
Step 3: left = low, right = high - 1
Step 4: if left <= right goto Step 5, else goto Step 9
Step 5: if arr[left] > pivot and arr[right] < pivot, swap arr[left] and arr[right]
Step 6: if arr[left] <= pivot, increment left
Step 7: if arr[right] >= pivot, decrement right
Step 8: goto Step 4
Step 9: swap arr[left] and arr[high]
Step 10: return left
Step 11: End

Code

def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left <= right:
        if arr[left] > pivot and arr[right] < pivot:
            arr[left], arr[right] = arr[right], arr[left]
        if arr[left] <= pivot:
            left += 1
        if arr[right] >= pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 1, high)

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
quicksort(arr, 0, len(arr) - 1)
print("Array After Sorting:", arr)

Time Complexity

Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)

Atas ialah kandungan terperinci Mengisih Algoritma dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!