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
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 c++
#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();
}
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
dengan c++
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();
}
3. Urutkan deret
angka berikut dengan bubble sort :
7 4 5 8 10
Tuliskan hasil tiap langkah (step)
Dengan c++
#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;
}
Algortima
deklarasi
integer a,k,c,d,g
deskripsi
k
<-- 5
b
<-- [5]
read (n) --> input
a
<-- 0
when a< k -1
write a <-- a+1
endfor a <-- 0
when a < k -1
wite a <-- a+1
endfor d <-- a+1
when
d<k
curite
d <-- d+1
endfor
if (b[c] > b[d])
c
<-- d
else
g
<-- b[c]
b[c]
<-- b[a]
b[a]
<-- g
endif
endfor
5.
Urutkan deret angka berikut dengan selection sort dan
tuliskan hasil tiap langkah (step) :
21 16 25 8 19 4 1
Dengan c++
#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();
}
lanjutan
[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 4Fase 2 [1,
4, 25, 8, 19, 16, 21] 8
terkecil, 25 8Fase 3 [1,
4, 8, 25, 19, 16, 21] 16
terkecil, 25 16Fase 4 [1,
4, 8, 16, 19, 25, 21] 19
terkecil, 19 19Fase 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]
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 !
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 c++
#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();
}
lanjutan
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]
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 c++
#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();
}
lanjutan
lanjutan
9. Ada beberapa kumpulan data sebagai berikut :
2 8 3 5 6 4 11 1 9
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 c++
# 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);
}
lanjutan
lanjutan
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 c++
# 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);
}
lanjutan
Tidak ada komentar:
Posting Komentar