DIKTAT BAB 8

Assalamu'alaikum wr.wb

Latihan

1. Perhatikan bahwa Anda dapat melewatkan banyak nomor dalam daftar dan masih berada dalam urutan menaik yaitu sebagai berikut :

3 4 6 17 21 24 32 43

Angka-angka ini meningkat saat Anda bergerak melalui daftar dari kiri ke kanan. Bangunlah sebuah array yang berisi angka-angka tersebut ? Kemudian lakukan pencarian biner (Binary Search) untuk memeriksa apakah angka yang kita cari ada dalam daftar array tersebut ?

Source Code:

#include <iostream>
#include <conio.h>
using namespace std;
int main(){
 const int Ar[8] = {3,4,6,17,21,24,32,43};
 int tar;

cout<<"masukan data yang dicari : ";
 cin>>tar;
int awal=0, akhir=10, tengah;


 while (awal <= akhir)
  { tengah = (awal + akhir)/2;
  if (tar > Ar[tengah] )      // descending ubah tanda > menjadi <
      { awal = tengah + 1; }
  else if (tar < Ar[tengah])  // descending ubah tanda < menjadi >
  {akhir= tengah - 1;}
  else {awal = akhir +1;
  }
   }
   if (tar == Ar[tengah])
   {cout<<" Data ditemukan, Ke- "<<tengah+1<<endl;
   }
   else {
    cout<<"target tidak ditemukan "<<endl;
   }
getch();

}

Dev C++:

Output:

2. Jika terdapat sebuah array yang elemennya berindeks 1 sampai dengan 15. Masing-masing elemen berturut-turut berisi nilai sebagai berikut: 

1, 2, 8, 25, 30, 49, 50, 55, 60, 61, 68, 70, 72, 84, 90.
a. Jelaskan langkah-langkah pencarian nilai 49 dalam array tersebut dengan metode pencarian biner, sehingga menghasilkan indeks elemen array tempat ditemukannya nilai tersebut.
b. Jelaskan langkah-langkah pencarian nilai 71 dalam array tersebut dengan metode pencarian biner, sehingga menghasilkan kesimpulan bahwa nilai tersebut tidak berhasil ditemukan.

Source Code:

#include <iostream>
#include <conio.h>
using namespace std;
int main(){
 const int Ar[15] = {1,2,8,25,30,49,50,55,60,61,68,70,72,84,90}; // untuk proses ascending
 int tar;

cout<<"masukan data yang dicari : ";
 cin>>tar;
int awal=0, akhir=10, tengah;


 while (awal <= akhir)
  { tengah = (awal + akhir)/2;
  if (tar > Ar[tengah] )      // descending ubah tanda > menjadi <
      { awal = tengah + 1; }
  else if (tar < Ar[tengah])  // descending ubah tanda < menjadi >
  {akhir= tengah - 1;}
  else {awal = akhir +1;
  }
   }
   if (tar == Ar[tengah])
   {cout<<" Data ditemukan, data berada di indeks ke-"<<tengah+1<<endl;
   }
   else {
    cout<<"target tidak ditemukan "<<endl;
   }
getch();

}

Dev C++:

 

Output:

 

3. Urutkan deret angka berikut dengan bubble sort :

7 4 5 8 10

Tuliskan hasil tiap langkah (step). 

Source Code:

#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

int main(int argc, char** argv) {
    int a, k, c, d, g;
    k=5;
    int b[5];
    cout<<"\t\tPROGRAM MENGURUTKAN ANGKA DENGAN BUBLE SORT\n\n";
    for(a=0; a<k; a++){
        cout<<"Masukkan nilai ke-"<<a+1<<":";
        cin>>b[a];
    }
    for (a=0; a<k-1; a++){
        for (d=a+1; d<k; d++){
        c=a;
        if (b[c]>b[d]){
            c=d;
        }   
        g=b[c];
        b[c]=b[a];
        b[a]=g;
        }
    }
    cout<<"\nSetelah diurutkan maka akan menjadi :\n";
    for(a=0; a<k; a++){
        cout<<b[a]<<"  ";
    }
    return 0;
}

Dev C++:

 

Output:

 

5. Urutkan deret angka berikut dengan selection sort dan tuliskan hasil tiap langkah (step) :
21 16 25 8 19 4 1 

Analisis:

[21, 16, 25, 8, 19, 4, 1]

Data pertama : 21

Mencari data terkecil dari data kedua sampai terakhir.

(i=1)

Data terkecil ditemukan pada posisi ke-7 (t=7), maka data pertama ditukar pada posisi ke-7, menjadi:

[1, 16, 25, 8, 19, 4,21]

Langkah ini diulang untuk data kedua (i=4). Ditemukan pada posisi ke-6 (t=6).

Data kedua ditukar dengan data ke-6, menjadi :

[1, 4, 25, 8, 19,16,  21]

Fase selengkapnya :

Data awal :          [21, 16, 25, 8, 19, 4, 1]            1 terkecil, 21               1

Fase 1              [1, 16, 25, 8, 19, 4, 21]            4 terkecil, 16               4

Fase 2              [1, 4, 25, 8, 19, 16, 21]            8 terkecil, 25               8

Fase 3              [1, 4, 8, 25, 19, 16, 21]            16 terkecil, 25             16

Fase 4              [1, 4, 8, 16, 19, 25, 21]            19 terkecil, 19             19

Fase 5              [1, 4, 8, 16, 19, 25, 21]            21 terkecil, 25             21

Fase 6              [1, 4, 8, 16, 19, 21, 25]            25 terkecil tetap.

Fase 7              [1, 4, 8, 16, 19, 21, 25]           

Fase 8              [1, 4, 8, 16, 19, 21, 25]           

Source Code:

#include <iostream>
#include <conio.h>
using namespace std;
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 selection_sort()
{
 int pos,i,j;
 for(i=1;i<=n-1;i++)
 {
  pos = i;
  for(j = i+1;j<=n;j++)
  {
   if(data[j] < data[pos]) pos = j;
  }
  if(pos != i) tukar(pos,i);
 }
}

int main()
{
 cout<<"URUT DERET ANGKA DENGAN SELECTION SORT"<<endl<<endl;

 cout<<"Masukkan Jumlah Data : ";
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cout<<"Masukkan data ke "<<i<<" : ";
  cin>>data[i];
  data2[i]=data[i];
 }

 selection_sort();
 cout<<"Data Setelah di Sort : ";
 for(int i=1; i<=n; i++)
 {
  cout<<" "<<data[i];
 }

 getch();
}

Dev C++:

lanjutan...

 

Output:

 

6. Diketahui deret angka sebagai berikut :
5 2 4 6 1 3
Dari deret angka tersebut, lakukan pengurutan dari yang paling kecil sampai paling besar menggunakan insertion sort ! 

Source Code:
#include <iostream>
#include <conio.h>
using namespace std ;
int data[10],data2[10];
int n;

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()
{

//INPUT DATA
 cout<<"Masukkan Jumlah Data : ";
 cin>>n;
 cout<<endl;
 for(int i=1;i<=n;i++)
 {
  cout<<"Masukkan data ke-"<<i<<" : ";
  cin>>data[i];
  data2[i]=data[i];
 }

 insertion_sort();

 cout<<endl<<endl;

 //MENAMPILKAN DATA
 cout<<"Data Setelah di Sort : ";
 for(int i=1; i<=n; i++)
 {
  cout<<" "<<data[i];
 }
 cout<<endl<<endl<<"Sorting Selesai";
 getch();
}

Dev C++:

lanjutan...

 

Output:

 

7. Mari kita lihat daftar nomor dari sebuah array untuk melihat bagaimana cara merge sort bekerja :
32 12 5 18 31 4 25 7
[0] [1] [2] [3] [4] [5] [6] [7]
Lakukan sorting dari data dalam array di atas menggunakan merge sort sehingga nomor kecil berada paling depan samapai yang paling besar berada paling belakang ! 

Analisis:

[ 32, 12, 5, 18, 31, 4, 25, 7 ]

Source Code:
#include <iostream> 
#include <conio.h> 
using namespace std;
int a[50]; 
void merge(int,int,int); 
void merge_sort(int low,int high) 
{ 
 int mid; 
 if(low<high) 
 { 
  mid=(low+high)/2; 
  merge_sort(low,mid); 
  merge_sort(mid+1,high); 
  merge(low,mid,high); 
 } 
} 
void merge(int low,int mid,int high) 
{ 
 int h,i,j,b[50],k; 
 h=low; 
 i=low; 
 j=mid+1; 
 while((h<=mid)&&(j<=high)) 
 { 
  if(a[h]<=a[j]) 
  { 
   b[i]=a[h]; h++; 
  } 
  else 
  { 
   b[i]=a[j]; j++; 
  } i++; 
 } 
 if(h>mid) 
 { 
  for(k=j;k<=high;k++) 
  { 
   b[i]=a[k]; i++; 
  } 
 } 
 else 
 { 
  for(k=h;k<=mid;k++) 
  { 
   b[i]=a[k]; i++; 
  } 
 } 
 for(k=low;k<=high;k++) 
  a[k]=b[k]; 
} 
int main() 
{ 
 int num,i,b;
 cout<<"***************************"<<endl; 
 cout<<" MERGE SORT PROGRAM "<<endl; 
 cout<<"***************************"<<endl; 
 cout<<endl<<endl; 
 cout<<"Masukkan Banyak Bilangan: ";cin>>num; 
   cout<<endl; 
 cout<<"Sekarang masukkan "<< num <<" Bilangan yang ingin Diurutkan :"<<endl; 
 for(b=1;b<=num;b++) 
 { 
  cout<<"Bilangan ke-"<<b<<" : ";cin>>a[b] ; 
 } 




 merge_sort(1,num); 
 cout<<endl; 
 cout<<"Hasil akhir pengurutan :"<<endl; 
 cout<<endl; 
 for(i=1;i<=num;i++) 
  cout<<a[i]<<" "; 
 cout<<endl<<endl<<endl<<endl;

   getch(); 
}

Dev C++:

lanjutan....

 

lanjutan....

 

Output:

9.Ada beberapa kumpulan data sebagai berikut :
2 8 3 5 6 4 11 1 9
Urutkan kumpulan data di atas menggunakan quick sort serta gambarkan step by step dari sorting tersebut Source Code:
 # include <iostream>
# include <iomanip>
# include <conio.h>
using namespace std;

void q_sort(int[],int,int);

int main ()
{
 int NumList[9]={2,8,3,5,6,4,11,1,9};

 cout<<" Data Sebelum diurutkan: \n";
 for(int d=0;d<9;d++)
 {
 cout<<setw(3)<<NumList[d];
 }
 cout<<"\n\n";
 q_sort(NumList,0,9);
 cout<<" Data setelah diurutkan: \n";
 for(int iii=0;iii<9;iii++)
 cout<<setw(3)<<NumList[iii]<<endl<<endl;

 getch();
}

void q_sort(int numbers[],int left,int right)
{
 int pivot,l_hold,r_hold;
 l_hold=left;
 r_hold=right;
 pivot=numbers[left];
 while(left<right)
 {
 while((numbers[right]>=pivot)&&(left<right))
 right--;
 if(left!= right)
 {
 numbers[left]=numbers[right];
 left++;
 }
 while((numbers[left]<=pivot)&&(left<right))
 {
 left++;
 }
 if (left!=right)
 {
 numbers[right]=numbers[left];
 right--;
 }
 }
 numbers[left]=pivot;
 pivot=left;
 left=l_hold;
 right=r_hold;
 if(left<pivot)
 q_sort(numbers,left,pivot-1);
 if(right>pivot)
 q_sort(numbers,pivot+1,right);
 }

Dev C++:

lanjutan....

Output:

 

10. Urutkan data yaitu [2 8 7 1 3 5 6 4] dengan menggunakan Quick Sort, agar elemen terkecil berada paling depan (urutan pertama), semakin ke belakang semakin besar ! 

Source Code:

# include <iostream>
# include <iomanip>
# include <conio.h>
using namespace std;
void q_sort(int[],int,int);

int main ()
{
 int NumList[8]={2,8,7,1,3,5,6,4};

 cout<<" Data Sebelum diurutkan: \n";
 for(int d=0;d<8;d++)
 {
 cout<<setw(3)<<NumList[d];
 }
 cout<<"\n\n";
 q_sort(NumList,0,8);
 cout<<" Data setelah diurutkan: \n";
 for(int iii=0;iii<8;iii++)
 cout<<setw(3)<<NumList[iii];

 getch();
}

void q_sort(int numbers[],int left,int right)
{
 int pivot,l_hold,r_hold;
 l_hold=left;
 r_hold=right;
 pivot=numbers[left];
 while(left<right)
 {
 while((numbers[right]>=pivot)&&(left<right))
 right--;
 if(left!= right)
 {
 numbers[left]=numbers[right];
 left++;
 }
 while((numbers[left]<=pivot)&&(left<right))
 {
 left++;
 }
 if (left!=right)
 {
 numbers[right]=numbers[left];
 right--;
 }
 }
 numbers[left]=pivot;
 pivot=left;
 left=l_hold;
 right=r_hold;
 if(left<pivot)
 q_sort(numbers,left,pivot-1);
 if(right>pivot)
 q_sort(numbers,pivot+1,right);
 }

Dev C++:

 

lanjutan....

 

Output:

 

 

Wassalamu'alaikum wr.wb