sorting c++

Pengertian Sorting

Dalam arti bahasa sorting adalah penyortiran atau memilih-milih. Pada struktur data Sorting adalah sebuahmetode untuk pengurutan data, misalnya dari data yang terbesar ke data yang terkecil. Dengan cara program yang dibuat harus dapat membandingkan antar data yang di inputkan.

Artinya jika ada deretan data, maka data yang pertama akan membandingkan dengan data yang kedua. Jika data yang pertama lebih besar dari pada data yang kedua maka data yang pertama akan bertukar posisi dengan data yang kedua, begitu seterusnya sampai benar-benar data terurut dari yang terbesar hingga yang terkecil.

Metode sorting sangat banyak dan berkembang ada  

·                     Selection Sort

·                      Insertion sort 

·                     dll

 

pengertian selection short:
adalah tehnik pengurutan dengan cara memilih elemen atau proses kerja dengan cara memilih elemen terkecil untuk kemudian dibandingkan & ditukarkan dengan elemen data awal dab seterusnya sampai dengan seluruh elemen,sehingga akan menghasilkan pola data yang telah di short.
perinsip kerja selection short:
1. Pengecekan dimulai data ke-1 sampai
dengan data ke-n
2. Tentukan bilangan dengan Index terkecil
dari data bilangan tersebut
Prinsip Kerja dari Teknik Selection Sort ini
adalah :
3. Tukar bilangan dengan Index terkecil
tersebut dengan bilangan pertama ( I = 1 )
dari data bilangan tersebut
4. Lakukan langkah 2 dan 3 untuk bilangan
berikutnya ( I= I+1 ) sampai didapatkan
urutan yg optimal.

contoh program :

#include <iostream>
#include <conio.h>

int main(void)
{
int array[5];
int length = 5;
int i, j;
int firstelement, temp;


for (i = 0; i < length; i++)
{
cout << "Masukkan Antrian: ";
cin >> array[i];
}


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;
}


for (i = 0; i < 5; i++)
{
cout << array[i] << endl;
}
getch();
}

  contoh:
1. Buatlah listing program untuk mengurutkan data secara descending menggunakan selection sort
    Contoh listing programnya :

#include<iostream.h>

#include<conio.h>

#define batas 50

int i, j, tukar, max, bil[batas];

void temp(n)

{

      for(n=0; n<max; n++)

      {

         cout<<bil[n]<<ends;

      }

      getch();

}

void main()

{

   cout<<"SELECTION SORT"<<endl<<endl;

   cout<<"MASUKKAN BANYAKNYA DATA : ";

   cin>>max;

   cout<<endl;

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

   {

      cout<<"INPUTKAN BILANGAN KE- "<<(i+1)<<" : ";

      cin>>bil[i];

   }

   for(i=0; i<max-1; i++)

   {

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

      if(bil[j]>bil[i])

      {

         tukar=bil[i];

         bil[i]=bil[j];

         bil[j]=tukar;

      }

      cout<<endl<<endl<<"PASS :";

      temp(i);

   }

   cout<<endl<<endl<<"HASIL SORTING :";

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

   {

      cout<<bil[i]<<ends;

   }

   getch();

}

 

 

 

Insertion Sort (Metode Penyisipan)

• Insertion Sort merupakan algoritma yang efisien untuk mengurutkan angka yang mempunyai jumlah elemen sedikit. Dimana:- Input : deretan angka sejumlah n buah
  - Output : permutasi (pengurutan) sejumlah n angka dari input yang sudah terurut secara ascending maupun descending 

• Metode penyisipan (Insertion sort) bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan.
• Metode ini mengurutkan bilangan-bilangan yang telah dibaca; dan berikutnya secara
  berulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut. 
• Insertion Sort bekerja seperti banyak orang yang sedang mengurutkan kartu di tangan. Dimulai dengan tangan kiri yang kosong dan kartunya tertumpuk di meja. Selanjutnya kita ambil satu persatu kartu di meja dan diletakkan di tangan kiri dengan posisi yang benar (terurut). Untuk menemukan posisi yang banar, maka kita harus membandingkan satu persatu kartu yang ada (di tangan kiri) secara berurutan.

 

 contoh program :

Contoh Listening Program C++

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

sumber :
http://sisinform-aaf1231072.blogspot.com/2013/02/insertion-sort.html

searching c++

1. Pengertian Searching
Pencarian (Searching) merupakan proses yang fundamental dalam pemrograman, guna menemukan data (nilai) tertentu di dalam sekumpulan data yang bertipe sama. Fungsi pencarian itu sendiri adalah untuk memvalidasi (mencocokkan) data.
2. Metode pencarian dibagi menjadi 2, yaitu:
1. Metode Pencarian Beruntun
Konsep yang digunakan dalam metode ini adalah membandingkan data-data yang ada dalam kumpulan tersebut, mulai dari elemen pertama sampai elemen ditemukan, atau sampai elemen terakhir.
2. Metode Pencarian Bagi Dua (Binary Search)
Metode ini diterapkan pada sekumpulan data yang sudah terurut (menaik atau menurun). Metode ini lebih cepat dibandingkan metode pencarian beruntun. Data yang sudah terurut menjadi syarat mutlak untuk menggunakan metode ini.
Konsep dasar metode ini adalah membagi 2 jumlah elemennya, dan menentukan apakah data yang berada pada elemen paling tengah bernilai sama, lebih dari atau kurang dari nilai data yang akan dicari. Jika bernilai sama, maka langsung data yang dicari ditemukan. Jika data di elemen terurut naik, maka jika data yang berada di tengah kurang dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kanan, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan sebaliknya untuk nilai data yang berada di tengah lebih dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kiri, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan demikian sebaliknya untuk data yang terurut menurun. Dalam hal ini tentukan indeks paling awal dan indeks paling akhir, untuk membagi 2 elemen tersebut.
Indeks awal = i, dimana nilai i, pada awalnya bernilai 0;
Indeks akhir = j, dimana nilai j, pada awalnya bernilai sama dengan jumlah elemen.
contoh script 1:
//#include
#include
#include
//#pragma hdrstop
//#pragma argsused
int main(int argc , char* argv[])
{
int x,i,k;
int l[10]={20,15,22,30,60,28,17,18,21,22};
printf(“Data yang dicari = “); scanf(“%d”,&x);
k=0;
for(i=0;i<9;i++)
{
if(l[i]==x)
{
printf("Data ditemukan di elemen %d\n",i);
k++;
}
}
if(k==0)
{
printf("Data tidak ditemukan\n");
}
printf("Jumlah data yang ditemukan = %d",k);
getch();
return 0;
}
contoh script 2:
//#include
//#include hrdstop
#include
#include
//#pragma argsused
int main(int argc, char* argv[])
{
int X,i,j,k,p;
int L[10]={12,14,15,17,23,25,45,67,68,70};
/*Menentukan apakah terurut menaik atau menurun*/
/*Variabel p digunakan untuk kode, apakah menaik atau menurun*/
/*Jika p=0, maka data terurut menaik*/
/*Jika p=1, maka data terurut menurun*/
if (L[0]<L[9])
{
printf("Data terurut menarik \n");
p=0;
}
else
{
printf("Data terurut menurun \n");
p=1;
}
/*input data X yang akan dicari*/
printf("Data yang dicari="); scanf("%d",&X);
/*Penentuan indeks awal dan akhir semula*/
i=0;
j=9;
/*proses perulangan untuk menentukan nilai tengah k */
do
{
k=(i+j)/2;
if (p==0) //jika data terurut menaik
{
if (L[k]==X)
{
printf ("Data ditemukan di elemen %d",k);
getch();
return 0; //langsung keluar program
}
else if(L[k]X)
{
i=k;
}
else
{
j=k;
}
}
}
while(k!=0); //sampai nilai k=0, iterasi berakhir
printf(“data tida ditemukan!!”);
getch();
return 0;
}




sumber : https://lusiajah.wordpress.com/2009/05/30/searching-dan-sorting-di-c/

queue c++

Queue atau antrian prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In First Out).

Queue atau antrian banyak kita jumpai dalam kehidupan sehari-hari, ex: antrian Mobil diloket Tol, Antrian mahasiswa Mendaftar, dll. Contoh lain dalam bidang komputer adalah pemakaian sistem komputer berbagi waktu(time-sharing computer system) dimana ada sejumlah pemakai yang akan menggunakan sistem tersebut secara serempak.

Pada Queue atau antrian Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya dimana membutuhkan variabel Head dan Tail (depan/front, belakang/rear).

Operasi-operasi Queue :

1. Create()

Untuk menciptakan dan menginisialisasi Queue

2. IsEmpty()

Untuk memeriksa apakah Antrian masih kosong

 

3. IsFull()

Untuk mengecek apakah Antrian sudah penuh atau belum

 

4. Enqueue ()

Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang

5. Dequeue()

Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian

 

6. Clear()

Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1

 

7. Tampil()

Untuk menampilkan nilai-nilai elemen Antrian

Syntax Program : 

//header file

# include <stdio.h>

# include <conio.h>

# include <stdlib.h>

# include <string.h>

# define QSIZE 5

//deklarasi struct

typedef struct

{

      int count;

    int head,tail;

    char names[QSIZE][30];

}QUEUE; //nama struct

char *enqueue(char *);

char* dequeue();

//deklarasikan prototype fungsi

void tampil();

void inisialisasi();

//deklarasi Node

QUEUE *pq;

//fungsi main

int main()

{

      //deklarasi variabel

      int pil;

      char str[30];

      QUEUE q;

      pq=&q;

      inisialisasi(); //panggil fungsi inisialisasi

      do{

            system("cls"); //bersihkan layar

            printf("\tMENU PILIHAN : ");

            printf("\n\t______________");

            printf("\n[1] Input Data");

            printf("\n[2] Delete Data");

            printf("\n[3] Show data in queue");

            printf("\n[4] Exit\n");

            printf("\nPilihan anda : ");

            scanf("%d",&pil);

            switch(pil){

            case 1:

                  printf("\nSilahkan memasukkan sebuah kata : ");

                  fflush(stdin); //menghapus buffer data

                  gets(str);

                 puts(enqueue(str)); /*Mencetak string hasil penambahan data yang dilakukan oleh fungsi enqueue()*/

                  break;

            case 2:

                 puts(dequeue()); /*Mencetak string terhapus yang dilakukan oleh fungsi enqueue()*/

                  break;

            case 3:

                  tampil(); //panggil fungsi tampil()

                  break;

            case 4: exit(0);

            default: printf("\nMasukkan anda salah!!");

            }

            printf("\nPress Any Key to continue...");

            fflush(stdin); //membersihkan buffer data

            while(!kbhit());

      }

      while(1); //perulanagan dijalankan terus

    //return 0;

}

//fungsi untuk inisialisasi awal

void inisialisasi()

{

      pq->head = pq->tail = pq->count= 0;

}

//fungsi untuk menambah data string dalam queue

char* enqueue(char *p)

{

      if(pq->count==QSIZE)

            return "\n\n\t\t Error: Antrian penuh";

      pq->tail= (pq->tail)%QSIZE;

      strcpy(pq->names[(pq->tail)++],p);

      pq->count++;

      return "Data telah berhasil dimasukkan";

}

//fungsi untuk menghapus data string dalam queue

char* dequeue()

{

      if(pq->count==0)

            return "\n\n\t\t Error: Antrian kosong";

      pq->head= (pq->head)%QSIZE;

      pq->count--;

      printf("\nData yang telah dihapus adalah\n:");

      return pq->names[(pq->head)++];

}

//fungsi untuk menampilkan data yang berada dalam antrian

void tampil()

{

      int i=pq->head;

      int x=0;

      if(pq->count==0)

            printf("Antrian kosong\n");

      else

      {

            while(x<pq->count)

            {

                  if(i==QSIZE)

                        i%=QSIZE;

                  printf(":%s\n",pq->names[i]);

                  i++;

                  x++;

            }

      }

}

 scere shot hasil program :

 contoh study kasus : 

1. Buatlah program dengan queue untuk menampung data mahasiswa yang terdiri dari nim, nama dan ipk mahasiswa
Listing programnya adalah

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<iostream.h>

#define n 20

int f, r;

typedef struct

{

   char nim[15];

   char nama[50];

   float ipk;

}mahasiswa;

void awal()

{

   f=0;

   r=-1;

}

void main()

{

   mahasiswa data[n];

   int pilih;

   awal();

   atas:

   cout<<"QUEUE DATA MAHASISWA"<<endl<<endl;

   do{

   cout<<endl<<"1. INSERT DATA"<<endl;

   cout<<"2. DELETE DATA"<<endl;

   cout<<"3. EXIT"<<endl<<endl;

   cout<<"MASUKKAN PILIHAN ANDA : ";

   cin>>pilih;

   switch(pilih)

   {

      case 1 :

         if(r<n-1)

         {

            r++;

            cout<<endl<<"MASUKKAN NIM : ";

            cin>>data[r].nim;

            cout<<"MASUKKAN NAMA : ";

            gets(data[r].nama);

            cout<<"MASUKKAN IPK : ";

            cin>>data[r].ipk;

         }

         else

         {

                      cout<<"ANTRIAN PENUH"<<endl;

          }

         break;

          case 2 :

            if(f<r+1)

          {

               cout<<endl<<"DATA YANG DIINPUTKAN"<<endl<<endl;

                cout<<"NIM MAHASISWA : "<<data[f].nim<<endl;

                cout<<"NAMA MAHASISWA : "<<data[f].nama<<endl;

                cout<<"IPK MAHASISWA : "<<data[f].ipk<<endl;

                f++;

                if(f==r+1 && r==n-1)

                {

                   awal();

                }

          }

          else

          {

             cout<<"ANTRIAN KOSONG"<<endl;

          }

               break;

         case 3 :

            cout<<"TERIMA KASIH";

            exit;

            break;

         default :

            cout<<endl<<"MASUKKAN ANGKA ANTARA 1-3"<<endl;

            goto atas;

   }

   }

   while((pilih>=1)&&(pilih<=2));

   getch();

}

 sumber : http://nblognlife.blogspot.com/2014/05/c-konsep-queue.html