Dalam Ilmu Komputer, Algoritma Sorting merupakan algoritma yang menempatkan elemen list pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerikal dan urutan lexicographical.
Sorting yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritma lain seperti pencarian dan penggabungan yang membutuhkan list terurut untuk berjalan dengan sempurna, yang juga sering digunakan untuk Canonicalisisasi data dan menghasilkan output yang dapat dibaca manusia. Untuk lebih lanjutnya, output harus melengkapi dua syarat ini:
1. Output merupakan urutan yang tidak menurut (nondecreasing) (setiap elemen tidak lebih kecil dari elemen sebelumnya menurut dari urutan keseluruhan yang diinginkan.
2. Output merupakan permutasi (pengurutan kembali) dari inputan yang diberikan.
Sejak permulaan komputasi, masalah pengurutan ini telah menarik penelitian yang serius, mungkin dikarenakan kerumitan dari penyelesaian secara efisien disamping mudah, dan dengan statemen yang kita mengerti.
Sebagai contoh, bubble sort pertama sekali ditemukan pada tahun 1956.[1] Walaupun banyak yang memperkirakan masalahnya telah terselesaikan, banyak algoritma sorting baru yang masih ditemukan samap sekarang (sebagai contoh, Library Sort yang baru dipublikasikan pertama sekali pada tahun 2006).
Algoritma sorting sangat umum pada setiap kelas pengenalan bidang Ilmu Komputer, dimana banyaknya algoritma untuk masalah ini menyediakan pengenalan awal mengenai banyaknya konsep algoritma inti, seperti Notasi Big O, Algoritma Pembagi, Struktur Data, Algoritma Acak, Analisa Best, Worst, Average Case, Running Time Calculation, dan Batas Atas dan Bawah.
Sorting yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritma lain seperti pencarian dan penggabungan yang membutuhkan list terurut untuk berjalan dengan sempurna, yang juga sering digunakan untuk Canonicalisisasi data dan menghasilkan output yang dapat dibaca manusia. Untuk lebih lanjutnya, output harus melengkapi dua syarat ini:
1. Output merupakan urutan yang tidak menurut (nondecreasing) (setiap elemen tidak lebih kecil dari elemen sebelumnya menurut dari urutan keseluruhan yang diinginkan.
2. Output merupakan permutasi (pengurutan kembali) dari inputan yang diberikan.
Sejak permulaan komputasi, masalah pengurutan ini telah menarik penelitian yang serius, mungkin dikarenakan kerumitan dari penyelesaian secara efisien disamping mudah, dan dengan statemen yang kita mengerti.
Sebagai contoh, bubble sort pertama sekali ditemukan pada tahun 1956.[1] Walaupun banyak yang memperkirakan masalahnya telah terselesaikan, banyak algoritma sorting baru yang masih ditemukan samap sekarang (sebagai contoh, Library Sort yang baru dipublikasikan pertama sekali pada tahun 2006).
Algoritma sorting sangat umum pada setiap kelas pengenalan bidang Ilmu Komputer, dimana banyaknya algoritma untuk masalah ini menyediakan pengenalan awal mengenai banyaknya konsep algoritma inti, seperti Notasi Big O, Algoritma Pembagi, Struktur Data, Algoritma Acak, Analisa Best, Worst, Average Case, Running Time Calculation, dan Batas Atas dan Bawah.
Berikut ini saya hendak share beberapa contoh algoritma sorting dengan bahasa pemprograman java yang saya pisah dengan tanda ( === ).
Semoga Bermanfaat.
==========================================================
package Sorting;
import java.util.*;
import java.io.*;
public class AcakArray {
public
static void main(String[] args)throws Exception {
DataInputStream
input=new DataInputStream(System.in);
System.out.println("Berapa
banyaknya angka yang diacak?");
String
masuk=input.readLine();
int
i=Integer.parseInt(masuk);
int
x=9;
int
[]acak=new int[i];
int
y;
for(y=0;y<acak.length;y++){
acak[y]=(int)(Math.random()*x+1);
}
System.out.println("Array
sebelum diurutkan :");
for(y=0;y<acak.length;y++){
System.out.println(acak[y]);
}
Arrays.sort(acak);
System.out.println("Hasil
pengurutan array :");
for(y=0;y<acak.length;y++){
System.out.println(acak[y]);
}
}
}
======================================================================================
package Sorting;
/**
*
* @author Minerva
*/
public class ArraySortBasic {
static int cnt =
0;
static int chg =
0;
static boolean
banding(double v, double w) {
cnt++;
return v <
w;
}
static void
tukar(double[] a, int i, int j) {
double t =
a[i];
a[i] = a[j];
a[j] = t;
chg++;
}
static void
bandingTukar(double[] a, int i, int j) {
if
(banding(a[j], a[i])) {
tukar(a,
i, j);
}
}
static void
sort(double[] a, int l, int r) {
for (int i = l
+ 1; i <= r; i++) {
for (int j
= i; j > l; j--) {
bandingTukar(a, j - 1, j);
}
}
}
static void insertion(double[] a, int l, int r)
{ int i;
for (i = r; i >
l; i--)
bandingTukar(a, i-1, i);
for (i = l+2; i
<= r; i++)
{ int j = i;
double v = a[i];
while
(banding(v, a[j-1]))
{ a[j] =
a[j-1]; j--; }
a[j] = v;
}
}
static void shell(double[] a, int l, int r)
{ int h;
for (h = 1; h <= (r-l)/9; h = 3*h+1);
for ( ; h > 0;
h /= 3)
for (int i =
l+h; i <= r; i++)
{ int j = i;
double v = a[i];
while (j
>= l+h && banding(v, a[j-h]))
{ a[j] =
a[j-h]; j -= h; }
a[j] = v;
}
}
static void
selection(double[] a, int l, int r) {
for (int i =
l; i < r; i++) {
int min =
i;
for (int j
= i + 1; j <= r; j++) {
if
(banding(a[j], a[min])) {
min = j;
}
}
bandingTukar(a, i, min);
}
}
static void bubble(double[] a, int l, int r)
{ for (int i = l; i
< r; i++)
for (int j = r;
j > i; j--)
bandingTukar(a, j-1, j);
}
public static void
main(String[] args) {
int N =
10;//Integer.parseInt(args[0]);
double a[] =
new double[N];
for (int i
= 0; i < N; i++) {
a[i] =
Math.random();
}
shell(a, 0, N
- 1);
if (N <
100) {
for (int i = 0; i < N; i++) {
System.out.println(a[i] + "");
}
}
System.out.println("Compares used: " + cnt);
System.out.println("Exchange used: " + chg);
}
}
===================================================================
package Sorting;
/**
*
* @author Minerva
*/
import java.util.Scanner;
public class BubbleSort{
public void
bubbleSort(float baris2[]){
for(int
i=0;i<baris2.length;i++){
for(int
elemen=0;elemen<baris2.length-1;elemen++){
if(baris2[elemen]>baris2[elemen+1])
tukar(baris2,elemen,elemen+1);
}
}
}
public void tukar(float baris3[],int satu, int dua){
float temp;
temp =
baris3[satu];
baris3[satu]=baris3[dua];
baris3[dua]
= temp;
}
public static void main(String args[]){
Scanner masuk=new
Scanner(System.in);
BubbleSort x = new
BubbleSort();
float nilai[]=new
float[5];
System.out.println("Masukan 5 buah data nilai");
for (int i =
0; i<5;i++){
System.out.print((i+1)+" :");
nilai[i]=masuk.nextFloat();
}
System.out.println("Data nilai yang dimasukan");
for
(int i = 0;i<5;i++)
System.out.println(nilai[i]);
System.out.println("Data hasil pengurutan");
x.bubbleSort(nilai);
for (int i=0;i<5;i++)
System.out.println(nilai[i]);
}
}
/*
* To change this
template, choose Tools | Templates
* and open the
template in the editor.
*/
=======================================================
package Sorting;
/**
*
* @author Minerva
*/
public class heap_Sort {
public static void
main(String a[]){
int
i;
int arr[] = {1,3,4,5,2};
System.out.println("\n HEAP SORT \n---------------\n");
System.out.print("
NILAI SEBELUM SORTING = ");
for
(i = 0; i < arr.length; i++)
System.out.print(" "+ arr [i]);
for(i=arr.length;
i>1; i--){
fnSortHeap(arr,
i - 1);
}
System.out.print("\n
NILAI SETELAH SORTING = " );
for
(i = 0; i < arr.length; i++)
System.out.print(" " + arr[i]);
}
public
static void fnSortHeap(int array[], int dr) {
int i,
ar;
int ab, ac,
ad, akar, temp;
akar =
(dr-1)/2;
for(ar = akar; ar >= 0; ar--){
for(i=akar;i>=0;i--)
{
ab = (2*i)+1;
ac = (2*i)+2;
if((ab
<= dr) && (ac <= dr)){
if(array[ac] >= array[ab])
ad = ac;
else
ad = ab; }
else{
if(ac > dr)
ad = ab;
else
ad = ac;}
if(array[i] < array[ad]){
temp =
array[i];
array[i] = array[ad];
array[ad] = temp; }
}}
temp =
array[0];
array[0]
= array[dr];
array[dr]
= temp;
return;
}
}
/*
* To change this
template, choose Tools | Templates
* and open the
template in the editor.
*/
=======================================================
package Sorting;
import java.io.*;
/**
*
* @author Minerva
*/
public class insertionSort {
final static int Nmax= 5;
public static void insertionSort(int L[]){
for (int
i=Nmax-1;i>=1;i--) {
for (int
j=i-1;j>=0;j--) {
if
(L[i]<L[j]) {
int c
= L[i];
L[i] =
L[j];
L[j] =
c;
}
}
}
}
public static void main (String args []) {
BufferedReader in
= new BufferedReader (new InputStreamReader (System.in));
int L[] = new int
[Nmax];
try {
for (int
i=0;i<Nmax;i++) {
System.out.print("Enter an integer :");
L[i] =
Integer.parseInt(in.readLine());
}
//Insertion_Ascending(L);
insertionSort(L);
for (int
i=0;i<Nmax;i++) {
System.out.print(L[i]+" ");
}
}
catch (Exception
e) {
System.out.println("ERROR ada kesalahan dalam input");
}
}
}
=================================================================
/*
* To change this
template, choose Tools | Templates
* and open the
template in the editor.
*/
/**
*
* @author Minerva
*/
package Sorting;
public class mergeSort {
public static void
mergeSort_srt(int array[],int lo,int n){
int low = lo;
int high = n;
if(low>=high){
return;
}
int
middle=(low+high)/2;
mergeSort_srt(array,low,middle);
mergeSort_srt(array,middle+1,high);
int
end_low=middle;
int start_high=middle+1;
while((lo<=end_low)&&(start_high<=high)){
if(array[low]<array[start_high]){
low++;
}else{
int
Temp=array[start_high];
for(int k = start_high-1;k>=low;k--){
array[k+1]=array[k];
}
array[low]=Temp;
low++;
end_low++;
start_high++;
}
}
}
public static void main(String a[]) {
int i;
int array[] = {5,9,8,7,4,3};
for(i=0;i<array.length;i++)
System.out.print(array[i]+ "
");
System.out.println("\n");
mergeSort_srt(array,0,array.length-1);
System.out.println("Values after the sort:\n");
for(i=0;i<array.length;i++)
System.out.print(array[i]+ "
");
System.out.println("\n");
System.out.println("PAUSE");
}
}
package Sorting;
/**
*
* @author Minerva
*/
public class QuickSort {
private int[] data; // array of values
private static int
[] list;
private static int
elem;
private static int
mid;
public
static void quicksort( int [] array )
{
quicksort
(array, 0, array.length - 1);
}
public
static void quicksort( int [] array, int left, int right )
{
int
leftPtr = left;
int
rightPtr = right;
if(
left < right )
{
int
pivot = array[left];
while
(leftPtr < rightPtr)
{
while(
(array[leftPtr] <= pivot) &&
(leftPtr < right))
leftPtr++;
while(
array[rightPtr] > pivot && rightPtr > left)
rightPtr--;
if(
leftPtr < rightPtr )
swap
( array, leftPtr, rightPtr );
}
swap
( array, left, rightPtr );
printArrayInQuick
(array, rightPtr);
quicksort(
array, left, rightPtr - 1 );
quicksort(
array, rightPtr + 1, right );
}
}
public
static boolean checkSort (int [] array)
{
if
(array.length <= 1)
return
true;
for
(int i = 1; i <= array.length-1; i++)
if
(array[i] < array[i-1])
return
false;
return
true;
}
public
static void swap ( int [] array, int index1, int index2 )
{
int
tmp = array[index1];
array[index1]
= array[index2];
array[index2]
= tmp;
}
public
static void printArray (int [] array)
{
if
(array.length > 0)
System.out.print
("{ " + array[0]);
for
(int i = 1; i < array.length; i++)
System.out.print
(", " + array[i]);
if
(array.length > 0)
System.out.println
(" }");
}
public
static void printArrayInQuick (int [] array, int pivot)
{
printArray
(array);
if
(array.length > 0)
System.out.print
(" " );
int
i;
for
(i = 1; i < array.length; i++)
if
(array[i-1] < 10)
if
(i-1 == pivot)
System.out.print
("^ " );
else
System.out.print
(" ");
else
if
(i-1 == pivot)
System.out.print
("^ ");
else
System.out.print
(" ");
if
(i-1 == pivot)
System.out.print("^");
System.out.println();
}
public static int findMe(int [] list, int low, int high, int
elem) {
if
(low<high) {
mid = (low
+ high) /2;
if
(elem<list[mid]) {
return
findMe(list, low, mid, elem);
}
if
(elem>list[mid]) {
return
findMe(list, ++mid, high, elem);
}
}
if
(elem!=list[mid]) return -1;
return mid;
}
public
static void main (String [] args)
{
int array[] =
{ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8 };
printArray
(array);
if
(checkSort(array))
System.out.println
("The array is sorted");
else
System.out.println
("The array is not sorted");
quicksort(array);
printArray
(array);
if
(checkSort(array))
System.out.println
("The array is sorted");
else
System.out.println
("The array is not sorted");
int
low = 0;
int high = 14;
int
element = 35;
int x
= findMe(array, low, high, element);
System.out.println();
System.out.println(element+" find in position "+x);
System.exit(0);
}
}
/*
* To change this
template, choose Tools | Templates
* and open the
template in the editor.
*/
=========================================================
package Sorting;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import
java.util.Arrays;
/**
*
* @author FILLA
*/
public class RadixSort {
final static int
Nmax= 9;
public static void radix_sort_uint(int[] a, int bits)
{
int[] b = new
int[a.length];
int[] b_orig
= b;
int rshift =
0;
for (int mask
= ~(-1 << bits); mask != 0; mask <<= bits, rshift += bits) {
int[]
cntarray = new int[1 << bits];
for (int
p = 0; p < a.length; ++p) {
int
key = (a[p] & mask) >> rshift;
++cntarray[key];
}
for (int i = 1; i
< cntarray.length; ++i)
cntarray[i] += cntarray[i-1];
for (int
p = a.length-1; p >= 0; --p) {
int
key = (a[p] & mask) >> rshift;
--cntarray[key];
b[cntarray[key]] = a[p];
}
int[]
temp = b; b = a; a = temp;
}
if (a ==
b_orig)
System.arraycopy(a, 0, b, 0, a.length);
}
public static
void main(String[] args) throws IOException
{
BufferedReader in = new BufferedReader (new InputStreamReader
(System.in));
int[] a = new
int [Nmax];
for (int
i=0;i<Nmax;i++) {
System.out.println("Masukkan Angka :");
a[i] =
Integer.parseInt(in.readLine());
}
radix_sort_uint(a, 4);
System.out.println("Hasil Radix Sort:");
System.out.println(Arrays.toString(a));
}
}
/*
* To change this
template, choose Tools | Templates
* and open the
template in the editor.
*/
===================================================
package Sorting;
/**
*
* @author Minerva
*/
public class Selection {
public static void
main(String[] args) {
int[]
data={15,45,56,34,53,87,123,10,98,70};
int temp,pos ;
for (int
i=0;i<data.length;i++) {
System.out.print(data[i]+"\t");
//System.out.println("\n");
}
for(int
i=0;i<data.length-1;i++){
pos=i;
for(int
j=i+1;j<data.length;j++){
if (data[j]
< data[pos]){
pos=j;
}
}
if(pos!=i){
temp=data[i];
data[i]=data[pos];
data[pos]=temp;
}
}
for(int
i=0;i<data.length;i++){
System.out.println(data[i]+"");
}
}
}
/*
* To change this
template, choose Tools | Templates
* and open the
template in the editor.
*/
package Sorting;
import java.util.*;
/**
*
* @author Minerva
*/
public class tree {
public static void
main(String[] args) {
int [] strs =
{1,4,5,3,7,3,8};
OBTComparable
root = new OBTComparable();
for(int i = 0;
i < strs.length; i++) {
root.insert(strs[i]);
}
Iterator
elements = root.elementsAscending();
while(elements.hasNext()) {
System.out.print(elements.next() + " ");
}
System.out.println();
}
}
class OBTComparable <T extends Comparable<T>>
{
private T value;
private
OBTComparable left;
private
OBTComparable right;
private boolean
empty;
//create an empty
tree
public
OBTComparable()
{
setEmpty();
}
//make this tree
into an empty tree
private void
setEmpty()
{
empty = true;
value = null;
left = null;
right = null;
}
//see if this is
an empty (sub)tree
public boolean
isEmpty()
{ return empty; }
//get the value
which is here
public T
getValue()
{ return value; }
//get the left sub
tree
public
OBTComparable getLeft()
{ return left; }
//get the right
sub tree
public
OBTComparable getRight()
{ return right; }
//store a value in
this position in the tree
private void
setValue(T requiredValue)
{
if(empty)
{
empty =
false;
left = new
OBTComparable(); //makes new empty tree
right =
new OBTComparable(); //makes new empty tree
}
value =
requiredValue;
}
//insert a value,
allowing multiple instances
public void
insert(T insertValue)
{
insert(this,
insertValue);
/*
if(empty)
setValue(insertValue);
else
if(value.compareTo(insertValue)==1)
left.insert(insertValue);
else
right.insert(insertValue);
*/
}
private void
insert(OBTComparable<T> node, T insertValue)
{
if(node.isEmpty())
{
node.setValue(insertValue);
}
else
{
if(insertValue.compareTo(node.getValue()) < 0)
insert(node.left, insertValue);
else
insert(node.right, insertValue);
}
}
public boolean
find(T findValue)
{
if(empty)
return
false;
else
if(findValue==value)
return
true;
else
if(findValue.compareTo(value)==-1)
return
left.find(findValue);
else
return
right.find(findValue);
}
public int
getSize()
{
if(empty)
return 0;
else
return
(left.getSize() + 1 + right.getSize());
}
public int
getDepth()
{
if(empty)
return 0;
else
{
int
leftDepth = left.getDepth();
int
rightDepth = right.getDepth();
if(leftDepth > rightDepth)
return
leftDepth +1;
else
return
rightDepth +1;
}
}
public Iterator
elementsAscending()
{
List<T>
elementsList = new ArrayList<T>();
addElementsAscending(elementsList);
return
elementsList.iterator();
}
private void
addElementsAscending(List elementsList)
{
if(!empty)
{
left.addElementsAscending(elementsList);
elementsList.add(value);
right.addElementsAscending(elementsList);
}
}
}