Sorting

Pada saat pemrograman sering dijumpai topik untuk menyusun item/data secara urut naik (ascending) atau urut menurun (descending). Bayangkan bagaimana jika anda menggunakan kamus dan jika kamus tersebut tidak tersusun secara alphabet, sama juga pada programming data yang kita simpan di memori computer data yang disimpan akan disimpan sesuai aturan tertentu

Sorting adalah kegiatan mengurutkan data yang tersedia dalam suatu tempat penyimpanan dengan urutan tertentu baik urut menaik (ascending) atau urut turun (descending). Meskipun pada kamus Bahasa Inggris sorting diartikan sebagai proses pemisahan atau mengatur sesuatu sesuai kelas atau sesamanya.

Kegunaan Sorting yang paling penting

1.    Memecahkan masalah “togetherness”

Pada saat item/data yang dimiliki sama, misal ada array sebanyak 1000. Akan dilakukan sorting sesuai urutan tertentu, dari yang nilai terkecil, nilai yang terbesar dan memiliki nilai yang sama. Hal ini bisa terpecahkan dengan cara jika urut menaik , V₁ ≤ V₂ ≤….≤ V_1000.

2.    Membandingkan item di dua atau lebih file

Jika beberapa file telah diurutkan sesuai urutan tertentu yang sama, membuat mencari semua data/file yang sama dalam satu kali proses tanpa perlu membackup. Sorting memungkinkan untuk akses secara berurutan pada file besar, seperti mensubstitusi layaknya dalam penanganan langsung.

3.    Pencarian informasi dengan key/kata kunci tertentu.

Sorting juga berperan dalam pencarian (searching), sorting membantu kita membuat output computer lebih sesuai untuk kebutuhan manusia.

Meskipun sorting telah digunakan untuk memproses data bisnis, sorting sebenarnya tool dasar bagi para programmer untuk digunakan di berbagai macam situasi

Berdasarkan pendekatan cara penyelesaian masalah, ada beberapa pendekatan yang dilakukan antara lain:

A.   Brute Force and Exhaustive Search

          Brute force disini berarti pendekatan secara langsung dalam pemecahan masalah, biasanya berdasarkan pada pernyataan masalah dan definisi konsep yang berhubungan dengan permsalahan.

B.   Decrease and Conquer

           Teknik decrease and conquer adalah teknik yang berdasarkan memanfaatkan hubungan antara solusi dengan masalah yang ada dengan solusi masalah yang lebih kecil.

C.   Divide and Conquer
       Divide and Conquer bekerja sesuai mengikuti :
      1. Permasalahan dibagi menjadi submasalah yang bertipe sama, idealnya berukuran        sama

      2. Submasalah mendapat solusi

      3. Jika diperlukan solusi dari submasalah dikombinasikan untuk mendapat solusi  pada masalah utama

D.   Transform and Conquer

  Pada Transform and Conquer ada 2 tahap prosedur

       1.    Transformation stage

                    Tahap ini permasalahan akan dimodifikasi agar lebih sesuai dengan solusi

             2.    Conquering stage 

                    Permasalahan dipecahkan atau mendapatkan solusi

E.  Space and Time Trade-Offs

Teknik pendekatan ini menggunakan pendekatan memproses awal input masalah masalah secara keseluruhan atau sebagian , dan menyimpan informasi tambahan yang diperoleh untuk mempercepat pemecahan masalah sesudahnya.

Sort adalah kegiatan mengurutkan data yang tersedia dalam suatu tempat penyimpanan dengan urutan tertentu baik urut menaik (ascending) atau urut turun (descending).

Berdasarkan pendekatan cara pemecahan masalah sort dapat dikelompokkan :

 A. Brute Force and Exhaustive Search

     BubbleSort

     SelectionSort

 B. Decrease and Conquer

InsertionSort

    TopologicalSorting

 C. Divide and Conquer

    MergeSort

    QuickSort

 D. Transform and Conquer

PreSorting

  HeapSort

 E. Space and Time Trade-Offs

Sorting by Counting

Dalam buku The Art of Computer Programming 2nd edition Volume 3 Donald E. Knuth mengkelompokkan sorting menjadi tiga; internal sorting, optimum sorting, dan external sorting.

Terlebih lanjut dibagi menjadi

1. Internal Sorting

    Sorting by Insertion

Sorting by Exchanging

Sorting by Selection

Sorting by Merging

Sorting by Distribution

2. Optimum Sorting

Minimum-Comparison Sorting

    Minimum-Comparison Merging

    Minimum-Comparison Selection

Network for Sorting

3. External Sorting

    Multiway Merging and Replacement Selection

    The Polyphase Merge

    The Cascade Merge

Reading Tape Backwards

The Oscillating Sort

Practical Consideration for tape Merging

External Radix Sorting

Two-Tape Sorting

Disk and Drums

Bubble sort adalah metode pengurutan dengan cara membandingkan elemen yang berada di array dan menggantikan posisi elemen tersebut yang sesuai dengan syarat tertentu secara menaik (ascending) atau menurun (descending). Pembandingan tersebut dilakukan sampai di posisi terakhir pada array sehingga terlihat seperti gelembung maka metode ini disebut Bubble sort.

Contoh:

Diketahui : Array dgn jumlah elemen sebanyak n, 

i=indeks array

A (array)

A0,………..,Aj ===== awal

A0,………..,Aj <==?==> Aj+1,………..,An-i-1 An-i ≤……≤ An-1

Pseudocode pada algoritma ini

Algoritma BubbleSort (A[0...n-1])

//sort array menggunakan metode bubble sort

//input : Array A[0…n-1] array tersusun acak

//output : Array A[0…n-1] array tersusun urut menaik

for i  <---  0 to n-2 do

for j <---  0 to n-2-i do

if A[j+i] < A[j] swap A[j] and A[j+1]

Selection sort adalah metode pengurutan dengan cara memeriksa seluruh list array untuk menemukan nilai elemen terkecil jika pengurutan menaik (ascending), menemukan nilai terbesar jika pengurutan menurun (descending) dan menempatkan nilai yang telah ditemukan di posisi terakhir pada list array. Kemudian akan dicari nilai terkecil diantara n-1 sampai semua nilai pada array menjadi urut baik urut menaik atau menurun.

Contoh:

Diketahui : Array dgn jumlah elemen sebanyak n, 

i=indeks array

A (array)

A0,………..,Aj ===== awal

A0≤A1≤…...≤Aj-1 Aj,……,Amin,…….,An-1

Algoritma SelectionSort(A[0….n-1]

//Sort menggunakan metode selection sort

//j=i+1

//input : Array A[0…n-1] array tersusun acak

//output : Array A[0…n-1] array tersusun urut menaik

for i <----0 to n-2 do

  min <-----i

for j <----i+1 to n-1 do

if A[j] < A[min] min<--- j

swap A[i] and A[min]

Insertion Sort adalah metode pengurutan dengan cara menyisipkan nilai j(i+1) ke tempat diantara elemen ke tempat semestinya atau sesuai ketentuan (ascending/descending)

A[0]≤…..≤A[j] < A[j+1] ≤…≤A[i-1]   A[i]…A[n-1]

Algoritma InsertionSort (A[0…n-1])

//Sort dengan metode insertion sort

//Input : Array A[0…n-1] array tersusun acak

//Output : Array A[0…n-1] array tersusun urut menaik

for i <---- 1 to n-1 do

v <---- A[i]

j  <---- i - 1

while j ≥ 0 and A[j] > v do

A[j + 1] <---- A[j]

j<---- j – 1

A[j + 1]<---- v

Merge Sort adalah metode pengurutan dengan cara membagi 2 sebuah array menjadi 2 bagian kemudian mengurutkan sesuai syarat/ketentuan (ascending/descending) pada masing-masing bagian kemudian menggabungkan kembali bagian terkecil menjadi satu bagian yang telah tersusun baik urut menaik maupun urut menurun.

Algoritma MergeSort (A[0..n-1])

//Sort Array A[0..n-1]

//Input : Array A[0..n-1]

//Output : Array A[0..n-1] 

 If n > 1

Copy A[0..[n/2]-1] to B[0..[n/2]-1]

Copy A[[n/2]..n-1] to C[0..[n/2]-1]

Mergesort(B[0..[n/2] – 1])

Mergesort(C[0..[n/2] – 1])

Merge(B, C, A)

Algoritma Merge(B[0..p-1]), C[0..q-1], A[0..p+q-1])

//Merge dua array yang telah urut menjadi satu array yang telah urut

//Input : Arrays B[0..p-1]) dan C[0..q-1] keduanya telah urut

//Output : Array A[0..p+q-1] dari elemen B dan C yang telah urut

 i<----0 ; j<----0; k<----0

while i < p and j < q do

if B[i] ≤ C[j]

A[k]<----B[i]; i<----i + 1

  else A[k]<----C[j]; j<----j + 1

if i=p

        copy C[j..q-1] to A[k..p+q-1]

else copy B[i..p-1] to A[k..p+q-1]

Sumber : 
 - Knuth, Donald E. 1998. The Art of Computer Programming

 - Levitin, Anany. Introduction to The Design and Analysis of Algorithms

 - Kadir, Abdul. Pengenalan Algoritma