Selection Sort Pada Bahasa Pemrograman C#

MAKALAH STRUKTUR DATA

SELECTION SORT

Dosen pengampu: Dr.MUHAMMAD FAISAL,S.Kom., M.T 

Oleh:

Ruri Nur Aini              NIM.12650022

Kelas                           A

JURUSAN TEKNIK INFORMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS ISLAM NEGERI MAULANA MALIK IBRAHIM

MALANG, 2015

A.      SEJARAH ALGORITMA

Ditinjau dari asal-usul katanya, kata Algoritma sendiri mempunyai sejarah yang aneh. Orang hanya menemukan kata algorism yang berarti proses menghitung dengan angka arab. Dikatakan algorist jika Anda menghitung menggunakan angka arab. Para ahli bahasa berusaha menemukan asal kata ini namun hasilnya kurang memuaskan. Akhirnya para ahli sejarah matematika menemukan asal kata tersebut yang berasal dari nama penulis buku arab yang terkenal yaitu Abu Ja’far Muhammad

Ibnu Musa Al-Khuwarizmi. Al-Khuwarizmi dibaca orang barat menjadi Algorism. Al-Khuwarizmi menulis buku yang berjudul Kitab Al Jabar Wal- Muqabala yang artinya “Buku pemugaran dan pengurangan” (The book of restoration and reduction). Dari judul buku itu kita juga memperoleh akar kata “Aljabar” (Algebra). Perubahan kata dari algorism menjadi algorithm muncul karena kata algorism sering dikelirukan dengan arithmetic, sehingga akhiran –sm berubah menjadi –thm. Karena perhitungan dengan angka Arab sudah menjadi hal yang biasa, maka lambat laun kata algorithm

berangsur-angsur dipakai sebagai metode perhitungan (komputasi) secara umum, sehingga kehilangan makna kata aslinya. Dalam bahasa Indonesia, kata algorithm diserap menjadi algoritma.

Abu Abdullah Ibnu Musa al-Khawarizmi (770M-840M) lahir di Khawarizm (Kheva), kota yang berada di selatan Sungai Oxus (sekarang disebut Uzbekistan) pada 770 M. Al Khawarizmi merupakan salah satu ilmuan terkenal di zamannya. Ada beberapa cabang ilmu matematika yang berhasil ditemukannya, antara lain yang dikenal sebagai astronom dan geografer.

Pada 1950, algoritma pertama kali digunakan pada Algoritma Eucliden (Euclid Algorithm). Euclid sendiri merupakan seorang matematikawan Yunani yang lahir sekitar 350 SM. Euclid menulis buku yang berjudul Element.

Di dalam buku tersebut, dijelaskan langkah-langkah untuk menemukan pembagi bersama terbesar (common greatest divisor) dari dua bilangan bulat, yakni m dan n. Namun, Eucliden pada saat itu tidak menyebutkan bahwa cara yang digunakannya adalah metode algoritma. Hal tersebut baru disebut sebagai algoritma pada abad-abad modern.

B.       DEFINISI DAN CIRI-CIRI ALGORITMA

Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dan logis. Kata logis merupakan kata kunci dalam algoritma. Langkah-langkah dalam algoritma harus logis dan harus dapat ditentukan bernilai salah atau benar. Dalam beberapa konteks, algoritma adalah spesifikasi urutan langkah untuk melakukan pekerjaan tertentu.

Lima ciri yang harus dipunyai algoritma agar menjadi algoritma yang benar adalah sebagai berikut.

1.      Algoritma harus berhenti setelah mengerjakan langkah terbatas. Dalam hal ini, jika langkah-langkah yang ada telah dipenuhi dan telah dieksekusi, algortima haruslah berhenti.

2.      Setiap langkah harus didefinisikan agar tidak memiliki arti dua (ambiguous).

3.      Algoritma mempunyai nol atau lebih masukan (input).

4.      Algoritma mempunyai nol atau lebih keluaran (output).

5.      Algoritma haruslah efektif, yakni mempunyai langkah yang sederhana agar dapat dikerjakan dengan waktu yang efektif.

C.      ALGORITMA SORTING

Sorting adalah sebuah proses merangkai benda dalam urutan tertentu dan/atau dalam himpunan yang berbeda, dan oleh karena itu dia memiliki dua arti umum yang berbeda:

1. pengurutan: merangkai benda yang sejenis, sekelas, dll, dalam urutan yang teratur.
2. kategorisasi: pengelompokan dan pemberian label kepada benda dengan sifat yang serupa.

Ada dua bentuk sorting yaitu secara ascending dan descending. Sorting secara ascending adalah cara mengurutkan data mulai data bernilai terkecil sampai terbesar. Sedangkan descending mengurutkan data mulai dari data terbesar sampai terkecil. Sebagai contoh misalkan diberikan data berupa bilangan berikut ini:

3 9 1 4 0 2

Hasil sorting ascending adalah 0 1 2 3 4 9, sedangkan hasil secara descending adalah 9 4 3 2 1 0.

Algoritma sorting terdiri dari beberapa algoritma seperti Bubble sort, Quick sort, Selection sort, Insertion sort, dan Merge sort yang di mana setiap jenis sorting ini memilki perbedaan satu sama lainnya. Berikut ini merupakan pembahasan umum mengenai jenis-jenis algoritma sorting yang telah dijelaskan di atas.

a.      Selection Sort

1.      Sejarah

Mr. Selection adalah seorang guru bahasa inggris. Tiga bulan sekali, dia membawa pulang kertas ujian untuk dievaluasi. Saat evaluasi selesai, kertas-kertas ujian tersebut disusun di mana nilai tertinggi di susunan pertama dan nilai terendah di susunan terakhir.  Dia memiliki kebiasaan membagi-bagikan kertas ujian tersebut kepada siswa-siswanya sambil memberikan pujian kepada siswa yang memilki nilai tertinggi dan memberikan teguran kepada siswa dengan nilai terendah.

Mr. Selection juga sering diberi tugas oleh ibunya untuk menyusun kertas-kertas ujian. Dia memutuskan untuk menyusun kertas-kertas tersebut dengan mengikuti strategi berikut:

1)      Menempatkan semua lembaran kertas secara bersebelahan.

2)      Mengamati dari kiri ke kanan untuk menemukan kertas siswa yang memperoleh nilai tertinggi.

3)      Mengambil kertas tersebut menempatkannya secara tertelungkup di meja lain.

4)      Mengamati kembali kertas-kertas yang tersisa dari kiri ke kanan dan menemukan kertas dengan nilai tertinggi berikutnya.

5)      Menempatkan kertas tersebut secara tertelungkup di atas kertas yang berada di meja lain.

Sepuluh tahun kemudian, ketika dia harus menulis sebuah program untuk mengurutkan nilai-nilai, dia teringat pada strategi yang pernah dia terapkan dalam penyusunan kertas ujian. Dia kemudian melakukan hal yang sama pada program tersebut dan algoritma tersebut diberi nama selection sort.

2.    Pengertian

Selection sort adalah metode pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot.

3.      Algoritma

Algoritma selection sort dapat dirangkum sebagai berikut:

Ø  Temukan nilai yang paling minimum di dalam struktur data. Jika ascending, maka yang harus ditemukan adalah nilai yang paling minimum. Jika descending, maka temukan nilai yang paling maksimum.

Ø  Tukar nilai tersebut dengan nilai pada posisi pertama di bagian struktur data yang belum diurutkan.

Ø  Ulangi langkah di atas untuk bagian struktur data yang tersisa.

Contoh:

D.      APLIKASI ALGORTIMA SORT

Algoritma sort banyak digunakan pada berbagai aplikasi. Berikut adalah beberapa aplikasi algoritma sort.

• Komersial komputasi organisasi Pemerintah, lembaga keuangan, dan perusahaan komersial mengatur banyak informasi dengan penyortiran. Dari informasi itu account akan diurutkan berdasarkan nama atau nomor, transaksi yang akan diurutkan berdasarkan waktu atau tempat, mail yang akan diurutkan berdasarkan kode pos atau alamat, file yang akan diurutkan berdasarkan nama atau tanggal, atau apa pun, mengolah data tersebut pasti melibatkan algoritma sorting.
• Mencari informasi. Memungkinkan untuk melakukan pencarian yang lebih efisien dengan menggunakan algoritma pencarian biner klasik.
• Riset operasi. Misalkan kita memiliki N pekerjaan untuk menyelesaikan, dimana j pekerjaan membutuhkan t detik _j pengolahan waktu. Kita harus menyelesaikan semua pekerjaan, tapi ingin memaksimalkan kepuasan pelanggan dengan meminimalkan waktu penyelesaian rata-rata dari pekerjaan. Pengolahan waktu terpendek aturan pertama, di mana kita menjadwalkan pekerjaan untuk meningkatkan waktu pemrosesan. Sebagai contoh lain, mempertimbangkan masalah load-balancing, di mana kita memiliki prosesor M identik dan pekerjaan N untuk menyelesaikan, dan tujuan kami adalah untuk menjadwalkan semua pekerjaan pada prosesor sehingga waktu ketika pekerjaan terakhir selesai adalah sedini mungkin . Masalah khusus ini adalah NP-keras jadi kita jangan berharap untuk menemukan cara praktis untuk menghitung jadwal yang optimal. Salah satu metode yang dikenal untuk menghasilkan jadwal yang baik adalah pengolahan aturan waktu terpanjang, di mana kita mempertimbangkan pekerjaan dalam urutan penurunan waktu proses, menetapkan setiap pekerjaan untuk prosesor yang tersedia pertama.
• Event simulasi. Banyak aplikasi ilmiah melibatkan simulasi, di mana titik perhitungan adalah model dari beberapa aspek dari dunia nyata agar dapat lebih dipahami. Melakukan simulasi tersebut dapat secara efisien memerlukan algoritma yang tepat dan struktur data.
• Simulasi numerik. Komputasi ilmiah ini sering berhubungan dengan akurasi (seberapa dekat kita pada jawaban yang benar?). Akurasi sangat penting ketika kita melakukan jutaan perhitungan dengan nilai-nilai perkiraan seperti representasi floating-point dari bilangan real yang biasa kita gunakan pada komputer. Beberapa algoritma numerik menggunakan antrian prioritas dan menyortir untuk mengontrol akurasi dalam perhitungan.
• Pencarian kombinatorial. Sebuah paradigma klasik dalam kecerdasan buatan adalah untuk mendefinisikan satu set konfigurasi dengan baik didefinisikan bergerak dari satu konfigurasi ke depan dan prioritas yang terkait dengan setiap langkah. Juga pasti adalah konfigurasi awal dan konfigurasi tujuan (yang sesuai dengan telah memecahkan masalah Algoritma A * adalah proses pemecahan masalah di mana kita meletakkan konfigurasi awal pada antrian prioritas, kemudian melakukan hal berikut sampai mencapai tujuan. Menghapus konfigurasi tertinggi-prioritas dan menambah antrian semua konfigurasi yang dapat dicapai dari yang dengan satu gerakan (tidak termasuk yang baru saja dihapus).

E.       IMPLEMENTASI

a.      Source code

/*
 * Created by SharpDevelop.
 * User: Uyik
 * Date: 11/21/2015
 * Time: 7:07 PM
 *
 * To change this template use Tools | Options | Coding | Edit Standard Headers.
 */
using System;
namespace selection
{
    class Program
    {
        public static void Main()
        {
            int[] a = new int[100];
            int min, pass, i;
            Console.WriteLine("Masukkan Jumlah array: ");
            string s = Console.ReadLine();
            int x = Int32.Parse(s);
            Console.WriteLine("-----------------------");
            Console.WriteLine(" Masukkan elemen array:");
            Console.WriteLine("-----------------------");
            for (int j = 0; j < x; j++)
            {
                string s1 = Console.ReadLine();
                a[j] = Int32.Parse(s1);
            }
            for (pass = 0; pass < x - 1; pass++)
            {
                min = pass;
                for (i = pass + 1; i < x; i++)
                {
                    if (a[min] > a[i])
                        min = i;
                }
                if (min != pass)
                {
                    int k = a[pass];
                    a[pass] = a[min];
                    a[min] = k;
                }
            }
            Console.WriteLine("-----------------------");
            Console.WriteLine("Angka sudah diurutkan dengan metode selection sort:");
            for (int j = 0; j < x; j++){            
                Console.WriteLine(a[j]);   }
        }
      }
}

b.      Hasil

DAFTAR PUSTAKA

lecturer.ukdw.ac.id/anton/.../prak.../modul%202%20-%20sorting.doc

http://lecturer.eepis-its.edu/~entin/Struktur%20Data%20%26%20Algoritma/buku/Data%20Structure%20-%20Bab%206.pdf

Abhiram. 2009. History of Sorting Algorithms. http://abhiramn.blogspot.com/2009/07/history-of-sorting-algorithms.html. Diakses tanggal 10 November 2015

Anonim. Algortima Sorting. tanzir.staff.gunadarma.ac.id/Downloads/files/12729/kuliah6.pdf. Diakses tanggal 10 November 2015

Anonim. Algoritma Sorting. poss.ipb.ac.id/files/JENI-Intro2-Bab06-Algoritma%20Sorting.pdf. Diakses tanggal 10 November 2015

Ari, Rosihan. 2008. Algoritma Sorting dan Implementasinya. http://blog.rosihanari.net/algoritma-sorting-dan-implementasinya. Diakses tanggal 10 November 2015

Munir, Rinaldi. 2011. Tarian Dansa Algoritma “Sorting” Gaya Rumania dan Hungaria. http://rinaldimunir.wordpress.com/2011/09/20/tarian-dansa-algoritma-sorting-gaya-rumania-dan-hungaria/. Diakses tanggal 10 November 2015

Nugroho, Adi. 2009. Algoritma & Struktur Data denga C#. Yogyakarta: Andi Offset.

Pratama, Johan. 2010. Algoritma Sorting. http://jojoinformation.wordpress.com/2010/05/29/algoritma-sorting/. Diakses tanggal 10 November 2015

Priyono, Handi. 2010. Sejarah dan Pengertian Algoritma-Pemrograman. http://handzmentallist.blogspot.com/2010/04/sejarah-dan-pengertian-algoritma.html. Diakses tanggal 10 November 2015

Septian, Agung. 2011. Perbedaan Bubble Sort, Merge Sort, dan Quick Sort. http://ahonk-ftk10.blogspot.com/2011/03/perbedaan-bubble-sortmerge-sort-dan.html. Diakses tanggal 10 November 2015

Triono, Puji. 2010. Analisis Perbandingan Algoritma Sorting dan Searching. Yogyakarta: Fakultas Teknologi Industri Universitas Ahmad Dahlan.

Negara, Setia B Tjaru. 2009. Kompleksitas Algoritma Pengurutan Selection Sort dan Insertion Sort. http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2009-2010/Makalah0910/MakalahStrukdis0910-074.pdf. Diakses pada tanggal 10 November 2015