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 ?
Dengan Dev C++ :
int
banyakData, cariData, posisi=0;
bool
ketemu = false;
cout
<< "Banyak data : ";
cin
>> banyakData;
int
data[banyakData];
for(int
ulang=0; ulang<banyakData; ulang++)
{
cout
<<"Berikan Data ke["<<ulang<<"] : ";
cin
>> data[ulang];
}
cout
<<"Data yang akan di cari posisinya: ";
cin >>
cariData;
for(int
ulang=0; ulang<banyakData; ulang++)
{
if(cariData == data[ulang])
{
posisi = ulang;
ketemu = true;
break;
}
}
if(ketemu)
{
cout<<"Data "<<cariData<<" ditemukan di
posisi : "<<posisi<<endl;
cout<<"Terimakasih"<<endl;
}
else
{
cout<<"Data yang anda berikan"<<endl;
cout<<"Tidak tertera pada data Array"<<endl;
}
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.
Dengan Dev C++ :
int
A[10],i,j,k,tkr,top,bottom,middle,tm;
for(i=0; i<10; i++)
{
printf("Data ke-%d : ", i+1);
scanf("%d", &A[i]);
}
printf("Masukkan data yang akan dicari : ");
scanf("%d",&k);
for(i=0; i<10; i++)
{
for(j=i+1; j<10; j++)
{
if(A[i]>A[j])
{
tkr=A[i];
A[i]=A[j];
A[j]=tkr;
}
}
}
tm=0;
top=9;
bottom=0;
while(top>=bottom)
{
middle=(top+bottom)/2;
if(A[middle]==k)
{
tm++;
}
if(A[middle]<k)
{
bottom=middle+1;
}
else
{
top=middle-1;
}
}
if(tm>0)
{
printf("Data %d yang dicari ada dalam
array\n",k);
}
else
{
printf("Data tidak diketemukan dalam
array\n");
}
b. Jelaskan langkah-langkah
pencarian nilai 71 dalam array tersebut dengan metode
pencarian biner, sehingga
menghasilkan kesimpulan bahwa nilai tersebut tidak berhasil
ditemukan.
Dengan Dev C++ :
int A[15],i,j,k,tkr,top,bottom,middle,tm;
for(i=0;
i<15; i++)
{
printf("Data ke-%d : ", i+1);
scanf("%d", &A[i]);
}
printf("Masukkan data yang akan dicari : ");
scanf("%d",&k);
for(i=0;
i<15; i++)
{
for(j=i+1; j<15; j++)
{
if(A[i]>A[j])
{
tkr=A[i];
A[i]=A[j];
A[j]=tkr;
}
}
}
tm=0;
top=9;
bottom=0;
while(top>=bottom)
{
middle=(top+bottom)/2;
if(A[middle]==k)
{
tm++;
}
if(A[middle]<k)
{
bottom=middle+1;
}
else
{
top=middle-1;
}
}
if(tm>0)
{
printf("Data %d yang dicari ada dalam array\n",k);
}
else
if(tm=71)
{
printf("Data tidak diketemukan dalam array\n");
} else
{
printf("Data tidak diketemukan dalam array\n");
}
3. Urutkan
deret angka berikut dengan bubble sort :
7 4 5 8 10
Tuliskan hasil tiap langkah (step).
Dengan Dev C++ :
int a,k,c,d,g;
k=5;
int b[5];
cout<<"Bubble sort adalah salah satu metode sorting atau
mengurutkan dari data terkecil ke data terbesar "<<endl<<endl;
for(a=0;a<k;a++)
{
cout<<"Masukkan nilai "<<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<<"\n setelah diurutkan akan menjadi : \n";
for(a=0;a<k;a++)
{
cout<<b[a]<<" \n";
}
4 4. Periksalah
daftar 6 angka di bawah ini :
14 32 5 12 61 7
Ketika Anda melihat daftar tersebut,
Anda segera dapat melihat bahwa 5 adalah angka
terkecil didaftar. Tugas ini
lebih sulit untuk komputer. Jadi untuk itu harus dibuat program
Bab 7
Search & Sort halaman : 186
untuk menemukan nilai minimum
tersebut. Buatlah program selection sort dan lakukan
sorting secara manual (step by step) !
Dengan Dev C++ :
int main()
{
int data [50];
int a,b;
int max,min;
// masukan untuk batas
printf("Banyak Bilangan: ");scanf
("%d",&a);
//pengulangan untuk memasukkan data ke dalam array
for (b=1;b<=a;b++)
{
printf("\nbilangan ke-%d: ",b);scanf("%d",&data
[b]);
}
//mencari nilai terbesar dan terkecil di array dengan
looping
max=data[1];
min=data[1];
for
(b=1;b<=a;b++)
{
if
(data[b]>=max)
{
max=data[b];
}
else if
(data[b]<=min)
{
min=data[b];
}
}
printf("\n\nnilai tertinggi\t:%d", max);
printf("\n\nnilai terkecil\t:%d", min);
getch();
35. Urutkan
deret angka berikut dengan selection sort dan tuliskan hasil tiap langkah
(step) :
21 16 25 8 19 4 1
Dengan Dev C++ :
void s_sort(T a[],int n)
{
int i,j,t;
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(a[j]<a[i])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
}
int main()
{
int a[100],i,n;
cout<<"Masukan jumlah elemen : ";
cin>>n;
cout<<"Masukan elemen - elemen tersebut :";
for(i=0;i<n;i++)
{
cout<<"\n
Enter : ";
cin>>a[i];
}
s_sort(a,n);
cout<<"Setelah di sorting :";
for(i=0;i<n;i++)
{
cout<<a[i]<<" , ";
}
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 !
Dengan Dev C++ :
int data[7] = {0,5,2,4,6,1,3};
int data2[7];
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<=6;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
for(int
i=1;i<=6;i++)
{
cout<<"Data ke "<<i<<" :
"<<data[i]<<endl;
data2[i]=data[i];
}
insertion_sort();
cout<<"\n\n";
//tampilkan data
cout<<"Data Setelah di Sort :
";
for(int i=1; i<=6;
i++)
{
cout<<"
"<<data[i];
}
cout<<"\n\nSorting Selesai";
getch();
}
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
paling kecil berada paling depan samapai yang paling
besar berada paling belakang !
Dengan Dev C++ :
using namespace std;
void merge(int low, int mid, int up);
void mergeSort(int low, int up);
int a[8] = {32 , 12
, 5 ,
18 , 31 , 4
, 25 , 7 };
int main()
{
int jumlahBil,i;
for(int i=0; i<8;i++)
{
cout<<"Bilangan ke- ["<< i <<
"] "<<a[i]<<endl;
}
mergeSort(1,8);
for(i=0;i<8;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
void merge(int low, int mid, int up)
{
int h, i,j,k;
int b[50];
h = low;
i = low;
j = mid+1;
while((h<=mid)&&(j<=up))
{
if(a[h] < a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=up;k++){
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=up;k++) a[k]=b[k];
}
void mergeSort(int low, int up)
{
int mid;
if(low<up)
{
mid=(low+up)/2;
mergeSort(low,mid);
mergeSort(mid+1,up);
merge(low,mid,up);
}
}
8.
Diketahui
deretan data sebagai berikut :
8 1 4 9 7 3 5 2
7
Urutkan data tsb. memakaiMerge
sort, agar elemen terkecil berada paling depan (urutan
pertama), semakin ke belakang semakin besar !
Dengan Dev C++ :
void merge(int low, int mid, int up);
void mergeSort(int low, int up);
int a[9] = {8 ,
1 , 4 , 9 ,
7 , 3
, 5 , 2 , 7 };
int main()
{
int jumlahBil,i;
for(int i=0; i<9;i++)
{
cout<<"Bilangan ke- ["<< i + 1
<< "] "<<a[i]<<endl;
}
mergeSort(1,9);
for(i=0;i<9;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
void merge(int low, int mid, int up)
{
int h, i,j,k;
int b[50];
h = low;
i = low;
j = mid+1;
while((h<=mid)&&(j<=up))
{
if(a[h] < a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=up;k++){
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=up;k++) a[k]=b[k];
}
void mergeSort(int low, int up)
{
int mid;
if(low<up)
{
mid=(low+up)/2;
mergeSort(low,mid);
mergeSort(mid+1,up);
merge(low,mid,up);
}
}
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 !
Dengan Dev C++ :
#include <stdio.h>
#define MAX 10
#define MaxStack 11
int Data[MAX];
// Prosedur menukar data
void Tukar (int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Prosedur pengurutan metode
Quick Sort
void QuickSortNonRekursif()
{
struct tump {
int Kiri;
int Kanan;
}
Tumpukan[MaxStack];
int i, j, L, R, x, ujung = 1;
Tumpukan[1].Kiri = 0;
Tumpukan[1].Kanan = MAX-1;
while (ujung!=0){
L =
Tumpukan[ujung].Kiri;
R =
Tumpukan[ujung].Kanan;
ujung--;
while(R > L){
i = L;
j = R;
x =
Data[(L+R)/2];
while(i <= j){
while(Data[i] < x)
i++;
while(x < Data[j])
j--;
if(i <= j){
Tukar(&Data[i], &Data[j]);
i++;
j--;
}
}
if(L < i){
ujung++;
Tumpukan[ujung].Kiri = i;
Tumpukan[ujung].Kanan = R;
}
R = j;
}
}
}
int main()
{
int i;
//Memasukkan data yang belum
terurut
printf("DATA SEBELUM TERURUT :
\n");
for(i=1; i<MAX; i++)
{
printf("Data ke %d : ", i);
scanf ("%d",
&Data[i]);
}
QuickSortNonRekursif();
//Data setelah terurut
printf("\nDATA SETELAH
TERURUT");
for(i=1; i<MAX; i++)
{
printf("\nData ke
%d : %d ", i, Data[i]);
}
//scanf("%d");
return(0);
}
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 !
Dengan Dev C++ :
#include <stdio.h>
#define MAX 10
#define MaxStack 11
int Data[MAX];
// Prosedur menukar data
void Tukar (int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Prosedur pengurutan metode Quick Sort
void
QuickSortNonRekursif()
{
struct
tump {
int Kiri;
int Kanan;
}
Tumpukan[MaxStack];
int i, j,
L, R, x, ujung = 1; Tumpukan[1].Kiri = 0;
Tumpukan[1].Kanan = MAX-1;
while
(ujung!=0){
L = Tumpukan[ujung].Kiri;
R = Tumpukan[ujung].Kanan;
ujung--;
while(R > L){
i = L;
j = R;
x =
Data[(L+R)/2];
while(i <= j){
while(Data[i]
< x)
i++;
while(x < Data[j])
j--;
if(i <= j){
Tukar(&Data[i], &Data[j]);
i++;
j--;
}
}
if(L < i){
ujung++;
Tumpukan[ujung].Kiri = i;
Tumpukan[ujung].Kanan = R;
}
R = j;
}
}
}
int main()
{
int i;
//Memasukkan
data yang belum terurut
printf("DATA SEBELUM TERURUT : \n");
for(i=1;
i<MAX; i++)
{
printf("Data ke %d : ", i);
scanf ("%d", &Data[i]);
}
QuickSortNonRekursif();
//Data
setelah terurut
printf("\nDATA SETELAH TERURUT");
for(i=1;
i<MAX; i++)
{
printf("\nData ke %d : %d ", i, Data[i]);
}
//scanf("%d");
return(0);
