1. ALGORITMA BUBBLE SORT (APUNG)
Proses
pengapungan ini dilakukan sebanyak n-1 langkah ( satu langkah disebut juga satu
kali pass) dengan n adalah ukuran larik.
Untuk
mendapatkan larik yang terurut menaik , algoritma pengurutan apung secara
global sebagai berikut :
- untuk setiap pass i=
1, 2, ..., n – 1, lakukan :
- Mulai dari elemen k =
n, n – 1, ..., i+1, lakukan:
- Bandingkan L[k]
dengan L[k – 1]
- Pertukarkan L[k]
dengan L[k – 1] jika L[k] < L[k – 1]
Procedure
BubbleSort1(input/output L : LarikInt, input n: integer )
{mengurutkan
larik L[1..n] sehingga terurut menaik dengan metode pengurutan apung}
k.awal
: Elemen larik L sudah terdefinisi nilai – nilainya
k.akhir
: Elemen larik L terurut menaik sedemikian sehingga L[1]
<=L[2]<=...<=L[n]
deklarasi
i, k, temp : integer
Algoritma
:
For
i←1 to n-1 do
For k←n downto i+1 do
If L[k] < L[k-1] then
temp
← L[k]
L[k]
← L[k – 1]
L[k
– 1]← temp
Endif
endfor
endfor
Contoh Scriptnya pada bahasa C++ :
#include<iostream>
#include<iostream>
using namespace std;
int main(){
//declaring array
int array[5];
cout<<"masukan 5
angka random : "<<endl;
for(int i=0; i<5; i++)
{
//Taking input in array
cin>>array[i];
}
cout<<endl;
cout<<"Input array :
"<<endl;
for(int j=0; j<5; j++)
{
//Displaying Array
cout<<"\t\t\tValue
at "<<j<<" Index:
"<<array[j]<<endl;
}
cout<<endl;
// Bubble Sort Starts Here
int temp;
for(int i2=0; i2<=4; i2++)
{
for(int j=0; j<4; j++)
{
//Swapping element in if
statement
if(array[j]>array[j+1])
{
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
// Displaying Sorted array
cout<<" Sorted Array : "<<endl;
for(int i3=0; i3<5; i3++)
{
cout<<"\t\t\tValue at
"<<i3<<" Index: "<<array[i3]<<endl;
}
return 0;
}
2. ALGORITMA
SELECTION SORT (SELEKSI)
Algoritma
pengurutan ini memiliki gagasan dasar , yaitu : memilih elemen maksimun /
minimum dari larik, lalu menempatkan elemen tersebut itu pada awal / akhir
larik ( elemen terujung). Selanjutnya elemen terujung “diisolasi “ dan tidak
disertakan pada proses selanjutnya.
Algoritma
pengurutan untuk maksimum ditulis secara garis besar sebagai berikut :
- Jumlah pass = n-1
- Untuk setiap pass i =1, 2, .., jumlah pass
dilakukan :
#
cari elemen terbesar (maks) mulai dari elemen ke – 1 sampai elemenke – n;
#
Pertukarkan maks dengan elemen ke – n;
#
Kurangi n satu ( karena elemen ke – n sudah terurut)
Procedure
SelectionSort1(input/output L : LarikInt, input n : integer )
k.awal
: elemen larik L sudah terdefinisi harganya
k.akhir : elemen larik
L terurut menaik sedemikian sehingga L[1]<=L[2]<=... <= L[n]
deklarasi
i, j, imaks, maks, temp
: integer
Algoritma
For
i←n downto 2 do { jumlah pass sebanyak n-1}
{cari elemen maks pada L[1...i]
imaks ← 1 {elemen pertama
diasumsikan sebagai maks}
maks ← L[1]
for j←2 to i do
if L[j] > maks then
imaks←j
maks←L[j]
endif
endfor
{pertukarkan
maks dengan L[i]}
temp←L[i]
L[i]←maks
L[imaks]←temp
Endfor
·
Algoritma Pengurutan Seleksi Minimum
Procedure SelectionSort2 (input/output L
: LarikInt, input n : interger)
{mengurutkan elemen-elemen larik L[1..n]
sehingga tersusun menurun dengan metode pengurutan seleksi minimum}
DEKLARASI
i
: interger {pencacah pass}
j
: interger {pencacah untuk mencari nilai
maksimum}
imin :
interger {indeks yang berisi
nilai minimu sementara}
ALGORITMA
for
i ← n downto 2 do {jumlah pass sebanyak n – 1 kali}
{cari
elemen terkecil pada elemen L[1..i]}
imin ←1
for j ← 2 to i do
if L[j] > L[imin]
then
imin ← L[j]
endif
endfor
{pertukaran L[imin] dengan L[i]}
Tukar (L[imin], L[i]);
Endfor
·
Contoh Scriptnya pada Bahasa C++ :
#include<iostream>
#include<conio.h>
using
namespace std;
template
<class T>
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]) //for descending order use 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
elmen:\n";
cin>>n;
cout<<"\nmasukan angka:\n";
for(i=0;i<n;i++)
{
cout<<"\nmasukan:";
cin>>a[i];
}
s_sort(a,n);
cout<<"\nAfter Sorting\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<"\t";
}
getch();
return 0;
}
3. ALGORITMA
INSERTION SORT (SISIP)
Salah
satu algoritma sorting yang paling sederhana adalah insertion sort.Ide dari
algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut
ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan
kartu. Anggaplah ingin mengurutkan satu set kartu dari kartu yang bernilai
paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja,
sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan dan atas
kebawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang
diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri
atas meja pertama dan letakkan pada meja kedua.Ambil kartu kedua
darimejapertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian
letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut akan
berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan
pada meja kedua.
Algoritma
insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua
bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja
kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan
kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah
diurutkan.Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen
yang tersisa pada bagian array yang belum diurutkan.
Kelemahan
metode ini adalah jika ada data pada posisi ke-1000, maka dibutuhkan pergeseran
elemen sebanyak 998 kali.
Contoh
penulisan dalam algoritma:
procedure UrutSisip(input/output L:
Larik, input N : integer)
DEKLARASI
K
: integer {pencacah langkah}
J
: integer {pencacah untuk penelusuran larik}
Temp
: integer {peubah bantu untuk agar L[K] tidak ditimpa selama pergeseran}
ALGORITMA
{elemen L[1] dianggap sudah
terurut}
for K ← 2 to N do {mulai dari
langkah 2 sampai langkah N}
Temp ← L[K] {ambil
elemen L[K] supaya tidak ditimpa pergeseran}
{cari posisi yang tepat
untuk L[K] di dalam L[1..K-1] sambil menggeser}
J ← K – 1
while Temp ≤ L[J] AND
(J > 1) do
L[J+1] ← L[J]
J ← J-1
Endwhile
if Temp ≥ L[J] then
L[J+1] ← Temp
Else
L[J+1] ← L[J]
L[J] ← Temp
endif
endfor
·
Contoh Scriptnya pada Bahasa C++ :
#include <conio.h>
using namespace std;
int main()
{
int a[10], i, j, k,
temp;
cout<<"masukan angka:\n";
for (i = 0; i < 16;
i++)
{
cin>>a[i];
}
for (i = 1; i < 10;
i++)
{
for (j = i; j
>= 1; j--)
{
if (a[j] <
a[j-1])
{
temp =
a[j];
a[j] =
a[j-1];
a[j-1] =
temp;
}
else
break;
}
}
cout<<"sorted array\n"<<endl;
for (k = 0; k < 16;
k++)
{
cout<<a[k]<<endl;
}
getch();
}
4. ALGORITMA
SHELL SORT
Algoritma
pengurutan shell ini ditemukan oleh Donald Shell pada tahun1959. Algoritma ini
merupakan perbaikan terhadap pengurutan sisip.Jika pada metode pengurutan
sisip, jika ada data pada posisi
ke-1000, maka dibutuhkan pergeseran elemen sebanyak 998 kali.
Untuk
mengurangi pergeseran terlalu jauh, harus mengurutkan larik setiap k elemen
dengan metode pengurutan shell, misalkan kita urutkan setiap 5 elemen (k kita
namakan juga step atau increment). Selanjutnya, kita gunakan nilai step yang
lebih kecil, misalnya k = 3, lalu kita
urut setiap 3 elemen. Begitu seterusnya sampai nilai k = 1. Karena nilai step
selalu berkurang maka algoritma pengurutan Shell kadang – kadang dinamakan juga
algoritma pengurutan kenaikan yang berkurang (diminishing increment sort).
Contoh
:
Procedure InSort(input/output L :
LarikInt, input n,start,step : interger)
{mengurutkan elemen larik
L[start..n] sehingga tersusun menaik dengan metode pengurutan sisip yang
dimodifikasi untuk shell sort}
DEKLARASI
i :
interger {pencacah step}
j :
interger {pencacah untuk
penelusuran larik}
y :
interger {peubah bantu yang
menyimpan nilai L[k]}
ketemu : Boolean {untuk menyatakan posisi penyisipan
ditemukan}
ALGORITMA
{elemen L[start] dianggap sudah
terurut}
i← start + step
while i ≤ n do
y← L[i]
{sisipkan L[i] ke dalam bagian yang
sudah terurut }
{cari posisi yang tepat untuk y di
dalam L[start..i-1] sambil menggeser}
j← i – step
ketemu← false
while (j ≥1) AND (not ketemu) do
if y < L[j] then
L[j+step] ←
L[j]
j← j-step
else
ketemu←
true
endif
endwhile
{j< 1 or ketemu}
L[j+step] ← y {sisipkan y pada
tempat yang sesuai}
i← i + step
endwhile
·
Contoh Scriptnya pada C++ :
using namespace std;
#include <iostream>
#include <conio.h>
void read(int a[10], int n){
cout<<"Reading\n";
for(int i = 0; i
< n; i++)
cin>>a[i];
}
void display(int a[10], int n){
for(int i = 0; i
< n; i++)
cout<<a[i]<<"\t";
}
void shell(int a[10], int n){
int gap = n/2;
do{
int
swap;
do{
swap = 0;
for(int i = 0; i < n - gap; i++)
if(a[i]
> a[i+gap])
{
int t = a[i];
a[i] = a[i+gap];
a[i+gap] = t;
swap = 1;
}
}
while(swap);
}
while(gap = gap
/ 2);
}
int main(){
int a[10];
int n;
cout<<"enter n\n";
cin>>n;
read(a,n);
cout<<"before sorting\n";
display(a,n);
shell(a,n);
cout<<"\nafter sorting\n";
display(a,n);
getch();
}
5. ALGORITMA MERGE SORT\
Contoh Script pada C++ :
using namespace std;
#include <iostream>
#include <conio.h>
void merge(int *,int, int , int );
void mergesort(int *a, int low, int
high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return;
}
void merge(int *a, int low, int
high, int mid)
{
int i, j, k, c[50];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
c[k] = a[i];
k++;
i++;
}
else
{
c[k] = a[j];
k++;
j++;
}
}
while (i <= mid)
{
c[k] = a[i];
k++;
i++;
}
while (j <= high)
{
c[k] = a[j];
k++;
j++;
}
for (i = low; i < k; i++)
{
a[i] = c[i];
}
}
int main()
{
int a[20], i, b[20];
cout<<"enter the
elements\n";
for (i = 0; i < 5; i++)
{
cin>>a[i];
}
mergesort(a, 0, 4);
cout<<"sorted array\n";
for (i = 0; i < 5; i++)
{
cout<<a[i];
}
cout<<"\nenter the
elements\n";
for (i = 0; i < 5; i++)
{
cin>>b[i];
}
mergesort(b, 0, 4);
cout<<"sorted array\n";
for (i = 0; i < 5; i++)
{
cout<<b[i];
}
getch();
}
6. ALGORITMA QUICK SORT
Contoh Script pada C++ :
#include <iostream>
void quickSort(int a[], int first,
int last);
int pivot(int a[], int first, int
last);
void swap(int& a, int& b);
void swapNoTemp(int& a,
int& b);
void print(int array[], const
int& N);
using namespace std;
int main()
{
int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 };
int N = sizeof(test)/sizeof(int);
cout << "Size of test array :" << N << endl;
cout << "Before sorting : " << endl;
print(test, N);
quickSort(test, 0, N-1);
cout << endl << endl << "After sorting : "
<< endl;
print(test, N);
return 0;
}
/**
* Quicksort.
* @param a - The array to be sorted.
* @param first - The start of the sequence to
be sorted.
* @param last - The end of the sequence to be
sorted.
*/
void quickSort( int a[], int first,
int last )
{
int pivotElement;
if(first < last)
{
pivotElement = pivot(a,
first, last);
quickSort(a, first, pivotElement-1);
quickSort(a, pivotElement+1, last);
}
}
/**
* Find and return the index of pivot element.
* @param a - The array.
* @param first - The start of the sequence.
* @param last - The end of the sequence.
* @return - the pivot element
*/
int pivot(int a[], int first, int
last)
{
int p = first;
int pivotElement = a[first];
for(int i = first+1 ; i <= last ; i++)
{
/* If you want to sort the list in the
other order, change "<=" to ">" */
if(a[i] <= pivotElement)
{
p++;
swap(a[i], a[p]);
}
}
swap(a[p], a[first]);
return p;
}
/**
* Swap the parameters.
* @param a - The first parameter.
* @param b - The second parameter.
*/
void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
/**
* Swap the parameters without a temp variable.
* Warning! Prone to overflow/underflow.
* @param a - The first parameter.
* @param b - The second parameter.
*/
void swapNoTemp(int& a,
int& b)
{
a -= b;
b += a;// b gets the original value of a
a = (b - a);// a gets the original value of b
}
/**
* Print an array.
* @param a - The array.
* @param N - The size of the array.
*/
void print(int a[], const int&
N)
{
for(int i = 0 ; i < N ; i++)
cout << "array["
<< i << "] = " << a[i] << endl;
}
7. ALGORITMA HEAP SORT
Contoh Script pada C++ :
#include <iostream>
#include <conio.h>
using namespace std;
void max_heapify(int *a, int i, int
n)
{
int j, temp;
temp = a[i];
j = 2*i;
while (j <= n)
{
if (j < n && a[j+1] >
a[j])
j = j+1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void heapsort(int *a, int n)
{
int i, temp;
for (i = n; i >= 2; i--)
{
temp = a[i];
a[i] = a[1];
a[1] = temp;
max_heapify(a, 1, i - 1);
}
}
void build_maxheap(int *a, int n)
{
int i;
for(i = n/2; i >= 1; i--)
{
max_heapify(a, i, n);
}
}
int main()
{
int n, i, x;
cout<<"Masukan jumlah elmen:\n";
cin>>n;
int a[20];
for (i = 1; i <= n; i++)
{
cout<<"masukan
angka:"<<(i)<<endl;
cin>>a[i];
}
build_maxheap(a,n);
heapsort(a, n);
cout<<"sorted output\n";
for (i = 1; i <= n; i++)
{
cout<<a[i]<<endl;
}
getch();
}
8. ALGORITMA EXHANGE SORT
Contoh Script pada C++ :
using namespace std;
#include<iostream>
int main(void)
{
int array[5]; // An
array of integers
int length = 5; // Lenght
of the array
int i, j;
int temp;
//Some
input
for (i = 0; i < 5; i++)
{
cout << "masukan
angka: ";
cin >> array[i];
}
//Algorithm
for(i = 0; i < (length -1); i++)
{
for (j=(i + 1); j <
length; j++)
{
if (array[i] <
array[j])
{
temp =
array[i];
array[i] = array[j];
array[j]
= temp;
}
}
}
//Some
output
for (i = 0; i < 5; i++)
{
cout << array[i]
<< endl;
}
}
9. ALGORITMA TREE SORT
Contoh Script pada C++ :
#include<iostream>
using namespace std;
struct tree{
int info;
tree *Left, *Right;
};
tree *root;
class TreeSort{
public:
int no_of_elements;
int elements[10];
public:
void getarray();
void sortit();
void insert1(int);
tree *insert2(tree *, tree *);
void display(tree *);
};
void TreeSort::getarray(){
cout<<"Berapa banyak elmen yang anda inginkan? ";
cin>>no_of_elements;
cout<<"masukan angka: ";
for(int i=0;i<no_of_elements;i++){
cin>>elements[i];
}
}
void TreeSort::sortit(){
for(int i = 0; i <
no_of_elements; i++){
insert1(elements[i]);
}
}
tree* TreeSort::insert2(tree
*temp,tree *newnode){
if(temp==NULL){
temp=newnode;
}
else if(temp->info < newnode->info){
insert2(temp->Right,newnode);
if(temp->Right==NULL)
temp->Right=newnode;
}
else{
insert2(temp->Left,newnode);
if(temp->Left==NULL)
temp->Left=newnode;
}
return temp;
}
void TreeSort::insert1(int n){
tree *temp=root,*newnode;
newnode=new tree;
newnode->Left=NULL;
newnode->Right=NULL;
newnode->info=n;
root=insert2(temp,newnode);
}
/* Inorder traversal */
void TreeSort::display(tree *t =
root){
if(root==NULL){
cout<<"Nothing to
display";
}else
if(t!=NULL){
display(t->Left);
cout<<t->info<<"
";
display(t->Right);
}
}
int main(){
TreeSort TS;
TS.getarray();
TS.sortit();
TS.display();
return 0;
}
(Dipost oleh EVI IRFAN BUDIANA - A710140033 - PENDIDIKAN TEKNIK INFORMATIKA)
(Dipost oleh EVI IRFAN BUDIANA - A710140033 - PENDIDIKAN TEKNIK INFORMATIKA)
