algo2 tugas-1
Beberapa contoh algoritma sorting
- BubbleSort
- Proses Pengurutan:
- Bubble Sort adalah nama yang diberikan pada prosedur untuk mengatur sekelompok bilangan dengan urutan dari kecil ke besar.
- Untuk mengurutkan bilangan diperlukan variabel array yang digunakan untuk menampung semua bilangan yang akan diurutkan.
- Proses pengurutan dilakukan dengan membandingkan semua elemen array satu persatu.
- Dalam metode bubble sort, pengurutan demulai dengan membandingkan elemen pertama untuk mendapatkan angka terbesar. Lalu angka tersebut ditempatkan pada elemen terakhir.
berikut adalah contoh sourcecode dalam java:
// bubbleSort.java // demonstrates bubble sort // to run this program: C>java BubbleSortApp //////////////////////////////////////////////////////////////// class ArrayBub { private long[] a; // ref to array a private int nElems; // number of data items //-------------------------------------------------------------- public ArrayBub(int max) // constructor { a = new long[max]; // create the array nElems = 0; // no items yet } //-------------------------------------------------------------- public void insert(long value) // put element into array { a[nElems] = value; // insert it nElems++; // increment size } //-------------------------------------------------------------- public void display() // displays array contents { for(int j=0; j<nElems; j++) // for each element, System.out.print(a[j] + " "); // display it System.out.println(""); } //-------------------------------------------------------------- public void bubbleSort() { int out, in; for(out=nElems-1; out>1; out--) // outer loop (backward) for(in=0; in<out; in++) // inner loop (forward) if( a[in] > a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() //-------------------------------------------------------------- private void swap(int one, int two) { long temp = a[one]; a[one] = a[two]; a[two] = temp; } //-------------------------------------------------------------- } // end class ArrayBub //////////////////////////////////////////////////////////////// class BubbleSortApp { public static void main(String[] args) { int maxSize = 100; // array size ArrayBub arr; // reference to array arr = new ArrayBub(maxSize); // create the array arr.insert(77); // insert 10 items arr.insert(99); arr.insert(44); arr.insert(55); arr.insert(22); arr.insert(88); arr.insert(11); arr.insert(00); arr.insert(66); arr.insert(33); arr.display(); // display items arr.bubbleSort(); // bubble sort them arr.display(); // display them again } // end main() } // end class BubbleSortApp //////////////////////////////////////////////////////////////// - QuickSort
- Algoritma quick sort diperkenalkan pertama kali oleh C.A.R.
- Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel kanan.
- Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.
- Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri.
Hoare pada tahun 1960, dan dimuat sebagai artikel di “Computer Journal 5” pada April 1962. Quick sort adalah algoritma sorting
yang berdasarkan pembandingan dengan metoda divide-and-conqueror.
Disebut Quick Sort, karena Algoritma quick sort mengurutkan dengan sangat cepat. Quick sort disebut juga dengan partition
exchange sort, karena konsepnya membuat partisi-partisi, dan
sort dilakukan per partisi
Dalam algoritma quick sort, pemilihan pivot adalah hal yang
menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan
pivot : - MergeSort
Berikut contoh Sourcecode dalam java:
</code>class QuickSort{
public static void main(String[] a){
System.out.println(new QS().Start(10));
}
}
// This class contains the array of integers and
// methods to initialize, print and sort the array
// using Quicksort
class QS{
int[] number ;
int size ;
// Invoke the Initialization, Sort and Printing
// Methods
public int Start(int sz){
int aux01 ;
aux01 = this.Init(sz);
aux01 = this.Print();
System.out.println(9999);
aux01 = size - 1 ;
aux01 = this.Sort(0,aux01);
aux01 = this.Print();
return 0 ;
}
// Sort array of integers using Quicksort method
public int Sort(int left, int right){
int v ;
int i ;
int j ;
int nt;
int t ;
boolean cont01;
boolean cont02;
int aux03 ;
t = 0 ;
if (left < right){
v = number[right] ;
i = left - 1 ;
j = right ;
cont01 = true ;
while (cont01){
cont02 = true ;
while (cont02){
i = i + 1 ;
aux03 = number[i] ;
if (!(aux03<v)) cont02 = false ;
else cont02 = true ;
}
cont02 = true ;
while (cont02){
j = j - 1 ;
aux03 = number[j] ;
if (!(v < aux03)) cont02 = false ;
else cont02 = true ;
}
t = number[i] ;
number[i] = number[j] ;
number[j] = t ;
//aux03 = i + 1 ;
if ( j < (i+1)) cont01 = false ;
else cont01 = true ;
}
number[j] = number[i] ;
number[i] = number[right] ;
number[right] = t ;
nt = this.Sort(left,i-1);
nt = this.Sort(i+1,right);
}
else nt = 0 ;
return 0 ;
}
// Print array of integers
public int Print(){
int j ;
j = 0 ;
while (j < (size)) {
System.out.println(number[j]);
j = j + 1 ;
}
return 0 ;
}
// Initialize array of integers
public int Init(int sz){
size = sz ;
number = new int[sz] ;
number[0] = 20 ;
number[1] = 7 ;
number[2] = 12 ;
number[3] = 18 ;
number[4] = 2 ;
number[5] = 11 ;
number[6] = 6 ;
number[7] = 9 ;
number[8] = 19 ;
number[9] = 5 ;
return 0 ;
}
}
<code>
</code>//Copyright (c) 1998, Arthur Gittleman
//This example is provided WITHOUT ANY WARRANTY either expressed or implied.
/* Implements the recursive merge sort
* algorithm to sort an array that the user
* inputs on the command line.
*/
public class MergeSort {
public static void mergeSort (int [] data, int left, int right) {
if (left < right) {
int middle = (left+right)/2;
mergeSort(data,left,middle);
mergeSort(data,middle+1,right);
merge(data,left,middle,middle+1,right);
}
}
public static void merge(int[] data, int l1, int r1, int l2, int r2) {
int oldPosition = l1;
int size = r2-l1+1;
int [] temp = new int[size];
int i = 0;
while (l1<=r1 && l2<=r2) {
if (data[l1] <= data[l2])
temp[i++] = data[l1++];
else
temp[i++] = data[l2++];
}
if (l1 > r1)
for (int j=l2; j<=r2; j++)
temp[i++] = data[l2++];
else
for (int j=l1; j<=r1; j++)
temp[i++] = data[l1++];
System.arraycopy(temp,0,data,oldPosition,size);
}
public static void display(int [] anArray) {
System.out.print("{");
for (int i=0; i<anArray.length; i++) {
if (i!=0) System.out.print(",");
System.out.print(anArray[i]);
}
System.out.println("}");
}
public static void main (String [] args) {
int [] data = new int[args.length];
for (int i=0; i < data.length; i++)
data[i] = Integer.parseInt(args[i]);
mergeSort(data,0,data.length-1);
display(data);
}
}
<code>
Leave a Comment
