Rangkuman Materi Sorting

Sorting

Sorting atau pengurutan adalah proses menyusun elemen – elemen dari masukan awal acak menjadi keluaran akhir tertata dengan urutan tertentu. Proses tersebut diimplementasikan dalam bermacam aplikasi. Contoh penerapannya antara lain berupa rincian transaksi sesuai urutan tanggal dan jam pada perbankan, daftar hadir yang diurutkan berdasarkan nomor induk dan daftar pustaka yang diurutkan sesuai abjad pengarang ataupun katalog buku di perpustakaan. Fungsi-fungsi statistik seperti median dan pembuatan kuartil data (quarter), desil dan percentil (percentile) mensyaratkan data untuk diurutkan terlebih dahulu. Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna. Selain menjadi suatu 2 aplikasi yang berdiri sendiri, pengurutan juga biasanya menjadi suatu bagian dari algoritma  yang lebih besar.

Insertion Sort

       Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Insertion Sort disebut-sebut sebagai metode pertengahan. Artinya, metode ini memiliki kecepatan ratarata antara metode primitif (bubble dan selection) dan modern (merge dan quick) . Metode ini, didasarkan pada sebuah kunci yang diambil pada elemen ke-2 pada sebuah larik, lalu menyisipkan elemen tersebut jika kondisi percabangan terpenuhi. Metode penyisipan (insertion) bertujuan untuk menjadikan bagian sisi kiri larik terurutkan sampai dengan seluruh larik berhasil diurutkan. 

Pseudocode untuk algoritma insertion sort adalah sebagai berikut: 

                   insertionsort(data[],n) 

                  for(i = 1; i < n; i++)

                  pindahkan seluruh elemen data[j] yang lebih besar daripada data[i] sebanyak satu posisi; 

                  geser data[ i ] pada posisi yang tepat;

Sintaks program fungsi Insertion Sort
void insertion_sort()
{
int temp;
for(int i=1;i<n;i++)
   {
temp = data[i];
j = i -1;
while(data[j]>temp && j>=0)
      {
data[j+1] = data[j];
  j--;
}
data[j+1] = temp;
}
}

Selection Sort

SELECTION SORT Merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. 

Sintaks program fungsi Selection Sort
void selection_sort()
{
for(int i=0;i<n-1;i++)
   {
pos = i;
for(int j=i+1;j<n;j++)
      {
if(data[j] < data[pos])
pos = j; //ascending
}
   if(pos != i) tukar(pos,i);
}
}


Daftar Pustaka
ANALISIS ALGORITMA INSERTION SORT DAN IMPLEMENTASINYA DALAM BAHASA PEMROGRAMAN C++
BAB 2 SORTING (PENGURUTAN)