TUGAS 3
Deret & Algotirma Shell Sort
Oleh
Rinaldi
FAKULTAS TEKNOLOGI & INFORMASI KOMPUTER
UNIVERSITAS PRIMA INDONESIA
1. Deret
Deret adalah jumlah dari elemen-elemen dalam suatu urutan Urutan dan deret finit(atau terhingga) mempunyai elemen pertama dan terakhir yang terdefinisi, sedangkan Urutan dan deret infinit (atau tak terhingga) berlangsung terus menerus tak terbatas.
Dalam matematika, jika ada suatu urutan bilangan infinite { an }, maka suatu deret secara informal adalah hasil dari penambahan semua elemen-elemen itu bersama-sama: a1 + a2 + a3 + · · ·. Ini dapat ditulis lebih singkat menggunakan simbol summation ∑. Contohnya adalah deret terkenal dari Paradoks Zeno dan representasi matematikanya:
Elemen-elemen dalam suatu deret sering diproduksi menurut kaidah tertentu, misalnya dengan suatu rumus, atau melalui suatualgoritme. Mengingat tidak terbatasnya jumlah elemen, hasilnya sering disebut deret tak terhingga (infinite series). Berbeda dengan finite summations, deret tak terhingga membutuhkan bantuan dari analisis matematika, dan secara khusus limit, untuk dapat dipahami dan dimanipulasi secara penuh. Selain jumlahnya yang banyak dalam matematika, deret tak terhingga juga sering digunakan dalam bidang-bidang kuantitatif lain seperti fisika, sains komputer, dan finansial.
Deret bilangan yaitu jumlah dari suku – suku dari suatu barisan .
Jika U1 , U2 , U3 , U4 , . . . .Disebut dengan barisan bilangan , maka bentuk deret bilangan adalah U1 + U2 + U3 +…
Contoh :
3 + 7 + 11 + 15 + . . .
Macam – macam deret bilangan yaitu :
- Deret bilangan aritmatika
- Deret bilangan geometri
B. Definisi Deret bilangan aritmatika dan deret bilangan geometri
1. Deret Bilangan Aritmatika
Deret aritmatika , yaitu suatu jumlah dari suku – suku barisan bilangan aritmatika .
Jika a , a+b , a+2b , a+3b , a+4b , . . . .a+(n-1)b adalah barisan bilangan aritmatika maka bentuk dari deret aritmatika adalah a+ (a+b) + ( a+2b) + (a+3b) + (a+4b) + . . . .
Rumus Jumlah deret aritmatika suku ke n adalah :
Keterangan :
Sn = jumlah suku ke n
n = Banyaknya suku
b = rasio atau beda
Contoh soal :
- 4 + 9 + 14 + 19 + . . .
Dari deret bilangan diatas , tentukan S30 = . . ?
Penyelesaian :
Diketahui : a = 4 , b = 5
Un = a + ( n – 1 ) b
U30 = 4 + ( 30 -1 ) 5
= 4 + 29.5
= 4 + 145
= 149
maka , S30 adalah :
Sn = 1/2 n ( a+ Un )
S30 = 1/2 . 30 ( 4 + 149 )
= 15 x 153
= 2295
2. Tentukan nilai n dan sn dari deret aritmatika dibawah ini :
3 + 7 + 11 + 15 + . . .+ 199
Penyelesaian :
Diketahui : a = 3 , b = 4
Ditanya :
a.) n = . . .
b.) Sn = . . .
Jawab :
a.) Un = a + ( n -1 ) b
199 = 3 + ( n – 1 ) 4
199 = 3 + 4n -4
199 = -1 + 4n
200 = 4n
50 = n
b.) Sn = 1/2 n ( a+ Un )
S50 = 1/2 .50 ( 3 + 199 )
= 25 ( 202 )
= 5050
3. Tentukan Sn , dari deret aritmatika berikut :
1 + 5 + 9 + 13 + . . . + U10
Penyelesaian :
Diketahui :
a = 1 , b = 4 , n = 10
Ditanya : Sn = . . . ?
Jawab :
Sn = 1/2n [ 2a + ( n – 1 ) b ]
S10 = 1/2.10 [ 2.1 + ( 10 – 1 ) 4 ]
= 5 [ 2 + 9.4 ]
= 5 ( 2 + 36 )
= 190
2. Deret Bilangan Geometri
Deret bilangan geometri , yaitu jumlah dari barisan bilangan geometri .
Jika bentuk barisan bilangan geometri adalah a , a.r , a.r2 , a.r3 , a.r4 , a.r5 . . . . a.rn-1 maka bentuk dari deret bilangan geometri adalah a + a.r + a.r2 + a.r3 + a.r4 + a.r5 . . . .a.rn-1
Jumlah n suku pertama dari deret geometri atau yang dilambangkan dengan Sn , adalah :
Apabila rumus di atas kita kalikan dengan r . maka akan menghasilkan rums sebagai berikut :
Dari kedua persamaan diatas , kita kurangkan maka akan dihasilkan sebagai beriikut :
Sn = a + a.r + a.r2 + a.r3 + a.r4 + a.r5 . . . .a.rn-1
rSn = a.r + a.r2 + a.r3 + a.r4 + a.r5 + a.r6. . . .a.rn-1 + a.rn
_
Sn – rSn = a – a.rn
Sn ( 1 – r ) = a ( 1 – rn )
Sn = a – a rn / 1 – r
Sn = a ( 1 – rn ) / ( 1 – r )
Jadi , dapat kita simpulkan bahwa , rumus jumlah n suku pertama dalam deret geometri adalah :
Untuk lebih jelasnya lagi , maka perhatikan contoh – contoh soal di bawah ini :
1. Diketahui sebuah deret geoetri , dimana U3 = 18 , dan U6 = 486 . Tentukan :
a.) a dan r
b.) S10
Penyelesaian :
a.) U6 = 486 –> a.r 5= 486
U3 = 18 –> a.r2 = 18
U6 / U3 = 486 / 18 —–> a.r 5 / a.r2 = 486 / 18
r3 = 27
r = 3
a.r2 = 18
a.32 = 18
a.9 = 18
a = 2
b.) Sn = a ( 1 – rn ) / 1 – r
S10 = 2 ( 1 – 310 ) / ( 1 – 3 )
S10 = 2 ( -59048 ) / ( -2 )
S10 = 59048
2. Perhatikan deret bilangan geometri berikut:
2 + 6 + 18 + 54 + . . . . .+ 1458 , tentukan Sn !
Penyelesaian :
Diketahui : a = 2 dan r = 3
Jawab :
Langkah pertama mencari n terlebih dahulu , yaitu dengan cara :
Un = a.rn-1
1458 = 2 . 3n-1
1458 /2 = 3n-1
729 = 3n-1
36 = 3n-1
n – 1 = 6
n = 7
Selanjutnya , tinggal masukkan ke dalam rumus :
Sn = a ( 1 – rn ) / 1 – r
S7 = 2 ( 1- 37 ) / 1- 3
S7 = 2 ( 1-2187 ) / -2
S7 = 2187
2. Algoritma Shell Sort
Metode
ini disebut juga dengan metode pertambahan menurun (diminishing
increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun
1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini
mengurutkan data dengan cara membandingkan suatu data dengan data lain
yang memiliki jarak tertentu, kemudian dilakukan penukaran bila
diperlukan. Proses pengurutan dengan metode Shell dapat dijelaskan
sebagai berikut :
Pertama-tama
adalah menentukan jarak mula-mula dari data yang akan dibandingkan,
yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2.
Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua
data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak
yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data
dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data
ke-(j + N / 2).
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
Algoritma metode Shell dapat dituliskan sebagai berikut :
1. Jarak = N
2. Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5. Sudah = true
6. j = 0
7. Selama (j < N – Jarak) kerjakan baris 8 dan 9
8. Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
Data[j + Jarak].
Sudah = true
9. j = j + 1
Berikut coding dalam C++
#include <stdio.h>
#include <conio.h>
void printarray(int arr[100], int n);
void shellsort(int arr[100], int n);
int main()
{
int arr[100],n;
printf(" SHELL SORT \n");
shellsort(arr,n);
getch();
}
void printarray(int arr[100], int n)
{
int i;
printf("\nArray : [ ");
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
printf("]\n");
}
void shellsort(int arr[100], int n)
{
int i,j,k,temp;
printf(" Masukkan Banyak Elemen : "); scanf("%d", &n);
for(i=0;i<n;i++)
{
printf("\nMasukkan elemen ke-%d : ",i+1);
scanf("%d",&arr[i]);
}
printf("\nArray sebelum terurut : [ ");
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
printf("]\n");
for(i=n/2; i>0; i=i/2)
{
for(j=i; j<n; j++)
{
for(k=j-i; k>=0; k=k-i)
{
if(arr[k+i]>=arr[k])
{
break;
}
else
{
temp=arr[k];
arr[k]=arr[k+i];
arr[k+i]=temp;
}
printarray(arr,n);
}
}
}
printf("\nArray setelelah terurut : \n");
for(i=0;i<n;i++)
{
printf("%d\t",arr[i]);
}
}
-Waktu terbaik dalam algoritma shellsort yaitu N/2
-Waktu terburuk dalam algoritma shellsort yaitu N/n
N = banyaknya angka yang ingin di sort
n = N/2
