Selection Sort

Selection Sort
Pengertian dari selection sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan,
Selection Sort Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang
maka dicatat posisinya dan kemudian ditukar.

Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter.Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun) Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.

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
Konsep 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 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:
1. Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list
2. Menukarkan nilai ini dengan elemen pertama list
3. 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.
Simulasi Selection Sort Untuk lebih jelasnya, perhatikanlah simulasi Selection Sort Ascending berikut dengan menggunakan larik
    5 1 43 27 6 18 33
Dalam satu kali, ditentukan elemen yang paling kecil di dalam bagian list yang belum urut
.
Elemen yang paling kecil ini, diwarnai merah . Untuk bagian larik yang telah diurutkan diberi warna kuning.

0		5	1	43	27	6	18	33
1		1	5	43	27	6	18	33
2		1	5	43	27	6	18	33
3		1	5	6	27	43	18	33
4		1	5	6	18	43	27	33
5		1	5	6	18	27	43	33
6		1	5	6	18	27	33	43

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.

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. 

 

controh algoritma

 

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

Bubble Sort

Bubble Sort

Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.

Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

Algoritma Bubble Sort

1. Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).
2. Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
3. Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.
4. Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.

Algoritma Bubble Sort untuk Pengurutan (Sorting)

Pengurutan merupakan salah satu proses dasar yang sering dibahas dalam algoritma dan struktur data. Dan salah satu algoritma klasik dan paling sederhana dalam hal pengurutan (sorting) adalah algoritma Bubble Sort. Terlepas dari beberapa kekurangan yang membuat algoritma ini tidak banyak digunakan dalam proses pengurutan di aplikasi, namun tidak bisa dipungkiri, algoritma ini boleh dikatakan sebagai pionir algoritma sorting.
Di dalam matakuliah Algoritma dan Struktur Data di berbagai perguruan tinggi juga bisa dipastikan memasukkan konsep pengurutan menggunakan algoritma Bubble sebagai salah satu pokok bahasan. Tentunya disertai contoh program sederhana yang menerapkan pengurutan menggunakan algoritma bubble sort. Contoh program akan disajikan dalam Bahasa C dan PHP. Algoritma bubble sort dalam proses pengurutan data secara sederhana bisa diibaratkan seperti halnya gelembung udara (bubble). Algoritma ini akan menggeser nilai yang terkecil atau terbesar (sesuai dengan jenis pengurutan, ascending atau descending) ke posisi ujung dari daftar. Demikian seterusnya hingga semua daftar dalam keadaan terurut. Proses dasar yang terjadi dalam algoritma ini adalah proses pertukaran nilai (swapping).

contoh

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

QUEUE

QUEUE

Queue / Antrian adalah suatu kumpulan data yang mana penambahan elemen hanya bisa dilakukan pada satu ujung (disebut dengan sisi belakang atau rear) dan penghapusan atau pengambilan elemen dilakukan lewat ujung lain (disebut dengan sisi depan atau front).

Antrian menggunakan prinsip Pertama Masuk Pertama Keluar – First In First Out (FIFO). Dengan kata lain urutan masuk sama dengan urutan keluar. Antrian banyak dijumpai dalam kehidupan sehari-hari. Mobil-mobil yang mengantri digerbang tol untuk membeli karcis tol; orang-orang yang mengantri di loket untuk membeli karcis film juga membentuk antrian.

 Saya buat sebuah program untuk memasukkan, menghapus, dan mencetak suatu antrian data yang berupa sting dengan menggunakan queue.

 

 

source code;

#include <iostream.h>

#include <stdio.h>

#include <conio.h>

#define MAX 10

typedef struct

{

char data[MAX];

char head;

char tail;

} Queue;

Queue antrian;

void Create()

{

antrian.head=antrian.tail=-1;

}

char IsEmpty()

{

if(antrian.tail==-1)

return 1;

else

return 0;

}

char IsFull()

{

if(antrian.tail==MAX-1) return 1;

else return 0;

}

void Enqueue(int data)

{

if(IsEmpty()==1)

{

antrian.head=antrian.tail=0;

antrian.data[antrian.tail]=data;

cout<<"Data "<<antrian.data[antrian.tail]<<" Masuk!!";

}

else if(IsFull()==0)

{

antrian.tail++;

antrian.data[antrian.tail]=data;

cout<<"Data "<<antrian.data[antrian.tail]<<" Masuk!!";

}

else if (IsFull() == 1)

{

cout<<"Maaf, penuh"<<endl;

cout<<data<<" Data tidak masuk";

}

}

void Dequeue()

{

char i;

char e = antrian.data[antrian.head];

if (antrian.tail == -1)

{

cout<<"Data Kosong"<<endl;

}

else

{

for(i=antrian.head;i<=antrian.tail-1;i++)

{

antrian.data[i] = antrian.data[i+1];

}

antrian.tail--;

cout<<"Data yang Keluar lebih dulu = "<<e<<endl;

}

}

void Clear()

{

antrian.head=antrian.tail=-1;

cout<<"Data dihapus"<<endl;

}

void Tampil()

{

if(IsEmpty()==0)

{

cout<<"Data Dalam Antrian"<<endl;

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

cout<<endl;

for(char i=antrian.head;i<=antrian.tail;i++)

{

cout<<"| "<<antrian.data[i]<<" |";

}

}

else cout<<"Data Kosong";

}

void main()

{

int pil;

char data;

Create();

do

{

clrscr();

cout<<"Queue data berupa String"<<endl;

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

cout<<endl;

cout<<"1. Masukkan data"<<endl;

cout<<"2. Hapus data"<<endl;

cout<<"3. Cetak"<<endl;

cout<<"4. Hapus semua"<<endl;

cout<<"5. Keluar"<<endl;

cout<<"Pilihan Anda= "; cin>>pil;

switch(pil)

{

case 1:

{

cout<<endl;

cout<<"Data = "; cin>>data;

Enqueue(data);

break;

}

case 2:

{

cout<<endl;

Dequeue();

break;

}

case 3:

{

cout<<endl;

Tampil();

break;

}

case 4:

{

cout<<endl;

Clear();

break;

}

}

getch();

} while(pil!=5);

}

tampilan

 

STACK

STACK

Stack adalah sebuah kumpulan data dimana data yang diletakkan di atas data yang lain. Dengan demikian stack adalah struktur data yang menggunakan konsep LIFO. Dengan demikian, elemen terakhir yang disimpan dalam stack menjadi elemen pertama yang diambil. Dalam proses komputasi, untuk meletakkan sebuah elemen pada bagian atas dari stack, maka kita melakukan push. Dan untuk memindahkan dari tempat yang atas tersebut, kita melakukan pop.

Pada saat ukuran stack, kalau kita teruskan menambah data lagi, akan terjadi overflow. Dengan demikian perlu data tambahan untuk mencatat posisi ujung stack. Dengan kebutuhan seperti ini, kita dapat menyajikan stack dengan menggunakan tipe data struktur (struct) yang terdiri dari dua field. Field pertama bertipe array untuk menyimpan elemen stack, medan kedua bertipe integer untuk mencatat posisi ujung stack.

Sebagai ilustrasi, “Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack. Hal ini asemacam kebalikan dari postingan saya sebelumnya tentang queue

Saya akan membuat suatu program yang melakukan pembalikan kalimat dengan menggunakan stack
Contoh:

source code

#include <iostream.h>

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#define maxstack 200

struct STACK        //membuat jenis data abstrak 'STACK'

{

    int top;

    char data[maxstack];

};

char dta[maxstack];

struct STACK stackbaru;

void inisialisasi()

{

    stackbaru.top = -1;

}

bool isfull()        //menanyakan penuhkah?

{

    if (stackbaru.top == maxstack-1) return true;

    else return false;

}

bool isempty()        //menanyakan kosongkah?

{

    if (stackbaru.top == -1) return true;

    else return false;

}

void push(char dta) //mengisi stack (menyiapkan data)

{

    if (isfull() == false)

    {

        stackbaru.top++;

        stackbaru.data[stackbaru.top]=dta;

    }

    else

    {

        puts ("\nMaaf Stack penuh");

    }

}

void pop()            //mengambil isi stack

{

    while (isempty() == false)

    {

            cout<<stackbaru.data[stackbaru.top];

            stackbaru.top--;

    }

}

void print()        //mencetak stack

{

    cout<<" ";

    for (int i=0; i<=stackbaru.top; i++)

    {

        cout<<stackbaru.data[i];

    }

}

void clear()

{

    stackbaru.top = -1;

}

void main()

{

    char kata[200];

    printf("--- PROGRAM PEMBALIK KALIMAT --- \n\n");

    printf("Masukkan kalimat yang Anda inginkan: \n");

    gets(kata);

    for(int i=0; kata[i]; i++)

        push(kata[i]);

    printf("------------------------------------ \n\n");

print();

cout<<" menjadi ";

pop();

cout<<"\n";

getche();

}

 

Tampilan

program sorting dengan menggunakan stack

source code;

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#define maxstack 6

//using namespace std;

int top=-1;

struct STACK

{

int top;

float data[4];

};

float dta;

struct STACK stackbaru;

bool isfull ()

{

   if (stackbaru.top == maxstack)

         return true;

   else return false;

}

bool isempty()

{

   if (stackbaru.top == -1)

         return true;

   else

         return false;

}

void push (float dta)

{

   if (isfull() == true)

   {

         cout<<"maaf, stack dalam keadaan penuh";

         getche();

   }else{

         top++;

         stackbaru.top++;

         stackbaru.data[top] = dta;

   }

}

void pop ()

{

   if (isempty () == true){

         cout<<"data pada stack dalam keadaan kosong";

         getche();

   }else {

         cout<<"data yang terambil : "<<stackbaru.data[top]<<endl;

         top--;

   }

}

void print () // mencetak stack

{

   for (int i =top; i>=0;i--){

         cout<<stackbaru.data[i]<<"   ";

   }

}

void clear ()

{

   top=-1;

}

void inisialisasi ()

{

stackbaru.top=-1;

}

void Sort (int Array[])

{

   int i,j,kecil,temp;

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

         {

         {kecil=i;

         for (j=i+1; j<5; j++)

         {

               if(Array[kecil]>Array[j])

            {kecil =j;}

         }

          temp = Array [i];

         Array[i] = Array[kecil];

         Array[kecil] = temp;

         }

   }

}

int main ()

{

void inisialisasi ();

   char menu;

   char ulang;

   int data [5];

   int i,j;

do {

   clrscr;

   printf("Menu : \n");

   puts("1. pop stack");

   puts("2. Push data dan sorting ascending");

   puts("3. cetak sorting descending");

   puts("4. Bersihkan stack");

   puts("5. Exit");

   cout<<"Menu pilihan anda : ";

   cin>>menu;

   if (menu == '1'){

         pop ();

         getche ();

         ulang == 'y';

   }

   else if (menu == '2')

   {

         cout<<"sorting ascending\n";

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

   {

   cout<<"input nilai ke "<<(i+1)<<" =";

   cin>>data[i];

   }

   Sort(data);

   cout<<"sorting ascending :";

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

   {cout<<data[j];

         push(data[j]);

   }

   cout<<"\n";

   getche();

         ulang = 'y';

   clrscr;

   }else if (menu == '3')

   {

         cout<<"sorting descending\n";

         print ();

      cout<<"\n";

         getche();

   }else if (menu =='4')

   {

         clear ();

         cout<<"Ulang? (y/t)";

         cin>>ulang;

   }else if (menu =='5')

   {

   }

}while (ulang =='Y' || ulang == 'y');

getche();

}

tampilan