Pada saat kita membuat sebuah program sering kali kita menghadapi permasalahan yang memerlukan pengrutan suatu nilai baik secara langsung atau pun tidak. Misalnya kita melakukan mencari sebuah nilai pada suatu list, permasalahan akan lebih mudah diselesaikan jika kita mengurutkan terlebih dahulu list tersebut dari kecil ke besar, kita tinggal melakukan pencarian nilai tersebut selama nilai tersebut lebih kecil atau sama dengan nilai yang ditelusuri pada list. Jika nilai dari dalam list sudah lebih besar dari nilai yang kita cari berarti sudah pasti nilai yang dicari tersebut tidak ada. Ini jauh lebih efektif dibandingkan mengecek semua nilai pada list tersebut dari awal sampai akhir jika nilai itu tidak ada, ini sangat tidak efektif/ bayangkan jika kita harus mencari satu nilai dalam data yang jumlahnya mencapai jutaan atau milyaran.

Sadar atau tidak manusia sering melakukan pengurutan dengan teknik-teknik tertentu dalam kehidupan sehari-hari. Misalnya saat kita bermain kartu remi, kita akan mengambil kartu tersebut dan mengurutkannya dengan cara-cara tertentu. Bila kita mengambil kartu tersebut satu-per-satu dari tumpukannya dan setiap mengambil kita langsung mengurutkannya dalam algoritma pengurutan, cara tersebut adalah implementasi dari insertion sort. Namun bila kartu dibagikan semuanya terlebih dahulu kemudian baru kita kelompokan menurut jenisnya. Kemudian barulah kita urutkan dari paling kecil ke paling besar maka itulah yang disebut selection sort.

Pengolahan data tidak dapat dilepaskan begitu saja dari kehidupan kita sehari-hari dan komputer pada umumnya digunakan untuk mengolah data.pengolahan data adalah pengolahan terhadap elemen-elemen data atau kombinasinya untuk membuat data itu berguna.hasil dari pengolahan data adalah sebuah bentuk yang berarti bagi penerimanya dan bermanfaat dalam pengambilan keputusan saat ini dan mendatang atau disebut dengan informasi.Oleh karena proses pengumpulan dan pengolahan data sangat penting dilakukan karena kemudahan dan kecepatan mendapatkan informasi merupakan suatu keinginan bagi penerima atau membutuhkannya

Pengurutan adalah satu hal yang sangat penting dalam dunia keinformatikaan.Terutama dalam pengolahan data . Sering kali, dengan pengurutan,proses pengolahan data dapat dilakukan dengan mudah lebih efesien.

Ada berbagai macam algoritma pengurutan.Namun hanya beberapa yang dipakai sebagai “pengenalan” terhadap siswa-siswa disuatu institusi.Di antaranya adalah Selection Sort dan Inserction Sort.Kedua algoritma pengurutan ini yabf menjadi fokus pembahasan dimakalah ini.

1.2 Perumusan Masalah

Dalam menyusun makalah ini, penulis merumuskan beberapa masalah berkaitan dengan :

1. Definisi Selection Sort

2. Simulasi Selection Sort

3. Notasi Algoritmik Selection sort

4. Kompleksitas Selection Sort

5. Stabilitas Selection Sort

6. Kekurangan dan kelebihan Selection Sort

7. Contoh Kasus Selection Sort

8. Definisi Insertion Sort

9. Simulasi Insertion Sort

10. Notasi Algoritmik Insertion Sort

11. Komplesitas Insertion Sort

12. Kelebihan dan Kekurangan Insertion sort

13. Contoh Kasus Insertion Sort

BAB II

PEMBAHASAN

2.1 SELECTION SORT

2.1.1 Pengertian Selection Sort

Algoritma Pengurutan sederhana salah satunya adalah Selection Sort.Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data.Untuk sorting ascending(menaik),elemen yan paling kecil diantara 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.Sebaiknya,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 :

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

2) Menukarkan nilai ini dengan elemen pertama list.

3) Mengulangi langkah diatas 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,

2.1.2 Simulasi 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.

Berikut ini adalah contoh program penggunaan Selection Short menggunakan aplikasi codeblock dan minGW dalam bahasa C++ :

#include <iostream>

void inputjumlah();

void selection();

void swap();

void output();

using namespace std;

int array[30],a,b,c,d,e,x;

void inputjumlah()

{

cout<<"Masukkan Jumlah Bilangan yang akan diurutkan : ";cin>>a;

cout<<endl;

for (b=0;b<a;b++)

{

cout<<"Data ke -"<<b+1<<" :";

cin>>array[b];

}

void swap()

{

int swapped;

swapped=c;

c=d;

d=swapped;

}

void output()

{

for (b=0;b<a;b++)

{

cout<<array[b]<<" ";

}

void selection ()

{

for(b=0;b<a;b++)

{

int max=-999;

int indexmax=-1;

for(e=b;e<a;e++)

{

if(array[e]>max)

{

max=array[e];

indexmax=e;

}

swap(array[b], array[indexmax]);

}

int main()

{

cout<<"Menggunakan Selection Sort"<<endl;

cout<<"=========================="<<endl;

inputjumlah();

selection();

swap();

output();

cout<<endl;

cout<<"===========end============"<<endl;

}

Setelah di RUN :

2.1.3 Notasi Algoritmik Selection Sort

Procedure : SelectionSort (data : array[1..100] of integer; input n:integer)
{ Mengurutkan data [1..100] dengan algoritma Selection Sort.}
Kamus : i, j, temp, min : integer
Algoritma :    for i= 1 to n-1 do {notasi for}
      min ← i
      for j = i+1 to n do
     if data[min] > data[j] then
     temp ← data[j]
    endif
    endfor
    temp ← data[i]
    data[i] ← data[j]
    data[j] ← temp
     end for

2.1.4 Kompleksitas Selection Sort

Kompleksitas Selection Sort Algoritma di dalam Selection Sort terdiri dari kalang bersarang. Dimana kalang tingkat pertama (disebut pass) berlangsung N-1 kali. Di dalam kalang kedua, dicari elemen dengan nilai terkecil. Jika didapat, indeks yang didapat ditimpakan ke variabel min. Lalu dilakukan proses penukaran Begitu seterusnya untuk setiap Pass. Pass sendiri makin berkurang hingga nilainya menjadi semakin kecil.

Pengurutan model ini tergolong buruk dan lebih baik dihindari penggunaanya, terutama untuk penanganan tabel lebih dari 1000 elemen . Karena masih ada algoritma lain yang implementasikannya sama mudahnya, namun performansinya jauh lebih baik.

2.1.5 Stabilitas Selection Sort

Stabilitas Selection Sort Selection Sort ini pada dasarnya merupakan algoritma sorting yang tidak stabil, namun dapat diubah menjadi stabil pada kasus tertentu
Algoritma sorting yang stabil akan mampu memanfaatkan relatifitas antar record melalui definisi di tiap-tiap keys yang dimiliki oleh record tersebut. Misalkan ada dua record R dan S dengan key yang sama dan dengan ketentuan R muncul sebelum S, maka pada hasil output akan muncul R sebelum S.
Namun ketika terdapat elemen yang sama (tidak dapat dibedakan) pada umumnya terdapat pada tipe data integer,stabilitas akan kembali di utamakan.

Misalkan terdapat pasangan data berikut yang akan diurutkan berdasarkan komponen peertamanya :

(4,1) (3,7 ) (3,1) (5,6)

Pada kasus ini ,akan menghasilkan dua output yang berbeda,dimana salah satunya akan memperhatikan key dari data dalam pengurutan dan solusi yang lain tidak.

(3,7) (3,1) (4,1) (5,6) ( order mainted/stable)

Atau

(3,1) (3,7) (4,1) (5,6) (order changed/unstable)

Algoritma sorting yang tidak stabil akan mengubah keterhubungan

antar record berdasarkan key yang dimiliki ,namun algoritma stabil akan mengabaikan key tersebut.Bagaimanapun juga algoritma yang stabil tetap bisa diubah menjadi tidak stabil dengan membandingkan key yang dimiliki tiap-tiap recordnya.

2.1.6 Kekurangan dan Kelebihan Selection Sort

I. Kekurangan Selection Sort

1. Membutuhkan method tambahan.

2. Sulit untuk membagi masalah.

II. Kelebihan Selection Sort

1. Algoritma ini sangat rapat dan mudah untuk diimplementasikan.

2. Operasi pertukarannya hanya dilakukan sekali saja.

3. Waktu pengurutan dapat lebih ditekan.

4. Mudah menggabungkannya kembali.

5. Kompleksitas selection sort relatif lebih kecil.

2.1.7 Contoh Kasus Selection Sort

Berikut contoh program pengurutan nilai IPK pada data mahasiswa

uses crt;
type mhs= record
     Nama, NIM: string;
     IPK : real;
end;
var Data : array [1..100] of mhs;
    i, j, n, temp : integer;
    pilih : char;

procedure input;
begin
clrscr;
write('Masukkan jumlah mahasiswa : ');
readln(n);
for i := 1 to n do
begin
writeln(' ___________________________________');
writeln('|        Data Mahasiswa Ke-',i,'        |');
writeln('|-----------------------------------|');
writeln('| Nama    :                         |');
writeln('| NIM     :                         |');
writeln('| IPK     :                         |');
writeln('|___________________________________|');
gotoxy(13,5+(7*(i-1)));readln(Data[i].Nama);
gotoxy(13,6+(7*(i-1)));readln(Data[i].NIM);
gotoxy(13,7+(7*(i-1)));readln(Data[i].IPK);
writeln;
end;
end;

Procedure Table;
Begin
writeln('|    |                          |           |           |');
writeln('|____|__________________________|___________|___________|');
end;

procedure Tampil;
begin
clrscr;
writeln(' _______________________________________________________');
writeln('|                                                       |');
writeln('|                 DATA NILAI MAHASISWA                  |');
writeln('|_______________________________________________________|');
writeln('|    |                          |           |           |');
writeln('| No |         Nama             |    NIM    |    IPK    |');
writeln('|____|__________________________|___________|___________|');
for i:=1 to n do
begin
gotoxy(1,7+i);Table;
gotoxy(3,7+i);writeln(i);
gotoxy(8,7+i);writeln(Data[i].Nama);
gotoxy(35,7+i);writeln(Data[i].NIM);
gotoxy(50,7+i);writeln(Data[i].IPK:2:0);
end;
readkey;
end;

procedure Selection;
var max: integer;
temp: mhs;
begin
for i:=1 to n-1 do
begin
   max:=i;
   for j:= i+1 to n do
    if Data[j].IPK< Data[max].IPK then
    max:=j;
    temp:= Data[max];
    Data[max]:= Data[i];
Data[i]:= temp;
end;
Tampil;
end;

begin
input;
Selection;
end.

2.2 INSERTION SORT

2.2.1 Pengertian Insertion Sort

Algoritma insertion sort adalah sebuah algoritma sederhana yang cukup efesien untuk mengurutkan sebuah list yang hampir terurut.Algoritma ini juga bisa digunakan sebagai bagian dari algoritma yang lebih canggih . Cara kerja algoritma ini adalah dengan mengamnil elemen list satu per satu dan dimasukkannya diposisi yang benar seperti namanya.Pada array, list yang baru dan elemen sisanya dapat berbagi tempat di array, meskipun cukup rumit. Untuk menghemat memori, implementasinya menggunakan pengurutan di tempat yang membandingkan elemen saat itu dengan elemen sebelumnya yang sudah diurut, lalu menukarnya terus sampai posisinya tepat.

Hal ini terus dilakukan sampai tidak ada elemen tersisa di input. Salah satu implementasinya pada kehidupan sehari-hari adalah saat kita mengurutkan kartu remi. Kita ambil kartu satuper-satu lalu membandingkan dengan kartu sebelumnya untuk mencari posisi yang tepat.

Variasi pada umumnya dilakukan terhadap array pada insertion sort adalah sebagai berikut :

1. Elemen awal di masukkan sembarang, lalu elemen berikutnya dimasukkan di bagian paling akhir.

2. Elemen tersebut dibandingkan dengan elemen ke (x-1). Bila belum terurut posisi elemen sebelumnya digeser sekali ke kanan terus sampai elemen yang sedang diproses menemukan posisi yang tepat atau sampai elemen pertama.

3. Setiap pergeseran akan mengganti nilai elemen berikutnya, namun hal ini tidak menjadi persoalan sebab elemen berikutnya sudah diproses lebih dahulu.

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

}

2.2.3 Notasi Algoritmik Insertion Sort

Procedur insertion sort

(input/output T:TabInt,Input N:integer)

{mengurut tabel integer [1..N] dengan insertion sort secara ascending)

Kamus : i,pass,Temp:integer

Algoritma:

Pass traversal [2..N]

Temp ß Tpass

I ßpass -1

White(j>1) and (T1>temp) do

T1+1ßTi

Ißi-1

Depend on (t,i,temp)

Temp>ti:t1+1ßtemp

Temp<ti :ti+1ßTi

Tißtemp

{T[1..pass-1]terurut}

2.2.4 Kompleksitas Insertion Sort

Algoritma insertion sort juga terdiri dari 2 kalang bersarang.Dimana terjadi N-1 pass (dengan N adalah banyak emen dtruktur data),dengan masing-masing pass terjadi i kali operasi perbandingan.i tersebut bernilai 1 untuk pass pertama ,bernilai 2 untuk pass kedua.begitu seterusnya hingga pass ke N-1.

Secara Kompleksitas,Selection sort dan insertion sort mempunyai Big-Oh yang sama.Walaupun begitu,insertion sort sebenarnya lebih mangkus.

Berdasarkan gambar,insertion sort 40% lebih cepat daripada selection sort. Namun,Insertion sort mempunyai kekurangan.Insertion sort lebih baik tidak digunakan untuk menangani struktur data dengan lebih dari 2000 elemen.

2.2.5 Kekurangan dan Kelebihan Insertion Sort

Kelebihan:

1. Sederhana dalam penerapannya.

2. Mangkus dalam data yang kecil.

3. Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat dibandingkan dengan Quicksort.

4. Mangkus dalam data yang sebagian sudah terurut.

5. Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang sedikit.

Kekurangan:

1. Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.

2. Untuk larik yang jumlahnya besar ini tidak praktis.

3. Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.

2.2.6 Contoh Kasus Insertion Sort

            #include <stdio.h>

int main()
{
int n, array[1000], c, d, t;

printf("Enter number of elements\n");
scanf("%d", &n);

printf("Enter %d integers\n", n);

for (c = 0; c < n; c++) {
    scanf("%d", &array[c]);
}

for (c = 1 ; c <= n - 1; c++) {
    d = c;

    while ( d > 0 && array[d] < array[d-1]) {
      t          = array[d];
      array[d]   = array[d-1];
      array[d-1] = t;

      d--;
    }
}

printf("Sorted list in ascending order:\n");

for (c = 0; c <= n - 1; c++) {
    printf("%d\n", array[c]);
}

return 0;
}

#include <iostream.h>
    #include <conio.h>
    main()
    {
        int i,j,n,data[10],simpan,min,posisi;
       cout<<"masukkan banyak data= ";cin>>n;
       for(i=1;i<=n;i++)
       {
        cout<<"data "<<i<<" = ";cin>>data[i];
       }
       for(i=1;i<n;i++)
       {
        for(j=i+1;j<=n;j++)
          {
                if(data[i]>data[j])
             {
                simpan=data[i];
                data[i]=data[j];
                data[j]=simpan;
             }
          }
       }
       cout<<"hasil= ";
       for(i=1;i<=n;i++)
        cout<<data[i]<<" ";

    getch();
    }

BAB III

PENUTUP

3.1 Kesimpulan

Algoritma pengurutan Mempunyai berbagai macam jenis. Tiap- tiap algoritma pengurutan mempunyai kekurangan dan kelebihannya sendiri.

Pada makalah ini telah dinahas algoritma selection sort dan insertion sort.Khusunya untuk selection sort dapat disimpulkan bahwa :

a. Kompleksitas selection sort relatif lebih kecil

b. Tidak ada best case dan worst case

c. Pada dasarnya selection sort merupakan algoritma yang tidak stabil.

Untuk Insertion sort,mempunyai beberapa keuntungan :

a. implementasi yang sederhana

b. merupakan online algorithmic

c. stabil

Intinya jadi Selection sort dan Insertion sort merupakan metode pengurutan yang palingsederhana.

Suarakan Ilmu Dan Bagikan

Cari Blog Ini

Tutorial Cryptohero Lengkap Bahasa Indonesia | Cryptocurrency Indonesia

ALGORITMA DAN PEMROGRAMAN INSERT & SELECTION

BAB I

PENDAHULUAN

1.1 Latar Belakang