SORTING

Definisi Sorting

Sorting adalah proses yang mengatur sekumpulan objek/data sehingga nilainya tersusun, baik itu dari kecil ke besar (ascending) atau dari besar ke kecil (descending). Disini saya akan membahasa tentang.

• ·         Bubble sort

• ·         Merge sort

• ·         Quick sort

Bubble Sort  
Bubble Sort adalah algoritma pengurutan paling sederhana yang bekerja dengan berulang kali menukar elemen yang berdekatan jika urutannya salah.

Contoh:

Pass Pertama:

(5 1 4 2 8) -> (1 5 4 2 8)

Di sini, algoritma membandingkan dua elemen pertama, dan bertukar sejak 5> 1.

(1 5 4 2 8) -> (1 4 5 2 8), Tukar sejak 5> 4

(1 4 5 2 8) -> (1 4 2 5 8), Tukar sejak 5> 2

(1 4 2 5 8) -> (1 4 2 5 8),

Sekarang, karena elemen-elemen ini sudah berurutan (8> 5), algoritma tidak menukar mereka.

Pass Kedua:

(1 4 2 5 8) -> (1 4 2 5 8)

(1 4 2 5 8) -> (1 2 4 5 8), Tukar sejak 4> 2

(1 2 4 5 8) -> (1 2 4 5 8)

(1 2 4 5 8) -> (1 2 4 5 8)

Sekarang, array sudah diurutkan, tetapi algoritma kami tidak tahu apakah itu selesai. Algoritme membutuhkan satu pass penuh tanpa swap apa pun untuk mengetahuinya.

Lulus Ketiga:

(1 2 4 5 8) -> (1 2 4 5 8)

(1 2 4 5 8) -> (1 2 4 5 8)

(1 2 4 5 8) -> (1 2 4 5 8)

(1 2 4 5 8) -> (1 2 4 5 8

Merge sort 
Merge sort adalah algoritma Divide and Conquer . Ini membagi array input dalam dua bagian, memanggil dirinya untuk dua bagian dan kemudian menggabungkan dua bagian yang diurutkan. Fungsi gabungan () digunakan untuk menggabungkan dua bagian. Penggabungan (arr, l, m, r) adalah proses utama yang mengasumsikan bahwa arr [l..m] dan arr [m + 1..r] diurutkan dan menggabungkan dua sub-array yang diurutkan menjadi satu. Lihat implementasi C berikut untuk detailnya.

MergeSort (arr [], l, r)

 Jika r> l

      1. Temukan titik tengah untuk membagi array menjadi dua bagian:  

              tengah m = (l + r) / 2

      2. Panggil mergeSort untuk babak pertama:   

              Panggil mergeSort (arr, l, m)

      3. Panggil mergeSort untuk babak kedua:

              Panggil mergeSort (arr, m + 1, r)

      4. Gabungkan dua bagian yang diurutkan dalam langkah 2 dan 3:

              Panggil gabungan (arr, l, m, r) 

Diagram berikut menunjukkan proses pengurutan gabungan lengkap untuk contoh array {38, 27, 43, 3, 9, 82, 10}. Jika kita melihat lebih dekat pada diagram, kita dapat melihat bahwa array secara rekursif dibagi menjadi dua bagian sampai ukuran menjadi 1. Setelah ukuran menjadi 1, proses penggabungan mulai bekerja dan mulai menggabungkan array kembali hingga array lengkap menjadi bergabung.

Quick sort

QuickSort adalah algoritma Divide and Conquer. Itu mengambil elemen sebagai pivot dan mempartisi array yang diberikan di sekitar pivot yang dipilih. Ada banyak versi quickSort yang memilih pivot dengan berbagai cara.

1.      Selalu pilih elemen pertama sebagai pivot.

2.      Selalu pilih elemen terakhir sebagai pivot (diterapkan di bawah)

3.      Pilih elemen acak sebagai pivot.

4.      Pilih median sebagai poros.

Proses utama dalam quickSort adalah partisi (). Target dari partisi adalah, diberikan array dan elemen x array sebagai pivot, letakkan x pada posisi yang benar dalam array yang diurutkan dan letakkan semua elemen yang lebih kecil (lebih kecil dari x) sebelum x, dan letakkan semua elemen yang lebih besar (lebih besar dari x) setelah x. Semua ini harus dilakukan dalam waktu linier.

Kode Pseudo untuk fungsi QuickSort rekursif:

 / * rendah -> Indeks awal, tinggi -> Indeks akhir * /

 quickSort (arr [], rendah, tinggi)

 {

     jika (rendah <tinggi)

     {

         / * pi adalah indeks partisi, arr [pi] sekarang

            di tempat yang tepat * /

         pi = partisi (arr, rendah, tinggi);

         quickSort (arr, low, pi - 1);  // Sebelum pi

         quickSort (arr, pi + 1, tinggi);  // Setelah pi

     }

 }