Sorting (selection sort dan insertion sort )

Sorting

       Sorting merupakan suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen. Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:

1. Urut naik (ascending)
   Mengurutkan dari data yang mempunyai nilai paling kecil sampai paling besar

2. Urut turun (descending)

   Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.

Mengapa harus melakukan sorting data? Ada banyak alasan dan keuntungan dengan mengurutkan data. Data yang terurut mudah untuk dicari, mudah untuk diperiksa, dan mudah untuk dibetulkan jika terdapat kesalahan. Data yang terurut dengan baik juga mudah untuk dihapus jika sewaktu-waktu data tersebut tidak diperlukan lagi. Selain itu, dengan mengurutkan data maka kita semakin mudah untuk menyisipkan data atapun melakukan penggabungan data.

Metode-metode sorting meliputi:

1. Insertion Sort (Metode Penyisipan)
2. Selection Sort (Metode Seleksi)

 

Insertion Sort 

 

Insertion Sort merupakan algoritma yang efisien untuk mengurutkan angka yang mempunyai jumlah elemen sedikit. Dimana:- Input : deretan angka sejumlah n buah
- Output : permutasi (pengurutan) sejumlah n angka dari input yang sudah terurut secara ascending maupun descending  Metode penyisipan (Insertion sort) bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan.Metode ini mengurutkan bilangan-bilangan yang telah dibaca; dan berikutnya secaraberulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut.
Insertion Sort bekerja seperti banyak orang yang sedang mengurutkan kartu di tangan. Dimulai dengan tangan kiri yang kosong dan kartunya tertumpuk di meja. Selanjutnya kita ambil satu persatu kartu di meja dan diletakkan di tangan kiri dengan posisi yang benar (terurut). Untuk menemukan posisi yang banar, maka kita harus membandingkan satu persatu kartu yang ada (di tangan kiri) secara berurutan.

Contoh Insertion Sort :

Bagian biru/abu-abu (dua bilangan pertama) sekarang dalam keadaan terurut secara relatif.

Berikutnya, kita perlu menyisipkan bilangan ketiga (4) ke dalam bagian biru/abu-abu sehingga
setelah penyisipan tersebut, bagian biru/abu-abu tetap dalam keadaan terurut secara relatif;
CARANYA :
pertama : Ambil bilangan ketiga (4).

• Kedua : Geser bilangan kedua (10) shg ada ruang untuk disisipi.

• Ketiga : Sisipkan bilangan 4 ke posisi yang tepat

• Sekarang, tiga bilangan pertama sudah terurut secara relatif dan kita sisipkan bilangan keempat kepada tiga bilangan pertama tsb.  Setelah penyisipan, empat bilangan pertama haruslah dalam keadaan terurut secara relatif.

•  Ulangi proses tsb sampai bilangan terakhir disisipkan

•  Proses Sorting Selesai

Berikut adalah Contoh Program C++nya :

#include <iostream>

#include <conio.h>

using namespace std ;

int data[10],data2[10];

int n;

void tukar(int a, int b)

{

 int t;

 t = data[b];

 data[b] = data[a];

 data[a] = t;

}

void insertion_sort()

{

 int temp,i,j;

 for(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;

 }

}

int main()

{

 cout<<"\t\t\t===PROGRAM INSERTION SORT===\n\n"<<endl;

 //Input Data

 cout<<"Masukkan Jumlah Data : ";

 cin>>n;

 cout<<"\n";

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

 {

  cout<<"Masukkan data ke "<<i<<" : ";

  cin>>data[i];

  data2[i]=data[i];

 }

 insertion_sort();

 cout<<"\n\n";

 //tampilkan data

 cout<<"Data Setelah di Sort : ";

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

 {

  cout<<" "<<data[i];

 }

 cout<<"\n\nSorting Selesai";

 getch();

}

Berikut Adalah Hasilnya :

 

 

 

 

 

 

 

 

 

 

 

Selection Sort

 

Pengertian dari selection sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan,
Selection Sort Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang
maka dicatat posisinya dan kemudian ditukar.
Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter.Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun) Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.

 Contoh Selection Sort :



Selection Sort Secara Ascending :

• Cek seluruh elemen array, temukan nilai terkecil (1) dan tukarkan posisinya dengan posisi nilai yang tersimpan pada posisi pertama dari array (3)

• Temukan nilai terkecil kedua (2), dan tukarkan posisinya dengan nilai yang berada pada posisi kedua (10).

• Dua elemen biru pertama tidak akan berubah lagi sebab mereka sudah merupakan nilai terkecil pertama dan kedua dalam array tsb.

Sekarang, ulangi dengan cara/proses “pilih tukar” 

Pengurutan Selesai. 

Berikut adalah contoh Program C++nya :

#include <iostream>
#include <conio.h>

int main(void)
{
int array[5]; // An array of integers.
int length = 5; // Lenght of the array.
int i, j;
int firstelement, temp;

//Some input
for (i = 0; i < length; i++)
{
cout << "Enter a number: ";
cin >> array[i];
}

//Algorithm
for (i= length - 1; i > 0; i--)
{
firstelement = 0;
for (j=1; j<=i; j++)
{
if (array[j] < array[firstelement])
firstelement = j;
}
temp = array[firstelement];
array[firstelement] = array[i];
array[i] = temp;
}

//Some output
for (i = 0; i < 5; i++)
{
cout << array[i] << endl;
}
getch();
}

• Program Setelah dieksekusi :