Analisa
Algoritma
Sorting Data
Disusun
oleh :
Renza Bin Harnata (06.2009.1.05156)
Wahyu
Wulandari Ningsih Wibowo (06.2009.1.05218)
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INFORMASI
INSTITUT TEKNOLOGI ADHI TAMA SURABAYA
2011
Binary Insertion Sort
Algoritma
:
1
i←1
2
selama (i < N) kerjakan baris 3 sampai dengan 14
3
x ← Data[i]
4
l←0
5
r←i–1
6
selama (l<=r) kerjakan baris 7 dan 8
7
m ← (l + r) / 2
8
jika (x < Data[m]) maka r ← m – 1, jika tidak l ← m + 1
9
j←i–1
10
selama ( j >=l) kerjakan baris 11 dan 12
11
Data[j+1] ← Data[j]
12
j←j–1
13
Data[l] ← x
14
I←i+1
void BinaryInsertSort()
{
int
i, j, l, r, m, x;
for
(i=1; i<Max; i++)
{x = Data[i];
l = 0;
r = i - 1;
while(l <= r)
{m = (l + r) / 2;
if(x < Data[m])
r = m - 1;
else
l = m + 1;
}
for(j=i-1;
j>=l; j--)
{Data[j+1] = Data[j];
Data[l]=x;
}
}
}
Perhitungan
eksekusi :
i
= 1 dieksekusi
1 kali
i<Max
dieksekusi n kali
i++
dieksekusi n
kali
x
= Data[i] dieksekusi n
kali
r
= i – 1 dieksekusi
n kali
1<=r dieksekusi n2
kali
m
= (l + r) / 2 dieksekusi n2
kali
r
= m - 1 dieksekusi n2
kali
l
= m + 1 dieksekusi n2
kali
j=i-1 dieksekusi 1 kali
j>=l dieksekusi n2
kali
j-- dieksekusi n2
kali
Data[j+1]
= Data[j] dieksekusi n2
kali
Data[l]=x dieksekusi n2
kali
Jumlah
= 2 + 8n + 4n2
Selection Sort
Algoritma
:
1
i←0
2
selama (i < N-1) kerjakan baris 3 sampai dengan 9
3
k←i
4
j←i+1
5
Selama (j < N) kerjakan baris 6 dan 7
6
Jika (Data[k] > Data[j]) maka k ← j
7
j←j+1
8
Tukar Data[i] dengan Data[k]
9
i←i+1
void SelectionSort()
{
int
i, j, k;
for(i=0;
i<Max-1;i++)
{k = i;
for (j=i+1; j<Max; j++)
{if(Data[k] >
Data[j])
k = j;
Tukar(&Data[i],
&Data[k]);
}
}
}
Perhitungan
eksekusi :
i
= 1 dieksekusi
1 kali
i<Max
dieksekusi
n kali
i++
dieksekusi
n kali
k
= i dieksekusi
n kali
j=i+1 dieksekusi
1 kali
j<Max dieksekusi
n2 kali
j++ dieksekusi
n2 kali
Data[k]
> Data[j] dieksekusi
n2 kali
k
= j dieksekusi
n2 kali
Tukar(&Data[i],
&Data[k]) dieksekusi n2
kali
Jumlah
= 2 + 3n + 5n2
Straight Insertion Sort
Algoritma
:
1
i←1
2
selama (i < N) kerjakan baris 3 sampai dengan 9
3
x ← Data[i]
4
j←i–1
5
selama (x < Data[j]) kerjakan baris 6 dan 7
6
Data[j + 1] ← Data[j]
7
j←j–1
8
Data[j+1] ← x
9
i←i+1
void StraighInsertSort()
{int
i, j, x;
for(i=1;
i<Max; i++)
{x = Data[i];
j = i - 1;
while (x < Data[j])
{Data[j+1] =
Data[j];
j--;
}
Data[j+1] = x;
}
}
Perhitungan
eksekusi :
i
= 1 dieksekusi
1 kali
i<Max
dieksekusi n kali
i++
dieksekusi n
kali
x
= Data[i] dieksekusi n
kali
j
= i – 1 dieksekusi
n kali
x
< Data[j] dieksekusi
n2 kali
Data[j+1]
= Data[j] dieksekusi n2
kali
j-- dieksekusi n2
kali
Data[j+1]
= x dieksekusi n2
kali
Jumlah
= 1 + 4n + 4n2
Bubble sort
Algoritma
:
1
i←0
2
selama (i < N-1) kerjakan baris 3 sampai dengan 7
3
j←N-1
4
Selama (j >= i) kerjakan baris 5 sampai dengan 7
5
Jika (Data[j-1] > Data[j]) maka tukar Data[j-1] dengan Data[j]
6
j←j–1
7
i←i+1
void BubbleSort()
{
int
i, j;
for(i=1;
i<Max; i++)
{ for(j=0; j<=Max-1; j++)
{ if(Data[j] > Data[j+1])
Tukar(&Data[j],
&Data[j+1]);
}
}
}
Perhitungan
eksekusi :
i
= 1 dieksekusi
1 kali
i<Max dieksekusi
n kali
i++
dieksekusi
n kali
j=0 dieksekusi
1 kali
j<=Max-1 dieksekusi
n2 kali
j++ dieksekusi
n2 kali
Tukar(&Data[j-1],
&Data[j]) dieksekusi n2
kali
Jumlah
= 2 + 2n + 3n2
ShellSort
Algoritma
:
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
void ShellSort(int N)
{
int
Jarak, i, j;
bool
Sudah;
Jarak
= N;
while(Lompat
> 1){
Jarak = Jarak / 2;
Sudah = false;
while(!Sudah){
Sudah = true;
for(j=0; j<N-Jarak;
j++){
i = j + Jarak;
if(Data[j]
> Data[i]){
Tukar(&Data[j],
&Data[i]);
Sudah =
false;
}
}
}
}
}
Perhitungan
eksekusi :
Jarak
= N dieksekusi
1 kali
Lompat
> 1 dieksekusi
n kali
Jarak
= Jarak / 2 dieksekusi
n kali
Sudah
= false dieksekusi
n kali
!Sudah dieksekusi
n2 kali
Sudah
= true dieksekusi
n2 kali
j=0 dieksekusi
1 kali
j<N-Jarak dieksekusi
n3 kali
j++ dieksekusi
n3 kali
i
= j + Jarak dieksekusi
n3 kali
Data[j]
> Data[i] dieksekusi
n3 kali
Tukar(&Data[j],
&Data[i]) dieksekusi
n3 kali
Sudah
= false dieksekusi
n3 kali
Jumlah
= 2 + 3n + 2n2+ 6 n3
Algoritma Bubble Sort
Program:
#include<iostream.h>
#define
Max 6
void Tukar (int *a,
int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void main()
{
int i, j,Data[Max];
for(i=0; i<Max;
i++)
{
cout<<"Masukan
Data ke "<<i+1<<" : ";cin>>Data[i];
}
for(i=1; i<Max;
i++)
{
for(j=0; j<=Max-1; j++)
{
if(Data[j] > Data[j+1])
{
Tukar(&Data[j],&Data[j+1]);
}
}
}
cout<<"Setelah
Data Diurutkan"<<endl;
cout<<"--------------------------------"<<endl;
for(i=0; i<Max;
i++)
{
cout<<Data[i]<<"
";
}
}
Tidak ada komentar:
Posting Komentar