DIKTAT BAB 8

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

}

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