PENJELASAN TENTANG SORTING (SELECTION SORT DAN INSERTION SORT

METODE SORTING

Seringkali perancang program perlu mengurutkan sekumpulan data yang dimiliki untuk memudahkan pemrosesan selanjutnya terhadap data tersebut. Pengurutan adalah sebuah algoritma dasar yang sering diperlukan dalam pembuatan program. Berbagai algoritma pengurutan telah diciptakan dan dapat digunakan. Pemahaman tentang beberapa algoritma pengurutan dasar perlu diketahui, termasuk cara penggunaannya dalam program.

PENGERTIAN SORT

Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan data. Sortdalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urut menaik (ascending) dari nilai terkecil sampai dengan nilai terbesar, atau urut menurun (descending) dari nilai terbesar sampai dengan nilai terkecil. Sorting adalah proses pengurutan.

Terdapat dua macam pengurutan:

• Pengurutan internal (internal sort), yaitu pengurutan terhadap sekumpulan data yang disimpan dalam media   internal komputer yang dapat diakses setiap elemennya secara langsung. Dapat dikatakan sebagai   pengurutan tabel
• Pengurutan eksternal (external sort), yaitu pengurutan data yang disimpan dalam memori sekunder, biasanya data   bervolume besar sehingga tidak mampu untuk dimuat semuanya dalam memori.

SELECTION SORT

                   Algoritma Selection sort memilih elemen maksimum/minimum array, lalu menempatkan elemen maksimum/minimum itu pada awal atau akhir array (tergantung pada urutannya ascending/descending). Selanjutnya elemen tersebut tidak disertakan pada proses selanjutnya. Karena setiap kali selection sort harus membandingkan elemen-elemen data, algoritma ini termasuk dalam comparison-based sorting.

Seperti pada algoritma Bubble Sort, proses memilih nilai maksimum /minimum dilakukan pada setiap pass. Jika array berukuran N, maka jumlah pass adalah N-1.

Selection Sort (Metode Seleksi) 

• One of the simplest sorting algorithms
• Merupakan kombinasi antara sorting dan searching
• Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil (Ascending) atau terbesar (Descending) 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])/ data pertama, pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1])/ data kedua atau selanjutnya.
• Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. 

Contoh Selection Sort :

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 dan tukar” 

• Pengurutan Selesai.

Contoh Program Selection Sort menggunakan bahasa pemrograman C++
berikut kode programnya :

#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 :

INSERTION SORT

                Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort.

                Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang “tepat” untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya yang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sortingdisebut sebagai “pass“), dengan indeks dimulai dari 0.

                Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.

Berikut adalah simulasi Algoritma Insertion Sort
Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.

Simulasi Insertion Sort

Dari gambaran proses pengurutan/ sorting  data di atas dapat diketahui  bagaimana data-data tersebut berpindah  posisi  dari satu index ke index lain dalam satu array.  Untuk detail proses pengurutan diatas, dapat disimak melalui detail simulasi berikut.

Data awal : 5, 2, 4, 6, 1, 3

Jumlah Index = 6   dimulai dari 0 s/d 5

Anggaplah index adalah ‘I’,

Untuk setiap proses pengurutan data, perbandingan data dimulai dari index kedua (dalam hal ini i=1)

Proses I:

i=1, x=1; j=0

x<j à2<5? — true  =2, 5, 4, 6, 1, 3

Proses II

i=2, j=1, x=2

x<j à  4<5 — true = 2, 4, 5, 6, 1, 3     j=j-1,      Jika benar    x=x-1

x<j à4<2 — false = 2, 4, 5, 6, 1, 3

Proses III

I=3, j=2, x=3

x<j à6<5 — false =  2, 4, 5, 6, 1, 3     j=j-1    jika sebuah proses bernilai false, maka proses tersebut tidak akan dilanjutkan, karena secara otomatis data yang ada disebelah kiri semuanya sudah terurut dengan benar.

Proses IV

i=4, j=3, x=4

x<j à1<6 — true = 2, 4, 5, 1, 6, 3   j=j-1,     jika benar  maka  x=x-1

x<j à 1<5 — true = 2, 4, 1, 5,6, 3  j=j-1 ,   jika benar  maka   x=x-1

x<j  à1<4  — true = 2, 1, 4, 5,6, 3  j=j-1,    jika benar  maka   x=x-1

x<j  à 1<2 — true =   1, 2, 4, 5,6, 3

Proses V

i=5, j=4, x=5

x<j à3<6  — true = 1, 2, 4, 5,3, 6  j=j-1, jika benar maka x=x-1

x<j à3<5 — true = 1, 2, 4, 3, 5, 6   j=j-1, jika benar maka x=x-1

x<j à3<4 — true = 1, 2, 3, 4, 5, 6  j=j-1, jika benar maka x=x-1

x<jà3<2 — false = 1, 2, 3, 4, 5, 6  j=j-1

Berikut adalah contoh program dari insertion sort

#include<iostream>

#include <conio.h>

int main()

{

int data[]={5, 2, 4, 6, 1, 3};

cout<<“sebelum disorting: “;

for(int i=0; i<6; i++)

cout<<data[i] <<“,  “;

cout<<endl <<endl;

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

{

int j=i;

while(data[j]<data[j-1])

{

int tmp=data[j];

data[j]=data[j-1];

data[j-1]=tmp;

j­­--;

}

}

cout<<“Setelah disorting: “;

for(int i=0; i<6; i++)

cout<<data[i] <<“,  “;

getch();

}

DAFTAR PUSTAKA:

https://thenurulazizah.wordpress.com/artikel-2/13-metode-sorting/

https://penamisterius.wordpress.com/2011/03/22/insertion-sort