Penyortiran dalam Struktur Data: Kategori & Jenis [Dengan Contoh]

Susunan data dalam urutan yang disukai disebut pengurutan dalam struktur data. Dengan menyortir data, lebih mudah untuk mencarinya dengan cepat dan mudah. Contoh pengurutan yang paling sederhana adalah kamus. Sebelum era Internet, ketika Anda ingin mencari kata dalam kamus, Anda harus melakukannya dalam urutan abjad. Ini membuatnya mudah.

Bayangkan kepanikan jika Anda harus membaca buku besar dengan semua kata bahasa Inggris dari dunia dalam urutan yang campur aduk! Ini adalah kepanikan yang sama yang akan dialami seorang insinyur jika data mereka tidak diurutkan dan terstruktur.

Jadi, singkatnya, menyortir membuat hidup kita lebih mudah. Lihat kursus ilmu data kami untuk mempelajari secara mendalam tentang algoritme ilmu data.

Dalam posting ini, kami akan membawa Anda melalui berbagai struktur data & algoritma penyortiran. Tapi pertama-tama, mari kita pahami apa itu algoritma pengurutan dan pengurutan dalam struktur data.

Apa itu Algoritma Pengurutan?

Algoritma pengurutan hanyalah serangkaian perintah atau instruksi. Dalam hal ini, array adalah input, di mana algoritma pengurutan melakukan operasi untuk memberikan array yang diurutkan.

Banyak anak akan belajar mengurutkan struktur data di kelas ilmu komputer mereka. Ini diperkenalkan pada tahap awal untuk membantu anak-anak yang tertarik mendapatkan ide tentang topik ilmu komputer yang lebih dalam – metode bagi-dan-taklukkan, pohon biner, tumpukan, dll.

Berikut adalah contoh dari apa yang dilakukan penyortiran.

Misalkan Anda memiliki array string: [h,j,k,i,n,m,o,l]

Sekarang, penyortiran akan menghasilkan larik keluaran dalam urutan abjad.

Keluaran: [h,i,j,k,l,m,n,o]

Mari pelajari lebih lanjut tentang pengurutan dalam struktur data.

Checkout: Jenis Pohon Biner

Mengurutkan Kategori

Ada dua kategori berbeda dalam penyortiran:

• Penyortiran internal : Jika data input sedemikian rupa sehingga dapat disesuaikan di memori utama sekaligus, itu disebut pengurutan internal.
• Penyortiran eksternal : Jika data input sedemikian rupa sehingga tidak dapat diatur dalam memori seluruhnya sekaligus, data tersebut perlu disimpan dalam hard disk, floppy disk, atau perangkat penyimpanan lainnya. Ini disebut penyortiran eksternal.

Baca: Ide dan Topik Proyek Struktur Data yang Menarik

Jenis Penyortiran dalam Struktur Data

Berikut adalah beberapa jenis algoritma pengurutan yang paling umum.

1. Gabungkan Sortir

Algoritma ini bekerja pada pemisahan array menjadi dua bagian dengan ukuran yang sebanding. Setiap bagian kemudian diurutkan dan digabungkan kembali dengan menggunakan fungsi merge ().

Berikut cara kerja algoritma:

MergeSort(arr[], l, r)

Jika r > l

1. Bagilah array menjadi dua bagian yang sama dengan mencari titik tengah:

tengah m = (l+r)/2

2. Gunakan fungsi mergeSort untuk memanggil paruh pertama:

Panggil mergeSort(arr, l, m)

3. Panggil mergeSort untuk paruh kedua:

Panggil mergeSort(arr, m+1, r)

4. Gunakan fungsi merge () untuk menggabungkan dua bagian yang diurutkan pada langkah 2 dan 3:

Gabungan panggilan (arr, l, m, r)

Lihat gambar di bawah ini untuk mendapatkan gambaran yang jelas tentang cara kerjanya.

Sumber

Program python untuk implementasi sortir gabungan

def mergeSort(a):

jika len(a) >1:

tengah = len(a)//2

A = a[:pertengahan]

B = a[pertengahan:]

gabungUrutkan(A)

gabungUrutkan(B)

i = j = k = 0

sedangkan i < len(A) dan j < len(B):

jika A[i] < B[j]:

a[k] = A[i]

saya+=1

lain:

a[k] = B[j]

j+=1

k+1

sedangkan i < len(A):

a[k] = A[i]

saya+=1

k+1

sedangkan j < len(R):

a[k] = B[j]

j+=1

k+1

def printList(a):

untuk saya dalam jangkauan(len(a)):

print(a[i],end=" ")

mencetak()

jika __name__ == '__main__':

a = [12, 11, 13, 5, 6, 7]

gabungUrutkan(a)

print("Array yang diurutkan adalah: ", end="\n")

daftar cetak(a)

Pelajari lebih lanjut: Rekursi dalam Struktur Data: Cara Kerja, Jenis & Kapan Digunakan

2. Sortir Seleksi

Dalam hal ini, pada awalnya, elemen terkecil dikirim ke posisi pertama.

Kemudian, elemen terkecil berikutnya dicari di array yang tersisa dan ditempatkan di posisi kedua. Ini berlangsung hingga algoritma mencapai elemen terakhir dan menempatkannya di posisi yang tepat.

Perhatikan gambar di bawah ini untuk lebih memahaminya.

Sumber

Program Python untuk implementasi sortir seleksi

sistem impor

X = [6, 25, 10, 28, 11]

untuk i dalam rentang(len(X)):

min_idx = i

untuk j dalam rentang(i+1, len(X)):

jika X[min_idx] > X[j]:

min_idx = j

X[i], X[min_idx] = X[min_idx], X[i]

print (“Array yang diurutkan adalah”)

untuk i dalam rentang(len(X)):

cetak(“%d” %X[i]),

Sertifikasi Tingkat Lanjut Ilmu Data, 250+ Mitra Perekrutan, 300+ Jam Pembelajaran, 0% EMI

3. Gelembung Sortir

Ini adalah yang termudah dan paling sederhana dari semua algoritma pengurutan. Ini bekerja berdasarkan prinsip berulang kali menukar elemen yang berdekatan jika mereka tidak dalam urutan yang benar.

Dalam istilah yang lebih sederhana, jika input akan diurutkan dalam urutan menaik, bubble sort pertama-tama akan membandingkan dua elemen pertama dalam array. Jika yang kedua lebih kecil dari yang pertama, ia akan menukar keduanya, dan beralih ke elemen berikutnya, dan seterusnya.

Contoh :

Masukan : 637124

lulus pertama

63 7124 -> 36 7124 : Bubble sort membandingkan 6 dan 3 dan menukarnya karena 3<6.

3 67 124 -> 3 67 124 : Sejak 6<7, tidak ada pertukaran

36 71 24 -> 36 17 24 : Ditukar 7 dan 1, sebagai 7>1

361 72 4 -> 361 27 4 : Ditukar 2 dan 7, sebagai 2<7

3612 74 -> 3612 47 : Tukar 4 dan 7, sebagai 4<7

Umpan kedua

36 1247 -> 36 1247

3 61 274 -> 3 16 274

31 62 74 -> 31 26 74

312 67 4 -> 312 67 4

3126 74 -> 3126 47

Umpan ketiga

31 2647 -> 13 2647

1 32 647 -> 1 23 647

12 36 47 -> 12 36 47

123 64 7 -> 123 46 7

1234 67 -> 1234 67

Seperti yang Anda lihat, kami mendapatkan hasil urutan menaik setelah tiga lintasan.

Program Python untuk implementasi bubble sort

def bubbleSort(a):

n = len(a)

untuk saya dalam rentang (n):

untuk j dalam rentang (0, ni-1):

jika a[j] > a[j+1] :

a[j], a[j+1] = a[j+1], a[j]

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

pengurutan gelembung(a)

print ("Array yang diurutkan adalah:")

untuk saya dalam jangkauan(len(a)):

cetak (“%d” %a[i]),

Baca juga: Data Frame dengan Python: Tutorial Mendalam Python

Kesimpulan

Itu membungkus penyortiran dalam struktur data dan algoritme pengurutan yang paling umum. Anda dapat memilih salah satu dari berbagai jenis algoritma pengurutan. Namun, ingatlah bahwa beberapa di antaranya mungkin sedikit membosankan untuk menulis programnya. Tapi kemudian, mereka mungkin berguna untuk hasil yang cepat. Di sisi lain, jika Anda ingin mengurutkan kumpulan data besar, Anda harus memilih bubble sort. Tidak hanya menghasilkan hasil yang akurat, tetapi juga mudah diterapkan. Kemudian lagi, ini lebih lambat dari jenis lainnya. Saya harap Anda menyukai artikel tentang pengurutan dalam struktur data.

Untuk mendapatkan lebih banyak wawasan tentang cara kerja penyortiran, hubungi kami dan kami akan membantu Anda memulai kursus yang paling sesuai dengan kebutuhan Anda!

Jika Anda penasaran untuk belajar tentang ilmu data, lihat Program PG Eksekutif IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan pakar industri, 1 -on-1 dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.

Bersenang-senang mengkode!