Algoritma Isih Pemilihan

Apakah Isih Pemilihan?

Algoritma Isih Pemilihan membahagikan tatasusunan kepada dua bahagian: bahagian yang diisih dan bahagian yang tidak diisih. Pada mulanya, bahagian yang diisih kosong, dan bahagian yang tidak diisih mengandungi semua elemen. Algoritma berfungsi dengan mencari elemen terkecil (atau terbesar, bergantung pada susunan pengisihan) daripada bahagian yang tidak diisih dan menukarnya dengan elemen pertama bahagian yang tidak diisih. Proses ini berterusan sehingga keseluruhan tatasusunan diisih.

Langkah-langkah Algoritma

1. Mulakan dengan elemen pertama dalam tatasusunan dan anggap ia adalah yang terkecil.
2. Bandingkan elemen ini dengan elemen lain dalam tatasusunan.
3. Jika anda menjumpai elemen yang lebih kecil, tukarkannya dengan elemen pertama.
4. Beralih ke elemen seterusnya dalam tatasusunan dan ulangi proses untuk baki elemen yang tidak diisih.
5. Teruskan proses ini sehingga keseluruhan tatasusunan diisih.

#Suppose we have the following array:

arr = [64, 25, 12, 22, 11]

Lulus 1:

• Elemen terkecil antara indeks 0 dan tatasusunan yang lain ialah 11.
• Kami menukar 64 dengan 11.

Susunan selepas hantaran pertama: [11, 25, 12, 22, 64]

Pas 2:

• Sekarang, fokus pada subarray bermula dari indeks 1. Elemen terkecil antara 25, 12, 22, 64 ialah 12.
• Kami menukar 25 dengan 12.

Susun atur selepas hantaran kedua: [11, 12, 25, 22, 64]

Lulus 3:

• Unsur terkecil antara 25, 22, 64 ialah 22.
• Kami menukar 25 dengan 22.

Susun atur selepas hantaran ketiga: [11, 12, 22, 25, 64]

Lulus 4:

• Subarray kini mengandungi 25, 64. Memandangkan ia sudah teratur, tiada pertukaran diperlukan.

Tatasusunan diisih akhir: [11, 12, 22, 25, 64]

def selection_sort(arr):
    # Traverse through all array elements
    for i in range(len(arr)):
        # Find the minimum element in the remaining unsorted part
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

Tatasusunan diisih: [11, 12, 22, 25, 64]

Kerumitan Masa Isih Pemilihan:

• Kes Terbaik: O(n²)

• Kes Purata: O(n²)

• Kes Terburuk: O(n²)

Walaupun Isih Pemilihan berprestasi baik untuk set data kecil, ia tidak sesuai untuk tatasusunan yang lebih besar kerana kerumitan masanya ialah O(n²). Walau bagaimanapun, ia mudah untuk dilaksanakan dan boleh berguna dalam kes di mana ingatan menjadi kebimbangan, kerana Isih Pemilihan ada di tempatnya (tidak memerlukan memori tambahan).

Kelebihan dan Kekurangan

Kelebihan:

• Mudah untuk difahami dan dilaksanakan.

• Berprestasi baik pada senarai kecil.

• Tidak memerlukan memori tambahan kerana ia menyusun tatasusunan di tempatnya.

Kelemahan:

• Tidak cekap untuk set data yang besar kerana O(n²) kerumitan masanya.

• Ia bukan algoritma pengisihan yang stabil, bermakna elemen yang sama mungkin tidak mengekalkan susunannya berbanding satu sama lain.

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