LANJUTAN DARI SHORTING
PENGERTIAN SHELL
SORT
Shell Sort
Algoritma
ini memiliki kesamaan cara kerja dengan insertion sort, yaitu membandingkan
elemen-elemen dengan jarak tertentu.
Insertion sort membandingkan elemen–elemen data yang
berdekatan (berjarak satu posisi), sedangkan shell sort membandingkan elemen
berjarak tertentu, misalnya elemen yang berjarak 5 posisi atau 2 posisi dan
pada akhirnya akan selesai pada pengurutan data yang berjarak 1 posisi. Namun nilai
ini haruslah dicari sedemikian rupa agar tidak menulangi atau merusak hasil
sorting sebelumnya.
Program tentang merge sort
void mergesort (int *x, int n)
{
int *r, i, j, k, l1, l2, u1, u2, size;
r = (int *) malloc (n * sizeof (int));
size = 1;
while (size < n)
{
l1 = 0; k = 0;
while (l1+size < n)
{
l2 = l1+size;
u1 = l2 – 1;
u2 = (l2 + size – 1 < n) ? l2 + size – 1 : n-1;
for (i=l1; j=l2; i<=u1 && j<=u2; k++)
r[k] = (x[i] <= x[j]) ? x[i++] : x[j++];
while (i<=u1) r[k++] = x[i++];
while (j<=u2) r[k++] = x[j++];
l1 = u2+1;
}
for(i=l1; k<n; i++) r[k++] = x[i];
for(i=0; i<n; i++) x[i] = r[i];
size *= 2;
}
free(r); }a
KELEBIHAN
DAN KELEMAHAN SORT
KELEBIHAN SORT :
1. Sederhana dalam penerapannya.
2. Mangkus dalam data yang kecil.
3. Jika list sudah terurut atau sebagian
terurut maka Insertion Sort akan lebih cepat dibandingkan dengan Quicksort.
4. Mangkus dalam data yang sebagian sudah
terurut.
5. Lebih mangkus dibanding Bubble Sort dan
Selection Sort.
6. Loop dalam pada Inserion Sort sangat
cepat, sehingga membuatnya salah satu algoritma pengurutan
tercepat pada jumlah elemen yang sedikit.
7. Stabil.
KELEMAHAN :
1. Banyaknya operasi yang diperlukan
dalam mencari posisi yang tepat untuk elemen larik.
2. Untuk larik yang jumlahnya besar ini
tidak praktis.
3. Jika list terurut terbalik sehingga
setiap eksekusi dari perintah harus memindai dan
mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.
4. Membutuhkan waktu O(n2) pada data yang
tidak terurut, sehingga tidak cocok dalam pengurutan elemen dalam jumlah besar.
METODE – METODE
PENERAPAN SORT
1.
Comparison-Based Sorting (pengurutan
berdasarkan perbandingan)
# Bubble sort, exchange sort.
# Bubble sort, exchange sort.
2. Priority
Queue Sorting Method (pengurutan berdasarkan prioritas)
# Selection sort, heap sort.
# Selection sort, heap sort.
3. Insert
and Keep Sorted Method (pengurutan berdasarkan penyisipan dan
penjagaan terurut) # Insertion sort, tree sort.
4. Devide
and Conquer Method(pengurutan berdasarkan pembagian dan penguasaan)
# Quick sort, merge sort.
5.
Diminishing Increment Sort Method (pengurutan berkurang menurun)
# Shell sort.
# Shell sort.
Terdapat dua pendekatan dalam metode pengurutan
dengan Selection Sort :
1.
Algoritma pengurutan maksimum (maximum
selection sort), yaitu memilih elemen maksimum sebagai basis
pengurutan.
2. Algoritma pengurutan minimum (minimum
selection sort), yaitu memilih elemen minimum sebagai basis
pengurutan
