Hallo fyee 😋 Kali ini aku mau bahas tentang materi Pengurutan (Sorting) nih. semoga bisa
membantu yah buat kalian
------------------------------------------------------------------------------------------------------------------
Apa sih
itu Pengurutan (Sorting) ? 😧
Pengurutan (Sorting) adalah proses untuk menyusun kumpulan data
seragam dengan aturan urut menaik ataupun menurun. Terdapat banyak jenis
metode pengurutan yang dapat digunakan dan memiliki kelebihan masing masing.
Pengurutan sangat penting dalam Teknologi Informasi yang tak lepas dari
pengolahan data. Pemecahan permasalahan pengolahan data dapat menjadi lebih
efektif dan efisien bila data sudah dalam keadaan terurut. Seperti dalam proses
pencarian data (searching), algoritma pencarian tingkat lanjut yang lebih
efektif daripada cara konvensional seperti Binary Search ataupun Interpolation
Search membutuhkan data yang sudah terurut. Contoh lain di mana data terurut
dibutuhkan adalah dalam penggabungan data menggunakan metode merging. Dalam
beberapa kasus, pengurutan tanpa pembandingan, memiliki kompleksitas waktu yang
lebih baik daripada metode pengurutan dengan pembandingan. Dan walaupun hal itu
dapat terjadi dengan berbagai batasan-batasan tertentu, eksplorasi lebih lanjut
yang dilakukan semakin lama semakin membuat batasan-batasan tersebut berkurang,
atau dengan kata lain semakin lama, algoritma-algoritma pengurutan tanpa
pembandingan semakin dapat digunakan secara umum (generalized).
Adapun
jenis – jenis metode pengurutan (sorting) adalah:
1.
Aturan pengurutan berdasarkan perbandingan (comparison based
sorting).
Contoh: buble sort,
exchange sort.
2.
Metode pengurutan prioritas antrian (prioritas queue sorting
method).
Contoh: selection sort,
heap sort.
3.
Metode penyisipan dan penjagaan terurut (insert dan keep sort
method).
Contoh: insertion sort,
tree sort.
4.
Metode pembagian dan penguasaan (devide and conquer method).
Contoh: quick sort, merge
sort.
5.
Metode pengurutan berkurang menurun (diminishing increment sort
method).
Contoh: shell sort.
Ada pun
pengertian dari beberapa metode diatas sebagai berikut :
1. Bubble Sort
Bubble sort adalah
mengurutkan data dengan cara membandingkan nilai data pertama dengan data
kedua, jika nilai data pertama lebih besar dari data kedua maka akan terjadi
pertukaran posisi antara data pertama dengan data kedua. Kemudian data kedua
dibandingkan lagi dengan data ketiga, jika data ketiga lebih besar dari data
kedua maka akan terjadi pertukaran posisi antara data kedua denga data ketiga,
begitu seterusnya sampai akhrinya mendapaktak urutan data dari yang nilainya
kecil kenilai yang besar. Data yang terkecil akan berada disebelah kiri dan
data yang besar akan berada disebelah kanan. Dalam bubble sort terdapat dua
cara membandingkan data yaitu, Pengurutan Ascending (jika data pertama lebih
besar dari data kedua maka kedua data tersebut akan ditukar posisinya), dan
Pengurutan Descending (Jika data pertama lebih kecil dari data kedua, maka
kedua data tersebut akan ditukar posisinya).
Algoritma ini seolah-olah
menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan,
tergantung jenis pengurutannya, asc atau desc. Ketika satu proses telah
selesai, maka bubble sort akan mengulangi proses, demikian seterusnya sampai
dengan iterasi sebanyak n-1. Kapan berhentinya? Bubble sort berhenti jika
seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa
dilakukan, serta tercapai perurutan yang telah diinginkan.
Contoh deklarasi bubble sort :
Dengan prosedur diatas, data terurut naik (ascending), untuk urut turun (descending) silahkan ubah bagian :
if (data[i] > data[j]) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
Menjadi :
if (data[i] < data[j]) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
3.
Selection sort
Selection
sort merupkan kombinasi antara sorting dan searching, dimana setipa prosesnya
akan dicari data-data yang belum diurutkan yang memiliki nilai terkecil atau
terbesar akan ditukarkan ke posisi yang tepat di dalam array. Misalnya untuk
pertama akan dicari data dengan nilai terkecil dan data tersebut akan
ditempatkan di indeks terkecil ( data [0] ), dan pada langkah kedua akan dicari
data kedua terkecil dan akan ditempatkan pada indeks kedua ( data [1] ). Dalam
proses ini, pembandingan dan perubahan data hanya dilakukan pada indeks data
dan pertukaran data secara posisi letak akan terjadi pada akhir proses
selection sort.
4.
Heap Sort
Dalam
pemrograman komputer, heapsort adalah algoritma sorting-perbandingan berbasis. Heapsort
dapat dianggap sebagai peningkatan semacam seleksi: seperti algoritma itu, membagi
input menjadi diurutkan dan wilayah disortir, dan iteratif menyusut wilayah
disortir dengan mengekstraksi elemen terbesar dan bergerak yang ke wilayah
diurutkan. Peningkatan tersebut terdiri dari penggunaan struktur data tumpukan
daripada pencarian linear-waktu untuk menemukan maksimal.
Meskipun
agak lambat dalam praktek pada kebanyakan mesin dari quicksort yang
dilaksanakan,
ini memiliki keunggulan yang lebih menguntungkan terburuk O (n login) runtime. Heapsort adalah algoritma di tempat, tapi itu bukan semacam
stabil.
Heapsort
diciptakan oleh JWJ Williams pada tahun 1964. [3] Hal ini juga kelahiran
tumpukan,
disajikan sudah oleh Williams sebagai struktur data yang berguna dalam dirinya sendiri. Pada tahun yang sama, RW Floyd menerbitkan sebuah versi
perbaikan yang bisa mengurutkan
array di tempat, melanjutkan penelitian sebelumnya ke dalam algoritma Treesort.
Algoritma
heapsort sendiri memiliki O (n log n) kompleksitas waktu baik menggunakan versi heapify.
procedure
heapify(a,count) is
(end is assigned the index of the first
(left) child of the root)
end := 1
while
end < count
(sift up the node at index end to the proper place such that all nodes above
the end index are in heap order)
siftUp(a, 0, end)
end := end + 1
(after sifting up the last node all nodes are in heap order)
procedure
siftUp(a, start, end) is
input: start represents the limit of how far up the heap to sift.
end is the node to sift up.
child := end
while
child > start
parent := floor((child-1) / 2)
if a[parent] < a[child] then (out of max-heap order)
swap(a[parent], a[child])
child := parent (repeat to continue sifting up the parent now)
else
return
5. Insertion
Sort
Insertion
sort adalah cara pengurutan data yang dimulai dari data kedua sampai dengan
data terakhir, jika ditemukan data yang lebih kecil maka akan ditempatkan
diposisi yang seharusnya dan terurut posisinya dari data yang terkecil sampai
data yang terbesar. Pada penyisipan data tersebut, data-data lainnya akan
bergeser kebelakang.
Proses
pengurutan dengan metode penyisipan langsung dapat dijelaskan sebagai berikut :
Data
dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila
ditemukan data yang lebih kecil daripada
data sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai. Akan lebih mudah
apabila membayangkan pengurutan kartu. Pertama-tama anda meletakkan kartu-kartu tersebut
di atas meja, kemudian melihatnya dari kiri ke kanan. Apabila kartu di sebelah kanan
lebih kecil daripada kartu di sebelah kiri, maka ambil kartu tersebut dan sisipkan di tempat
yang sesuai. Algoritma penyisipan langsung dapat dituliskan sebagai
berikut :
i = 1
selama (i < N)
kerjakan baris 3 sampai dengan 9
x = Data[i]
j = i – 1
selama (x <
Data[j]) kerjakan baris 6 dan 7
Data[j + 1] = Data[j]
j = j – 1
Data[j+1] = x
i = i + 1
Di bawah ini
merupakan prosedur yang menggunakan metode penyisipan langsung:
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;
} }
---( Binary Insertion
Sort (Metode Penyisipan Biner)
Metode ini merupakan
pengembangan dari metode penyisipan langsung. Dengan cara penyisipan langsung,
perbandingan selalu dimulai dari elemen pertama (data ke-0), sehingga untuk
menyisipkan elemen ke i kita harus melakukan perbandingan sebanyak i- 1 kali. Ide
dari metode ini didasarkan pada kenyataan bahwa pada saat menggeser data ke-i,
data ke 0 s/d i-1 sebenarnya sudah dalam keadaan terurut.
Algoritma penyisipan
biner dapat dituliskan sebagai berikut :
i = 1
selama (i < N)
kerjakan baris 3 sampai dengan 14
x = Data[i]
l = 0
r = i – 1
selama (l<=r)
kerjakan baris 7 dan 8
m = (l + r) / 2
jika (x <
Data[m]) maka r = m – 1, jika tidak l = m + 1
j = i – 1
selama ( j >=l)
kerjakan baris 11 dan 12
Data[j+1] = Data[j]
j = j – 1
Data[l] = x
I= i + 1 Di bawah ini
merupakan prosedur yang menggunakan metode penyisipan biner:
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;
}
}
Contoh deklarasi
insertion sort :
6.
Quick Sort
Quicksort merupakan Algoritma Sorting yang
dikembangkan oleh Tony Hoare yang, secara kasus rata-rata,
membuat pengurutan O(n log n) untuk mengurutkan n item. Algoritma ini
juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting
Pergantian Pembagi. Pada kasus terburuknya, algoritma ini membuat perbandingan
O(n2), malaupun kejadian seperti ini sangat langka. Quicksort sering
lebih cepat dalam praktiknya dari pada algoritma O(n log n) yang
lainnya. Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja
lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat
dilakukan hanya dengan ruang tambahan O(log n). Quicksort merupakan sorting pembanding dan pada implementasi efisien
tidak merupakan algoritma sorting yang stabil. Algoritma Quicksort
merupakan Algoritma Pembagi. Pertama sekali quicksort membagi list yang besar
menjadi dua buah sub list yang lebih kecil: element kecil dan element besar.
Quicksort kemudian dapat menyortir sub list itu secara rekursif.
Langkah-Langkah pengerjaannya ialah:
a.
Ambil sebuah elemen, yang disebut dengan pivot,
pada sebuah daftar.
b.
Urutkan kembali sebuah list sehingga elemen dengan
nilai yang kecil dari pivot berada sebelum pivot, sedangkan seluruh element
yang memiliki nilai yang lebih besar dari pivot berada setelahnya (nilai yang
sama dapat berada pada pivot setelahnya). Setelah pemisahan, pivot berada pada
posisi akhirnya. Operasi ini disebut Partition.
c.
Sub list kemudian disortir secara recursif dari
elemen yang lebih kecil dan sub list dari elemen yang lebih besar. Kasus dasar
dari rekusrif ialah list dari besaran nol atau satu, yang tidak perlu untuk di
sorting.
Versi
Sederhana
Dalam
Pseudocode sederhana, Algoritmanya dapat dinyatakan sebagai berikut:
function quicksort('array')
if length('array') ≤ 1
return 'array' // an array of zero or one elements is already sorted
select and remove a pivot value 'pivot' from 'array'
create empty lists 'less' and 'greater'
for each 'x' in 'array'
if 'x' ≤ 'pivot' then append 'x' to 'less'
else append 'x' to 'greater'
return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two
recursive
calls
Contoh keseluruhan dari quicksort pada kumpulan
acak dari angka. Element yang gelap merupakan pivot. Pivot selalu dipilih
sebagai element terakhir pada partisi. Bagaimanapun, selalu memilih elemen
terakhir pada partisi sebagai pivot sehingga hasil pada kasus terburuk pada
daftar yang telah diurutkan, atau daftar yang serupa. Karena elemen sama
memotong hingga pada akhir dari prosedur soring pada jumlah yang besar, versi
dari algoritma quicksort yang memilih pivot sebagai elemen tengah berjalan
lebih cepat dari pada algortima yang dijelaskan pada diagram ini pada sejumlah
besar angka.Perlu diperhatikan bahwa kita hanya memeriksa elemen dengan
membandingkan mereka pada elemen yang lain. Prosedur ini disebuk Sorting
Pembandingan. Jenis ini juga merupakan jenis sorting yang stabil (asumsikan
bahwa untuk setiap method menerima elemen pada urutan aslinya dan pivot yang
dipilih merupakan elemen terakhir dari nilai yang sama).
Kebenaran dari algoritma partisi didasari pada dua
argumen berikut:
Pada setiap iterasi, seluruh elemen diproses selama
ini berada pada posisi yang diinginkan: sebelum pivot lebih kurang dari nilai
pivot, setelah pivot lebih besar dari nilai pivot (Invarian Loop).
Kebenaran dari keseluruhan algortima dapat
dibuktikan dengan penyederhanaan fakta: untuk elemen nol atau satu, algoritma
tidak akan mengubah data; untuk jumlah data yang lebih besar, algoritma akan
menghasilkan dua bagian, elemen yang kurang dari pivot dan elemen yang lebih
besar dari nya, data ini sendiri akan diurutkan secara hipotesa rekursif.
Contoh dari penerapan Quicksort.
Partisi ditepat bekerja pada daftar yang kecil.
Elemen kotak merupakan element pivot, elemen berwarna biru merupakan elemen
yang bernilai kecil atau sama, dan elemen yang berwarna merah lebih besar.
7.
Merge Sort
Metode penggabungan biasanya
digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai
berikut :
Mula-mula diberikan dua kumpulan
data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus
dijadikan satu table sehingga dalam keadaan urut. Misalnya kumpulan data
pertama (T1) adalah sebagai berikut :
3 11 12 23 31
Sedangkan kumpulan data kedua (T2)
adalah sebagai berikut :
9 15 17 20 35
Proses penggabungan ini dapat
dijelaskan sebagai berikut : mula-mula diambil data pertama dari T1 yaitu 3 dan
data pertama dari T2 yaitu 9. Data ini dibandingkan, kemudian yang lebih kecil
diletakkan sebagai data pertama dari hasil pengurutan, misalnya T3. Jadi T3
akan memiliki satu data yaitu 3. Data yang lebih besar yaitu 9 kemudian
dibandingkan dengan data kedua dari T1, yaitu 11. Ternyata 9 lebih kecil dari
11, sehingga 9 diletakkan sebagai data kedua dari T3. Demikian seterusnya sehingga
didapat hasil sebagai berikut :
3 9 11 12 15 17 20 23 31 35
Algoritma penggabungan dapat
dituliskan sebagai berikut :
1. i = 0
2. j = 0
3. J3 = 0
4. Kerjakan baris 5 sampai dengan
7 selama (i < J1) atau (j < J2)
5. J3 = J3 + 1
6. Jika (T1[i] < T2[j]) maka
T3[J3] = T1[i], i = i + 1
7. Jika (T1[i] >= T2[j]) maka
T3[J3] = T2[j], j = j + 1
8. Jika (i > J1) maka kerjakan
baris 9, jika tidak kerjakan baris 15
9. i = j
10. Selama (i < J2) kerjakan
baris 11 sampai dengan 13
11. J3 = J3 + 1
12. T3[J3] = T2[i]
13. i = i + 1
14. Selesai
15. j = i
16. Selama (j < J1) kerjakan
baris 17 sampai dengan 19
17. J3 = J3 + 1
18. T3[J3] = T1[j]
19. j = j + 1
Di bawah ini merupakan prosedur penggabungan dua kumpulan data yang sudah dalam keadaan urut:
void MergeSort(int T1[],int
T2[],int J1,int J2, int T3[],int *J3)
{
int i=0, j=0;
int t=0;
while ((i<J1)||(j<J2))
{
if(T1[i]<T2[j])
{
T3[t] = T1[i];
i++;
}
Else
{
T3[t] = T2[j];’
j++;
}t++;
}
if(i>J1)
for(i=j; i<J2; i++)
{
T3[t] = T2[i];
t++;
}
if(j>J2)
for(j=i; j<J1; j++)
{
T3[t] = T1[j];
t++;
}
*J3 = t;
}
...oO0---( Mana yang terbaik?
Tidak ada algoritma terbaik untuk
setiap situasi yang kita hadapi, bahkan cukup sulit untuk menentukan algoritma
mana yang paling baik untuk situasi tertentu karena ada beberapa faktor yang
mempengaruhi efektifitas algoritma pengurutan. Beberapa faktor yang berpengaruh
pada efektifitas suatu algoritma pengurutan antara lain:
1. Banyak data yang diurutkan.
2. Kapasitas pengingat apakah
mampu menyimpan semua data yang kita miliki.
3. Tempat penyimpanan data.
---( Attachment: sorting.c
Berikut ini adalah implementasi
dari keenam metode sorting diatas. Data yang akan disorting dibangkitkan secara
random. Ubah-ubahlah nilai N pada program berikut untuk mengetahui perbedaan
kecepatan tiap-tiap metode. Semakin besar anda memberikan nilai N, semakin
terlihat perbedaan waktunya.
8.
Shell Sort
Metode ini disebut juga dengan metode
pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh
Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell
Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan
data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila
diperlukan. Proses pengurutan dengan metode Shell dapat dijelaskan sebagai
berikut :
Pertama-tama adalah menentukan jarak
mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama
dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar
dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data
kedua dibandingkan dengan jarak yang sama yaitu N / 2. Demikian seterusnya
sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil
daripada data ke-(j + N / 2).
Pada proses berikutnya, digunakan jarak
(N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N /
4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data
tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu
N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua
data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak
(N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah
1.
Algoritma metode Shell dapat dituliskan
sebagai berikut :
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
Data[j + Jarak].
Sudah = true
9. j = j + 1
Di bawah ini merupakan prosedur yang
menggunakan metode Shell:
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;
}
} } } }
Sumber :
http://www.mdp.ac.id/materi/2012-2013-2/sp244/111070/SP244-111070-950-18.pdf
pada tanggal 3 April 2015, jam 15:30 WIB
http://hack.spyrozone.net/0221_Struktur_Data_Sorting_Method_by_y3ppy_WWW.SPY.REZONE.NET_07_Oktober_2007.html
pada tanggal 3 April 2015, jam 15:12 WIB
http://stmikhandayani2013.weebly.com/uploads/4/4/1/8/44185755/strukdat_4a.ppt
pada tanggal 3 April 2015, jam 16:01 WIB
http://en.wikipedia.org/wiki/Shellsort
pada tanggal 5 April 2015, jam 22:04 WIB
http://id.wikipedia.org/wiki/Quicksort
pada tanggal 5 April 2015, jam 22:17 WIB
http://en.wikipedia.org/wiki/Heapsort
pada tanggal 5 April 2015, jam 22:26 WIB
Komentar
Posting Komentar