Sorting (Selection Sort & Insertion Sort) STRUKTUR DATA

Selamat pagi kawan semua, disini saya akan memberikan materi tentang Sorting, untuk lebih lengkapnya check it out.. 

Pengertian Sorting

Dalam arti bahasa sorting adalah penyortiran atau memilih-milih. Pada struktur data Sorting adalah sebuahmetode untuk pengurutan data, misalnya dari data yang terbesar ke data yang terkecil. Dengan cara program yang dibuat harus dapat membandingkan antar data yang di inputkan.

Artinya jika ada deretan data, maka data yang pertama akan membandingkan dengan data yang kedua. Jika data yang pertama lebih besar dari pada data yang kedua maka data yang pertama akan bertukar posisi dengan data yang kedua, begitu seterusnya sampai benar-benar data terurut dari yang terbesar hingga yang terkecil.

Selection Sort

Selection Sort merupakan salah satu algoritma pengurutan yang sederhana. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending (menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian ditukar.

Selection Sort diakui karena kesederhanaan algoritmanya dan performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi tertentu. Algoritma ini bekerja sebagai berikut:

* Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list.

* Menukarkan nilai ini dengan elemen pertama list

* Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua

Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan.

Contoh pada C++:

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#include <iomanip.h>

main()

{

int x[5];

int i;

int temp;

int minindex;

int j;

clrscr();

cout<<" >> Welcome To The Program Selection Sort << \n" <<endl;

cout<<"masukkan nilai x :\n";

for(i=0; i<5; i++)

{

cout<<"x["<<i<<"] = ";cin>>x[i];

}

cout<<"\n data sebelum di sort :";

for(i=0; i<5;i++)

{

cout<<setw(4)<<x[i];

}

for(i=0; i<5-1; i++) //perulangan iterasi

{

minindex=i;

for(j=i+1; j<5; j++) //perulangan membandingkan data

{

if(x[minindex]>x[j])

{

minindex=j;

}

}

temp=x[i];

x[i]=x[minindex];

x[minindex]=temp;

}

cout<<"\n\nData setelah di sort :";

for(i=0; i<5; i++)

{

cout<<setw(4)<<x[i];

}

getch();

}

INSERTION SORT

Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. Inde algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.

Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingi mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.

1. Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. Dan anggaplah kita akan menyusun kartu ke tangan kiri kita.
2. Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
3. Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
4. Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang).

Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya, demikian juga halnya dalam pengurutan data.

Berikut contoh program pada C++:

#include <iostream>

#include <conio.h>

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

}

Sekian materi tentang Sorting dari saya semoga bermanfaat.

Referensi:
Buku Struktur Data (Algoritma & Struktur Data 2) dengan C, C++ Ed.5
www.slideshare.com