Algoritma Bubble Sort

Algoritma Bubble Sort

Memiliki sebuah array yang Anda butuhkan untuk dimasukkan ke dalam rangka ? Buatlah catatan bisnis dan ingin mengurutkan mereka dengan nomor ID atau nama belakang klien ? Kemudian Anda akan membutuhkan algoritma sorting . Untuk memahami algoritma pengurutan yang lebih kompleks dan efisien , penting untuk terlebih dahulu memahami sederhana , tapi lebih lambat algoritma . Pada artikel ini , Anda akan belajar tentang bubble sort , termasuk semacam dimodifikasi gelembung yang sedikit lebih efisien , insertion sort , dan selection sort . Semua ini algoritma pengurutan cukup baik untuk sebagian besar tugas-tugas kecil , meskipun jika Anda akan memproses sejumlah besar data, Anda ingin memilih salah satu algoritma pengurutan yang tercantum pada halaman penyortiran maju .


bubble sort

Algoritma paling sederhana adalah sorting bubble sort . Gelembung sort bekerja dengan iterasi ke array yang akan diurutkan dari elemen pertama sampai terakhir , membandingkan setiap pasangan elemen dan beralih posisi mereka jika perlu . Proses ini diulangi sebanyak yang diperlukan , sampai array diurutkan . Karena skenario terburuk adalah bahwa array dalam urutan terbalik , dan bahwa elemen pertama dalam array diurutkan adalah elemen terakhir dalam array dimulai , yang paling pertukaran yang akan diperlukan adalah sama dengan panjang array . Berikut ini adalah contoh sederhana :

Mengingat sebuah array 23.154 semacam gelembung akan mengakibatkan urutan berikut array sebagian diurutkan : 21354 , 21345 , 12345 . Pertama 1 dan 3 akan dibandingkan dan beralih , maka 4 dan 5 . Pada lulus berikutnya , 1 dan 2 akan beralih , dan array akan berada di urutan .

Dasar kode untuk bubble sort terlihat seperti ini , untuk menyortir array integer:

for ( int x = 0; x < n ; x + + )

{

for ( int y = 0 , y < n - 1 , y + + )

{

if ( array [ y ] > array [ y +1 ] )

{

int temp = array [ y +1 ] ;

array [ y +1 ] = array [ y ] ;

array [ y ] = temp;

}

}

}

Perhatikan bahwa ini akan selalu lingkaran n kali dari 0 sampai n , sehingga urutan algoritma ini adalah O ( n ^ 2 ) . Ini adalah kedua skenario terbaik dan terburuk karena kode tidak mengandung cara untuk menentukan apakah array sudah dalam rangka .

Sebuah versi yang lebih baik dari bubble sort , yang dikenal sebagai diubah bubble sort , termasuk bendera yang diatur jika pertukaran dilakukan setelah seluruh lulus melalui array . Jika tidak ada pertukaran dibuat , maka harus jelas bahwa array sudah dalam rangka karena tidak ada dua elemen perlu diaktifkan . Dalam hal ini, semacam ini harus berakhir . Urutan kasus baru terbaik untuk algoritma ini adalah O ( n ) , karena jika array sudah diurutkan , maka tidak ada pertukaran yang dibuat . Anda dapat mengetahui kode sendiri ! Ini hanya membutuhkan sedikit perubahan pada bubble sort asli .