Python - Algoritma Pengurutan

Pengurutan mengacu pada pengaturan data dalam format tertentu. Algoritme pengurutan menentukan cara untuk mengatur data dalam urutan tertentu. Urutan paling umum dalam urutan numerik atau leksikografis.

Pentingnya pengurutan terletak pada kenyataan bahwa pencarian data dapat dioptimalkan hingga tingkat yang sangat tinggi, jika data disimpan dengan cara yang diurutkan. Pengurutan juga digunakan untuk merepresentasikan data dalam format yang lebih mudah dibaca. Di bawah ini kita melihat lima implementasi pengurutan dengan python.

• Bubble Sort
• Gabungkan Sortir
• Sortir Penyisipan
• Sortir Kerang
• Sortir Pilihan

Bubble Sort

Ini adalah algoritma berbasis perbandingan di mana setiap pasangan elemen yang berdekatan dibandingkan dan elemen ditukar jika tidak berurutan.

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)

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

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

Gabungkan Sortir

Merge sort terlebih dahulu membagi array menjadi dua bagian yang sama, lalu menggabungkannya dalam cara yang diurutkan.

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))

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

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

Sortir Penyisipan

Urutan penyisipan melibatkan menemukan tempat yang tepat untuk elemen tertentu dalam daftar yang diurutkan. Jadi pada awalnya kami membandingkan dua elemen pertama dan mengurutkannya dengan membandingkannya. Kemudian kami memilih elemen ketiga dan menemukan posisi yang tepat di antara dua elemen yang diurutkan sebelumnya. Dengan cara ini kami secara bertahap menambahkan lebih banyak elemen ke daftar yang sudah diurutkan dengan meletakkannya di posisi yang tepat.

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)

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

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

Sortir Kerang

Penyortiran Shell melibatkan penyortiran elemen yang jauh dari gema lainnya. Kami mengurutkan sublist besar dari list yang diberikan dan terus mengurangi ukuran list hingga semua elemen diurutkan. Program di bawah ini menemukan celah dengan menyamakannya dengan setengah dari panjang ukuran daftar dan kemudian mulai menyortir semua elemen di dalamnya. Kemudian kami terus mengatur ulang celah hingga seluruh daftar diurutkan.

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)

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

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

Sortir Pilihan

Dalam pemilihan urutan kita mulai dengan mencari nilai minimum dalam daftar yang diberikan dan memindahkannya ke daftar yang diurutkan. Kemudian kami mengulangi proses untuk setiap elemen yang tersisa dalam daftar yang tidak diurutkan. Elemen berikutnya yang memasuki daftar yang diurutkan dibandingkan dengan elemen yang ada dan ditempatkan pada posisinya yang benar. Jadi pada akhirnya semua elemen dari daftar yang tidak diurutkan diurutkan.

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)

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

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