Algoritma - Sorting Linear Time

Kita tahu bahwa tidak mungkin untuk mengurutkan elemen n lebih cepat dari O(n lg n) dalam kasus terburuk ketika hanya menggunakan perbandingan namun ternyata ada algoritma penyortiran yang berjalan lebih cepat dari itu mereka memerlukan asumsi khusus tentang urutan input untuk disorting. Beberapa algoritma yang dapat mengurutkan n angka dalam waktu O (n lg n), semisal Merge sort dan heapsort mencapai batas atas atau upper bound dalam kasus terburuk, quicksort mencapainya dengan rata-rata. Selain itu, pada masing-masing algoritma ini, kita dapat menghasilkan urutan n nomor input yang menyebabkan algoritma berjalan dalam n log n/waktu.

Namun kita pun juga tahu bahwa pengurutan berbasis perbandingan terbaik adalah (n lg n) dan tidak sulit untuk mengetahui bahwa algoritma sorting linear time menggunakan operasi selain perbandingan untuk menentukan urutan yang diurutkan. Linear time mempunyai kompleksitas waktu terbaik dalam situasi di mana algoritma harus secara berurutan membaca seluruh masukannya, sehingga begitu banyaknya penelitian telah diinvestasikan untuk menemukan algoritma yang menunjukkan waktu linier atau, setidaknya, waktu hampir linier.

Meskipun begitu, linear time ini biasanya tidak terlalu diinginkan dari sudut pandang praktis disebabkan efisiensi algoritma linear-time bergantung pada key random yang diurut sehingga ketika kondisinya tak dipenuhi membuat hasilnya menjadi menurunnya kinerja. Kemudian alasan lainnya karena algoritma ini membutuhkan ruang ekstra yang proporsional dengan ukuran array yang sedang disortir, jadi jika kita berurusan dengan file besar, array tambahan menjadi keharusan

Oke sekarang yang akan kita bahas nantinya adalah algoritma Sorting ini bisa berjalan dalam linear time atau waktu linear diantaranya counting sort, radix sort dan bucket sort. Counting sort dan radix sort mengasumsikan bahwa input terdiri dari bilangan bulat dalam rentang kecil. Sedangkan, semacam bucket mengasumsikan bahwa input dihasilkan oleh proses acak yang mendistribusikan elemen secara seragam selama interval.

Kesemuaan algoritma pada linear time berbagi properti yang menarik seperti urutan yang diurutkan mereka tentukan hanya didasarkan pada perbandingan antar elemen masukan. Maka nantinya anda akan tahu bahwa comparison sort atau perbanding urutan mesti menggunakan perbandingan n log n untuk kasus terburuk dalam mengurutkan n elemen. Juga anda bisa temukan bahwa algoritma ini menggunakan operasi lain selain perbandingan untuk menentukan urutan sorting akibatnya batas bawah n log n tidak berlaku bagi mereka.

Kita mulai dari counting sort, ini merupakan teknik penyortiran stabil untuk mengurutkan objek menurut kunci yang jumlahnya kecil, yang idenya diambil dengan mengurutkan bilangan bulat hanya dengan memindahkan setiap bilangan bulat ke dalam posisinya yang benar dalam susunan bantu, dimana penghitungan posisi yang benar dilakukan dengan cara menghitung (counting) elemen-elemen dengan nilai lebih kecil atau sama dengan elemen tersebut.

Sederhananya jika terdapat 9 elemen yang lebih kecil daripada x, maka x akan mendapatkan posisinya di posisi 10. Algoritma ini mesti melakukan sedikit modifikasi sehingga dapat menangani kasus di mana terdapat elemen elemen lain yang nilainya sama dengan x karena tidak mungkin menempatkan semua elemen yang nilainya sama dengan x di posisi yang sama. Teknik penyortiran ini efektif ketika perbedaan antara kunci yang berbeda tidak begitu besar, jika tidak, itu dapat meningkatkan kompleksitas ruang

Kompleksitas counting sort

     Kompleksitas Waktu: O (n + r)
     Kompleksitas Ruang: O (n + r)

Keungggulan Algoritma ini bisa mengurutkan dengan waktu yang lebih singkat sebab tidak membandingkan dengan elemen lain atau Non comparison sorts namun kelemahannya menggunakan array yang terlalu banyak Tergantung pada asumsi kunci: angka yang akan diurutkan adalah bilangan bulat dalam {0, 1, …,n)

Untuk lebih paham anda bisa lihat contoh sederhana berikut: Ada Input data seperti ini: 2, 5, 3, 0, 2, 3, 0, 3

A:

box1

Ambil hitungan hitungan untuk menyimpan hitungan setiap objek unik. Misal 0 berjumlah 2, 1 jumlahnya 0, dst

B:

box2

Hitung jumlah modifikasinya yang sudah menyimpan hitungan setiap objek unik. Misal 2+0 = 2, 2+2=4, 4+3=7, dst

box3

C: menyediakan penyimpanan kerja sementara.

box4

Ingat nilai 5 lebih besar dari 3 maka ditempatkan paling belakang, dan nilai terkecil didepan 5 adalah 3, maka 3 kita eksekusi terlebih dahulu, sehingga pada kotak nilai berubah dari 7 ke 6

D:

box5

E:

box6

F:

box7

Diatas sudah menggambarkan Operasi COUNTING-SORT pada array input a[1…8] di mana setiap elemen dari A adalah bilangan bulat non-negatif tidak lebih besar dari k = 5

Metode Counting sort dapat disimpulkan lebih baik dari metode lower bound atau batas bawah (n log n) karena itu bukan semacam pembanding. Bahkan, tidak ada perbandingan antara elemen input terjadi di mana saja dalam kode. Sebaliknya, Counting sort menggunakan nilai sebenarnya dari elemen untuk mengindeks ke dalam sebuah array. (n log n) batas bawah untuk menyortir tidak berlaku ketika kita berangkat dari model semacam pembanding

Properti penting dari Counting sort adalah stabil dimana angka dengan nilai yang sama muncul dalam array output dalam urutan yang sama seperti yang mereka lakukan dalam array input. Sehingga terjadi proses memutuskan hubungan antara dua angka dengan aturan bahwa nomor mana saja yang muncul pertama kali dalam array input akan muncul pertama kali dalam array ouput.

algorithm counting_sort (A,k)

Input  : A : array [1..n] of integer, k: max (A)
Output : B : array [1..n] of integer
      for i = 1 to k do
          C[i] = 0  
      for j = 1 to length(A) do
          C[A[j]] = C[A[j]] + 1
      for 2 = 1 to k do
          C[i] = C[i] + C[i-1]
      for j = 1 to length(A) do
          B[C[A[j]]] = A[j]
          C[A[j]] = C[A[j]] - 1
      return B

Biasanya, properti stabilitas hanya penting ketika data satelit dibawa berkeliling dengan elemen yang sedang disortir. Counting sort’s stability itu penting untuk alasan lain dimana counting sort ini sering digunakan sebagai subrutin dalam bentuk radix. Seperti yang akan kita bahas pada materi berikutnya, agar radix dapat bekerja dengan benar, counting sort harus stabil.