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