Memahami Isih Sisipan: Pendekatan Didorong Soalan

Dalam catatan blog ini, kami akan mengambil pendekatan terdorong soalan untuk memahami asas algoritma isihan sisipan. Saya menghasilkan pendekatan ini apabila saya cuba mencari cara yang lebih baik untuk memahami algoritma sisipan dan lain-lain yang akan saya pelajari tidak lama lagi. Saya ingin membina strategi yang boleh saya gunakan pada kebanyakan, jika tidak semua, algoritma yang akan saya pelajari. Semasa saya memikirkan perkara ini, saya pasti bahawa saya mungkin perlu menggunakan pemikiran prinsip pertama

Diinspirasikan oleh pemikiran prinsip pertama, pendekatan ini melibatkan percubaan pertama untuk memahami algoritma, sama ada pemahaman awal kita kabur atau jelas. Kami kemudiannya mengenal pasti konsep atau mekanik kecil yang terlibat yang membentuk algoritma. Dengan membentuk soalan mengenai mekanik atau konsep kecil ini. Kami pada asasnya cuba memahami cara kerja algoritma dari perspektif kecil yang berbeza dengan tumpuan untuk cuba menyelesaikan soalan yang kami bentuk sendiri.

Jawapan yang anda bentuk mungkin atau mungkin tidak pada mulanya menyerupai sintaks yang digunakan dalam algoritma sebenar. Matlamatnya adalah untuk menjawab soalan anda sendiri, tidak kira sama ada sintaksnya hampir atau tidak. Sebaik sahaja anda mempunyai pemahaman yang jelas, anda kemudian boleh menukar, menggabungkan jawapan anda untuk menggunakan sintaks, serupa dengan pelaksanaan sebenar algoritma. Saya percaya proses ini membolehkan anda meneroka bentuk kod alternatif, memahami sebab sintaks tertentu digunakan, menangani kes tepi dengan cara yang lebih baik sendiri.

Saya percaya kaedah ini memastikan kami memahami teori dan alasan di sebalik setiap baris kod, menjadikan proses pelaksanaan lebih intuitif dan bermakna. Soalan berikut dan proses pemikiran yang saya lalui membantu saya memahami Isih Sisipan dengan lebih baik dan membolehkan saya mengodkannya dengan berkesan.

Bagi anda, soalan mungkin berbeza; mereka mungkin lebih banyak, lebih sedikit atau berbeza sama sekali. Mungkin ada yang mengatakan ini serupa dengan kejuruteraan terbalik, walau apa pun yang anda panggil, kaedah ini membolehkan saya mendapat pemahaman yang menyeluruh tentang algoritma Isih Sisipan. Saya harap ia melakukan perkara yang sama untuk anda untuk mana-mana algoritma lain. Soo, mari selami!

Pelaksanaan Isih Sisipan

Ini ialah bentuk kod yang akhirnya akan kami laksanakan untuk Isih Sisipan.

def insertion_sort(values):

    for new_value_index in range(1,len(values)):

        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1

        values[index+1] = new_value

Soalan

Diberi senarai diisih, menggunakan gelung sambil, cetak nilai dari kanan ke kiri.

values = [4,8,12,16,20,24,30]
# given a sorted list, using while loop, print values from right to left.

index = len(values)-1
while index>=0:
    print(values[index],end = " ")
    index-=1

Memandangkan senarai diisih dan nilai baharu, cari indeks di mana nilai baharu itu akan dimasukkan untuk memastikan senarai diisih.

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# using while loop, if traversing from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value: break
    index-=1

print(values,new_value,index)

Memandangkan senarai diisih dan nilai baharu, masukkan nilai baharu pada senarai supaya ia kekal diisih.

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# if traversal from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value:break
    index-=1

values = values[:index+1] + [new_value] + values[index+1:]
print(values)

Diberi senarai diisih, kemudian ditambah dengan nilai baharu, alihkan nilai baharu ke kedudukan indeks yang diberikan.

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

given_index = 3

# above given

n = len(values)-1

index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

print(values)

values[given_index+1] = new_value

print(values)

Diberi senarai diisih, kemudian ditambah dengan nilai baharu, isih senarai.

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

print(values)

### given a sorted list, then appended with new value, sort the list
####

n = len(values)-1
new_value = values[-1]

# find the index at which the value is to be inserted
# right to left
index = n-1
while index>=0:
    if values[index]<new_value:break
    index-=1
given_index = index 
print("given_index : "  , given_index)

# move the values forward by one step until we reach the given index
index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

values[index+1] = new_value

print(values)

Diberikan senarai diisih, kemudian ditambah dengan nilai baharu, susun senarai.

values = [4, 8, 12, 16, 20, 24, 30]

new_values = [14,32]

values += new_values

print(values)

# given a sorted list, then appended with two new value(s), sort the list

n = len(values)-1

new_value_start_index = n - 1

print(new_value_start_index, values[new_value_start_index])

for new_value_index in range(new_value_start_index,len(values)):

    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value: break
        values[index+1] = values[index]
        index-=1

    values[index+1] = new_value

print(values)

Senarai diberi, susunlah.

import random

values = random.sample(range(10,90), k = 10)

values

print(values)

for new_value_index in range(1,len(values)):
    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value:break
        values[index+1] = values[index]
        index-=1
    values[index+1] = new_value

print(values)

Pelaksanaan Isih Sisipan

def insertion_sort(values):
    for new_value_index in range(1,len(values)):
        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1
        values[index+1] = new_value

Sumber Tambahan

Walaupun saya pada mulanya bekerja melalui set soalan yang komprehensif untuk memahami algoritma dengan lebih baik, soalan di atas adalah satu set soalan yang saya fikir penting untuk memahami Isih Sisipan dengan cara yang lebih baik. Termasuk semua soalan yang saya kerjakan akan menjadikan siaran itu agak panjang.

Bagi mereka yang berminat untuk melihat semua soalan, saya telah mencipta Buku Nota Jupyter yang mengandungi set penuh soalan dengan jawapan saya sendiri, yang membolehkan saya memahami pelaksanaan Isih Sisipan sepenuhnya.

Saya menggalakkan anda menyemak buku nota jika anda ingin menyelidiki lebih lanjut.

Pembetulan dan cadangan dialu-alukan.

Atas ialah kandungan terperinci Memahami Isih Sisipan: Pendekatan Didorong Soalan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!