SELECTION SORT & INSERTION SORT

SORTING

Suatu proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi urut dan teratur menurut suatu aturan tertentu.

Pada umumnya ada 2 macam pengurutan :

1. Pengurutan secara ascending ( urutan naik)
2. Pengurutan secara descending (urutan turun)

Contoh :

Data Acak : 5 6 8 1 3 25 10

Ascending : 1 3 5 6 8 10 25

Descending : 25 10 8 6 5 3 1

Algoritma untuk melakukan Sorting :

1.    Selection Sort

2.    Insertion Sort

3.    BubbleSort

4.    Quick 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. Selama proses pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

PROSES SELECTION SORT

• Mencari data terkecil dari data pertama sampai dengan data yang terakhir. kemudian ditukar posisinya dengan data pertama.
• Mencari data terkecil dari data kedua sampai dengan data terakhir, kemudian ditukar posisinya dengan data kedua.
• Mencari data terkecil dari data ketiga sampai dengan data terakhir, kemudian ditukar posisinya dengan data ketiga.
• Begitu seterusnya sampai semua data terurut naik. Apabila terdapat n buah data yang akan diurutkan, maka membutuhkan (n-1) langkah pengurutan, dengan data terakhir, yaitu data ke n tidak perlu diurutkan karena hanya tinggal data satu-satunya.

Contoh:

Terdapat suatu variable array dimana nilai dalam array tersebut :

NILAI[8] = { 44, 55, 12, 42, 94, 18, 6, 67 }

PENYELESAIAN

Insertion Sort

Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan ke tempat yang seharusnya. Pengurutan dimulai dari data ke 2 sampai dengan data terakhir , jika ditemukan data yang lebih kecil, maka akan di tempatkan (diinsert) di posisiyang seharusnya. Pada penyisipan elemen maka elemen – elemen lain akan bergeser ke belakang.

PROSES INSERTION SORT

• Algoritma ini akan mudah anda kuasi jika sering bermain Game Remi, Domino, dll
• Ide algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu.
• Jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut

Contoh:

CONTOH PROGRAM SELECTION SHORT

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

}

HASIL

CONTOH PROGRAM INSERTION SHORT

#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===PROGRAMINSERTION 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();

}

HASIL

Referensi :Sorting, Menjelaskan tentang sorting dan algoritmanya keterangan , I KOMANG SETIA BUANA, S.Kom.,MT