Isih Algoritma || Python || Struktur Data dan Algoritma

Isih Algoritma

1. Isih Buih

Dalam hal ini, kita menukar elemen yang lebih tinggi dengan jirannya sehingga kita mencapai penghujung tatasusunan. Kini elemen tertinggi berada pada kedudukan terakhir. Jadi, kami menukar sempadan dan mengurangkannya sebanyak 1 daripada yang terakhir. Paling teruk, kita perlu mengulangi n kali untuk mengisih tatasusunan.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Algoritma -

1. Lelaran pada tatasusunan dan cari elemen maksimum, kemudian tukarkannya ke yang terakhir.
2. Bandingkan semua elemen bersebelahan dan tukar jika elemen yang lebih besar adalah sebelum elemen yang lebih kecil. Teruskan melakukan ini sehingga anda sampai ke penghujung tatasusunan.
3. Kekalkan bendera: jika tiada unsur ditukar, maka kita boleh memecahkan gelung, kerana tatasusunan diisih.

Kerumitan Masa :

• Kes Terbaik - Jika tatasusunan sudah diisih maka hanya satu lelaran diperlukan. Kerumitan masa - O(n)
• Kes Purata - jika tatasusunan diisih secara rawak, maka kerumitan masa - O(n2)
• Kes Terburuk - jika tatasusunan dalam susunan menurun maka kami akan memerlukan n*2 lelaran.

Kerumitan Angkasa - O(1), Tiada memori tambahan diperlukan.

Kelebihan -

1. Tiada memori tambahan diperlukan.

2. Stabil kerana unsur mengekalkan susunan relatifnya.

Kelemahan -

1. Kerumitan masa - O(n2), yang sangat tinggi untuk set data yang besar.

Aplikasi-

1. Boleh digunakan hanya apabila set data sangat kecil dan kesederhanaan mengatasi ketidakcekapan disebabkan kerumitan masa yang tinggi.

2. Isih Pemilihan

Dalam hal ini, kami mencari elemen terkecil dalam tatasusunan dan menggantikannya dengan elemen pertama. Kemudian, kita tambahkan sempadan sebanyak 1 dan ulangi langkah yang sama sehingga kita sampai ke penghujung tatasusunan.

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

Algoritma -

1. Lelaran pada tatasusunan dan cari elemen minimum.

2. Tukar dengan elemen pertama dan tambahkan penunjuk sebanyak 1.

3. Ulang proses ini sehingga kita sampai ke penghujung tatasusunan.

Kerumitan Masa : Ia mempunyai kerumitan masa O(n2) dalam ketiga-tiga kes: terbaik, purata dan paling teruk. Ini kerana kita perlu memilih elemen minimum dan tukarkannya setiap kali, tidak kira sama ada tatasusunan sudah diisih atau tidak.

Kerumitan Angkasa - O(1), Tiada memori tambahan diperlukan.

Kelebihan -

1. Tiada memori tambahan diperlukan.

2. Lebih sedikit pertukaran dilakukan berbanding dengan jenis gelembung.

Kelemahan -

1. Kerumitan masa - O(n2), yang sangat tinggi untuk set data yang besar.

2. Tidak Stabil, kerana ia tidak mengekalkan susunan relatif unsur yang sama.

Aplikasi -

1. Ia boleh digunakan dalam sistem dengan memori terhad kerana ia tidak memerlukan storan tambahan.

2. Ia digunakan dalam sistem yang meminimumkan bilangan swap adalah kritikal, seperti dalam sistem dengan operasi tulis perlahan.

3. Isih Sisipan

Ia ialah algoritma yang berfungsi dengan memasukkan elemen yang tidak diisih ke dalam kedudukan yang betul dengan menyemak secara berulang ke belakang dari kedudukan elemen ke permulaan tatasusunan.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Algoritma -

1. Mulakan dari elemen kedua tatasusunan dan bandingkan dengan elemen pertama. Jika elemen semasa lebih kecil daripada elemen pertama, maka tukar elemen tersebut.

2. Sekarang tingkatkan penunjuk dan lakukan ini untuk elemen ketiga: bandingkan dengan elemen kedua dan pertama.

3. Ulang proses yang sama untuk elemen yang lain, bandingkan dengan semua elemen sebelumnya dan masukkannya pada kedudukan yang sesuai.

Kerumitan Masa :

- Kes Terbaik - Jika tatasusunan sudah diisih maka hanya satu lelaran diperlukan. Kerumitan masa ialah O(n)
- Kes Purata - jika tatasusunan diisih secara rawak, maka kerumitan masa ialah O(n2)
- Kes Terburuk - jika tatasusunan berada dalam susunan menurun maka kami akan memerlukan n2 lelaran.

Kerumitan Angkasa - O(1), Tiada memori tambahan diperlukan.

Kelebihan -

1. Tiada memori tambahan diperlukan.
2. Stabil, kerana unsur mengekalkan susunan relatifnya.

Kelemahan -

1. Kerumitan masa - O(n2), yang sangat tinggi untuk set data yang besar.

2. Tidak Stabil, kerana ia tidak mengekalkan susunan relatif unsur yang sama.

Aplikasi-

1. Ia cekap untuk senario di mana unsur tiba dalam masa nyata dan perlu diisih, seperti strim data langsung.

4. Gabung Isih

Merge Sort ialah algoritma yang mengikut pendekatan bahagi dan takluk. Ia mempunyai dua langkah utama: pertama, membahagi tatasusunan secara rekursif dan kedua, menggabungkan tatasusunan yang dibahagikan mengikut tertib diisih.

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

Algoritma -

1. Bahagikan tatasusunan kepada dua bahagian dengan mengira titik tengah.

2. Teruskan membahagi sehingga panjang setiap sub-tatasusunan ialah 1.

3. Panggil fungsi cantum pada kedua-dua bahagian: separuh kiri dan separuh kanan.

4. Gunakan tiga penunjuk untuk proses penggabungan:

• Penunjuk pertama untuk tatasusunan separuh kiri.
• Penunjuk kedua untuk tatasusunan separuh kanan.
• Penunjuk ketiga untuk tatasusunan yang diisih.

1. Lelar melalui kedua-dua bahagian dan bandingkan elemennya. Masukkan elemen yang lebih kecil ke dalam tatasusunan yang diisih dan naikkan penunjuk yang sepadan sebanyak 1.

2. Ulang proses ini secara rekursif sehingga keseluruhan tatasusunan diisih.

Kerumitan Masa : Isih Gabungan mempunyai kerumitan masa O(n log n) dalam ketiga-tiga kes: terbaik, purata dan paling teruk. Ini kerana, tidak kira sama ada tatasusunan sudah diisih atau tidak, langkah yang sama diikuti untuk setiap bahagian dan bergabung.

O( log n ) - Saiz tatasusunan dibahagi separuh pada setiap langkah semasa fasa bahagi.

O(n) - Semasa proses penggabungan kita perlu mengulangi semua elemen sekali.

Jadi jumlah kerumitan masa ialah O (n) * O (log n) = O (n log n)

Kerumitan Ruang - O(n), Memori tambahan diperlukan semasa proses penggabungan untuk menyimpan tatasusunan sementara.

Kelebihan -

1. Stabil, kerana unsur mengekalkan susunan relatifnya.

2. Kerumitan masa ialah O (n log n), walaupun untuk set data yang besar.

3. Sesuai untuk pemprosesan selari kerana sub-tatasusunan digabungkan secara bebas.

Kelemahan -

1. Kerumitan masa - O(n2), yang sangat tinggi untuk set data yang besar.
2. Memori tambahan diperlukan untuk proses penggabungan.
3. Tiada pada tempatnya kerana memori tambahan diperlukan.
4. Lebih perlahan daripada QuickSort secara umum untuk kebanyakan set data.

Aplikasi -

1. Ia digunakan dalam situasi di mana data terlalu besar untuk dimuatkan dalam ingatan, seperti menggabungkan fail besar.
2. Ia digunakan untuk mengisih senarai terpaut kerana akses rawak tidak diperlukan.

5. Isih Pantas

Isih Pantas ialah algoritma yang mengikut pendekatan divide-and-conquer. Kami memilih elemen pangsi dan membahagikan tatasusunan di sekeliling elemen pangsi selepas meletakkan pangsi dalam kedudukan diisih yang betul.

Langkah pertama ialah memilih elemen pangsi dan kemudian membahagikan tatasusunan di sekeliling pangsi. Semua elemen yang lebih kecil daripada pangsi akan berada di sebelah kiri, dan semua elemen yang lebih besar daripada pangsi akan berada di sebelah kanannya. Pivot kemudiannya berada dalam kedudukan diisih yang betul. Secara rekursif, proses yang sama digunakan dengan membahagikan tatasusunan kepada dua bahagian: separuh pertama mengandungi elemen sebelum pangsi, dan separuh kedua mengandungi elemen selepas pangsi. Proses ini diulang sehingga panjang setiap sub-tatasusunan mencapai 1.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Algoritma -

1. Bahagikan tatasusunan kepada dua bahagian dengan mengira titik tengah.
2. Pilih pangsi; sebarang elemen boleh dipilih sebagai pangsi.
3. Lelaran pada tatasusunan dan bandingkan setiap elemen dengan pangsi.
4. Letakkan semua elemen lebih kecil daripada pangsi di sebelah kiri dan semua elemen lebih besar daripada pangsi di sebelah kanan.
5. Tukar pangsi dengan penuding kiri supaya pangsi berada pada kedudukan isih yang betul.
6. Ulang proses ini secara rekursif sehingga panjang partition melebihi 1.

Kerumitan Masa :

1. Kes Terbaik - Kerumitan masa - O(n log n), apabila pangsi membahagi tatasusunan kepada dua bahagian yang sama.
2. Kes Purata - Kerumitan masa - O(n log n), apabila pangsi membahagi tatasusunan kepada dua bahagian yang sama. Tetapi tidak semestinya sama.
3. Kes terburuk - Kerumitan masa - O(n2) , Bila -

• Elemen terkecil dipilih sebagai pangsi dalam tatasusunan yang telah diisih.

• Elemen terbesar dipilih sebagai pangsi dalam tatasusunan yang diisih dalam tertib menurun.

O( log n ) - Saiz tatasusunan dibahagi separuh pada setiap langkah semasa fasa bahagi.

O(n) - Semasa menyusun elemen.

Jadi, jumlah kerumitan masa ialah O (n) * O (log n) = O (n log n)

Kerumitan Angkasa Lepas :

1. Kes Terbaik dan Purata - O( log n) - untuk tindanan rekursif.

2. Kes Terburuk - O(n) - untuk tindanan rekursif.

Kelebihan -

1. Cekap untuk set data yang besar melainkan pangsi dipilih tidak baik.
2. Ia mesra cache kerana kami bekerja pada tatasusunan yang sama untuk mengisih dan tidak menyalin data ke mana-mana tatasusunan tambahan.
3. Salah satu algoritma tujuan umum terpantas untuk data besar apabila kestabilan tidak diperlukan.

Kelemahan -

1. Kerumitan masa - O(n2), yang sangat tinggi untuk set data yang besar.
2. Tidak Stabil, kerana ia tidak mengekalkan susunan relatif unsur yang sama.

Aplikasi -

1. Ia digunakan dalam perpustakaan pengaturcaraan dan rangka kerja. Contohnya - fungsi sorted() Python dan Array.sort() Java adalah berdasarkan isihan pantas.
2. Ia digunakan pengoptimuman pertanyaan indDatabase dengan menyusun baris dengan cekap semasa pelaksanaan pertanyaan.
3. Ia berfungsi dengan baik untuk pengisihan dalam memori bagi set data yang besar kerana sifat mesra cachenya.

6.Isih Timbunan

Isih Timbunan ialah algoritma pengisihan berasaskan perbandingan. Ia adalah lanjutan daripada Isih Pemilihan. Dalam Heap Sort, kami mencipta Binary Heap dan menukar elemen maksimum atau minimum dengan elemen terakhir. Kemudian, kita kurangkan saiz timbunan sebanyak 1. Proses ini diulang sehingga panjang timbunan lebih besar daripada 1.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

Algoritma -

1. Bina timbunan maksimum menggunakan proses timbunan. Heapify ialah kaedah yang digunakan untuk mengekalkan sifat timbunan struktur data timbunan binari.
2. Jika tatasusunan bersaiz n, ia mengandungi n//2 nod induk.
3. Untuk ibu bapa di indeks i:

a.Anak kirinya berada di indeks 2i 1

b. Anak kanannya berada di indeks 2i 2

1. Lelaran pada semua subpokok dengan ibu bapa daripada indeks n//2 hingga 0 dan panggil fungsi heapify padanya.
2. Kini, tatasusunan menjadi timbunan maksimum, dengan elemen terbesar pada indeks 0.
3. Tukar elemen pertama dengan elemen terakhir timbunan dan kurangkan saiz timbunan sebanyak 1.
4. Ulang proses ini sehingga panjang timbunan lebih daripada 1

Kerumitan Masa : Isih Timbunan mempunyai kerumitan masa O(n log n) dalam ketiga-tiga kes: terbaik, purata dan paling teruk. Ini kerana, tidak kira sama ada tatasusunan sudah diisih atau tidak, langkah yang sama diikuti setiap kali timbunan maksimum dibuat dan elemen ditukar.

O( log n ) - Untuk mencipta timbunan maks

O(n) - Apabila timbunan maks dibuat dan elemen ditukar n kali.

Jadi jumlah kerumitan masa ialah O (n) * O (log n) = O (n log n)

Kerumitan Ruang : Untuk semua kes - O( log n) - untuk timbunan rekursif.

Kelebihan -

1. Kerumitan masa ialah O (n log n), walaupun untuk set data yang besar.
2. Penggunaan memori hampir berterusan.

Kelemahan -

1. Tidak Stabil, kerana ia tidak mengekalkan susunan relatif unsur yang sama.
2. Banyak pertukaran diperlukan berbanding dengan pengisihan gabungan.

Aplikasi -

1. Ia berguna untuk melaksanakan baris gilir keutamaan di mana pengekstrakan elemen maksimum atau minimum adalah kerap.
2. Berguna dalam sistem yang memerlukan pengisihan di tempat dan penggunaan memori adalah kritikal.
3. Ia digunakan dalam senario di mana kedudukan diperlukan.

7. Isih Mengira dan Isih Radix

Isih Mengira ialah algoritma pengisihan bukan berasaskan perbandingan. Ia amat cekap apabila julat nilai input adalah kecil berbanding dengan bilangan elemen yang akan diisih. Idea asas di sebalik Pengisihan Pengiraan ialah mengira kekerapan setiap elemen yang berbeza dalam tatasusunan input dan menggunakan maklumat tersebut untuk meletakkan elemen dalam kedudukan yang disusun dengan betul.

Radix Sort menggunakan Counting Sort sebagai subrutin. Ia menggunakan Isih Mengira pada setiap tempat digit nombor dan mengisih berulang kali sehingga ia memproses semua digit nombor terbesar dalam tatasusunan.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

Algoritma -

1. Cari nombor maksimum dalam tatasusunan dan tentukan bilangan digit (d) di dalamnya. Jika panjang nombor itu ialah d, Mengira Isih dipanggil d kali pada tatasusunan.

2. Isih Mengira Panggilan untuk setiap tempat digit dalam tatasusunan, bermula dari tempat satu, kemudian tempat puluhan, dan seterusnya.

3. Dalam Pengiraan jenis:

• Mula-mula, buat tatasusunan indeks dan petakan elemen berdasarkan nilainya.Sebagai contoh, jika digit ialah 4, naikkan nilai pada indeks ke-4 tatasusunan indeks.
• Buat tatasusunan jumlah awalan daripada tatasusunan indeks.
• Menggunakan tatasusunan jumlah awalan, cipta tatasusunan diisih baharu bersamaan dengan panjang tatasusunan input
• Sebagai contoh, jika tatasusunan jumlah awalan mempunyai nilai 2 pada indeks 1, letakkan nilai 1 pada kedudukan 2 dalam tatasusunan yang diisih dan kurangkan nilai dalam tatasusunan jumlah awalan dengan 1

Kerumitan Masa :

Isih Mengira mempunyai kerumitan masa O(n k), dengan n ialah bilangan elemen untuk diisih dan k ialah julat nilai (saiz tatasusunan indeks). Kerumitan ini sah untuk ketiga-tiga kes: terbaik, sederhana dan paling teruk.

Ini kerana, tidak kira sama ada tatasusunan sudah diisih atau tidak, langkah yang sama diikuti setiap kali.

Kerumitan masa

Radix Sort meningkat dengan faktor d, dengan d ialah bilangan digit dalam nombor terbesar dalam tatasusunan. Kerumitan masa ialah O (d * (n k))

Jadi jumlah kerumitan masa ialah O (d) * O(n k) = O (d * (n k))

Kerumitan Ruang : Untuk semua kes - O(n k), dengan n ialah panjang tatasusunan input dan k ialah julat nilai dalam tatasusunan indeks.

Kelebihan -

1. Stabil kerana unsur mengekalkan susunan relatifnya.
2. Isih mengira biasanya berprestasi lebih pantas daripada semua algoritma pengisihan berasaskan perbandingan, seperti isihan gabungan dan isihan pantas, jika julat input adalah mengikut tertib bilangan input.

Kelemahan -

1. Mengira isihan tidak berfungsi pada nilai perpuluhan.
2. Mengira isihan adalah tidak cekap jika julat nilai yang hendak diisih adalah sangat besar.
3. Tidak sesuai dengan algoritma pengisihan, kerana ia menggunakan ruang tambahan O(O(n m)).

Aplikasi -

1. Ia digunakan dalam aplikasi seperti mengira kejadian aksara dalam rentetan.
2. Berguna untuk mengisih integer dengan julat nilai yang besar, seperti ID atau nombor telefon.
3. Cekap untuk mengisih data dengan berbilang kunci, seperti tarikh atau tupel.

Atas ialah kandungan terperinci Isih Algoritma || Python || Struktur Data dan Algoritma. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!