Program C Untuk Penyortiran Gelembung: Pengurutan Gelembung dalam C

pengantar

Penyortiran array memegang tempat yang sangat penting dalam ilmu komputer. Kegunaannya diperhatikan ketika ada kebutuhan untuk mengatur data dalam urutan tertentu. Ada berbagai jenis algoritma pengurutan. Algoritma pengurutan yang paling umum dan banyak digunakan adalah Bubble Sort.

Sortir Gelembung dalam C

Teknik yang digunakan untuk menyortir dalam Bubble sort sederhana dan mudah dipahami. Yang dilakukannya hanyalah membandingkan elemen saat ini dengan elemen berikutnya dan menukarnya jika lebih besar atau lebih kecil seperti yang ditentukan oleh kondisinya. Algoritma ini sangat akurat. Setiap kali suatu elemen dibandingkan dengan elemen lain sampai tempatnya ditemukan, itu disebut lulus.

Algoritme ini sebanding dengan gelembung dalam air karena menyaring bagian atas gelembung seperti susunan. Di antara semua algoritma yang digunakan untuk pengurutan, Bubble sort adalah yang termudah dan paling lambat dengan kompleksitas waktu O(n^2). Namun, algoritme dapat dioptimalkan melalui penggunaan variabel flag yang keluar dari loop saat pertukaran selesai. Kasus terbaik untuk Bubble sort adalah O(n) ketika array diurutkan.

Sebagai contoh, mari kita ambil array lima angka yang tidak disortir seperti yang diberikan di bawah ini

13, 32,26, 34,9

Bubble sort akan mulai mempertimbangkan dua elemen pertama, dan akan membandingkannya untuk memeriksa mana yang lebih besar. Dalam hal ini, 32 lebih besar dari 13. Jadi bagian ini sudah diurutkan y. Selanjutnya, kita bandingkan 32 dengan 26. Jadi kita menemukan bahwa 32 lebih besar dari 26, sehingga harus ditukar. Array baru akan terlihat seperti

13, 26, 32,34,9

Selanjutnya, kita bandingkan 32 dan 34. Kita tahu bahwa mereka sudah diurutkan. Jadi kita pindah ke dua variabel terakhir 34 dan 9. Karena 34 lebih besar dari 9, mereka harus ditukar.

Kami menukar nilai dan sampai ke akhir array setelah iterasi pertama. Sekarang array akan terlihat seperti

13, 26. 32,9,34

Setelah iterasi kedua, array akan terlihat seperti

13, 26, 9,32,34

Setelah iterasi ketiga, array akan menjadi

13.9,26,32,34

Setelah iterasi keempat, array akan sepenuhnya diurutkan

9, 13,26,32,34

Harus Dibaca: Ide Proyek di C

Algoritme

Di sini kita mengasumsikan bahwa array memiliki n elemen. Selanjutnya, kami berasumsi bahwa fungsi nilai tukar menukar semua nilai untuk membuat nomor array dalam urutan yang diurutkan.

mulai BubbleSort (array)

untuk semua elemen daftar

jika larik[i]> larik[i+1]

nilai tukar(array[i], array[i+1] )

berakhir jika

akhir untuk

kembalikan larik

akhiri Bubble Sort

Baca: Pengurutan dalam Struktur Data: Kategori & Jenis

Kode semu

Terbukti pada algoritma di atas bahwa ada perbandingan antara setiap pasangan elemen array sampai seluruh array diurutkan dalam urutan menaik. Ini dapat mengakibatkan beberapa masalah kompleksitas, seperti hasil algoritme ketika array sudah diurutkan dalam urutan menaik. Untuk mengurangi masalah, kami akan menggunakan satu variabel flag, yang memungkinkan kami untuk melihat apakah telah terjadi pertukaran. Jika tidak diperlukan lagi swapping, kita akan keluar dari loop dalam.

Pseudocode untuk algoritma BubbleSort dapat ditulis sebagai berikut:

prosedur BubbleSort (array: item dalam array)

iterasi= array.jumlah;

untuk k=0 hingga iterate-1 lakukan:

bendera = salah

untuk l=0 hingga iterate-1 lakukan:

jika (array[l]> array[l+1]) maka

nilai tukar(array[l], array [l+1])

bendera = benar

berakhir jika

akhir untuk

Jika (tidak ditukar) maka

Merusak

Berakhir jika

Akhir untuk

Akhiri prosedur pengembalian array

Mari kita coba contoh program bubble sort di C :

# sertakan<stdio.h>

batal utama

{

int array [10], i, j, num

untuk (i=0; i<=9; i++)

{

scanf(“%d”, &array[i])

}

untuk(i=0;i<=9;i++)

{

untuk(j=0;j<=9-i;j++)

{

jika(array[j]>array[j+1])

{

jumlah= larik[j];

array[j]=array[j+1];

array[j+1]=jumlah;

}

}

}

printf(“Array yang diurutkan adalah /n”);

untuk(i=0;i<=9;i++)

{

printf(“%d”,&array[i])

}

}

Seperti yang ditunjukkan dalam contoh, algoritme pengurutan gelembung ini menerima 10 angka dari pengguna dan menyimpannya dalam larik. Di bagian selanjutnya, ada dua for loop. Lingkaran luar berjalan untuk nilai I, sama dengan nol hingga kurang dari sama dengan sembilan. Fungsi loop luar adalah untuk menjaga semua elemen nilai yang harus dibandingkan dengan elemen lain.

Ada loop lain di dalam loop luar. Itu dimulai dari j=0 dan berjalan sampai lebih kecil dari atau sama dengan delapan. Di dalam, ada pernyataan if bersyarat yang membandingkan dan memeriksa apakah array[j] lebih besar dari array [j+1]. Jika kondisi terpenuhi, nilai array[j] dan array [j+1] ditukar satu sama lain.

Variabel dengan nama num digunakan untuk tujuan ini. Array pertama[j] ditetapkan ke num, kemudian array[j+1] ditugaskan ke array[j], dan terakhir num ditugaskan ke array[j+1]. Proses ini akan berlanjut sampai semua elemen dalam array diurutkan dalam urutan yang meningkat. Setelah itu, array yang diurutkan akan dicetak.

Implementasi Bubble Sort yang dioptimalkan

Kami memiliki algoritme yang dioptimalkan untuk pengurutan gelembung untuk meningkatkan hasil. Penggunaan variabel flag melakukan optimasi. Variabel flag akan menahan 1 jika ada swapping yang lain akan keluar dari loop. Di bawah ini adalah program pengurutan gelembung yang dioptimalkan di C.

#sertakan<stdio.h>

batal utama

{

int array [10], i, j, num, flag=0;

untuk (i=0; i<=9; i++)

{

scanf(“%d”, &array[i])

}

untuk(i=0;i<=9;i++)

{

untuk(j=0;j<=9-i;j++)

{

jika(array[j]>array[j+1])

{

jumlah= larik[j];

array[j]=array[j+1];

array[j+1]=jumlah;

bendera=1;

}

jika (! bendera)

{

merusak;

}

}

}

printf(“Array yang diurutkan adalah /n”);

untuk(i=0;i<=9;i++)

{

printf(“%d”,&array[i])

}

}

Program yang diberikan dijalankan dengan cara yang mirip dengan program bubble sort biasa. Satu-satunya perubahan adalah penggunaan variabel flag. Awalnya, flag diset ke 0. Namun, jika terjadi swapping, flag menjadi 1. Ini menyiratkan bahwa array masih memerlukan satu pemeriksaan lagi. Di sisi lain, jika bendera bukan 1, menyiratkan bahwa pertukaran belum terjadi, kami keluar dari loop dalam, dengan asumsi bahwa array sudah diurutkan. Setelah dieksekusi, kita akan mendapatkan hasil yang sama seperti Bubble sort biasa.

Kompleksitas Waktu

Kompleksitas waktu kasus terbaik untuk Bubble sort adalah O(n). Itu terjadi ketika array sudah diurutkan. Kasus terburuk adalah O(n*n) ketika array belum diurutkan.

Baca: 12 Program Pola Teratas di Java yang Harus Anda Periksa Hari Ini

Apa selanjutnya?

Jika Anda tertarik untuk mempelajari lebih lanjut tentang Java, pengembangan perangkat lunak full-stack, lihat Diploma PG Tingkat & IIIT-B dalam Pengembangan Perangkat Lunak Full-stack yang dirancang untuk profesional yang bekerja dan menawarkan 500+ jam pelatihan ketat, 9+ proyek , dan penugasan, status Alumni IIIT-B, proyek batu penjuru praktis & bantuan pekerjaan dengan perusahaan-perusahaan top.