Handout No: 24 [Handout berikutnya, sebelumnya, atau kembali ke halaman utama]

    Algoritma-algoritma Pengurutan Internal

    28 April 1999

    Goal: Selection Sort, Heap Sort, Insertion Sort, Tree Sort, Bubble Sort,
    Shell Sort, Quick Sort, Merge Sort, Radix Sort, dan Proximity Map Sort

    Motivasi

    Dari konteks kuliah ini sebenarnya relevansinya dengan strukur data amat lemah karena hanya berkaitan dengan struktur data array. Namun karena sudah menjadi semacam konvensi bahwa topik pengurutan ini dimasukkan dalam kuliah Struktur Data (bisa dilihat pada umumnya buku-buku teks membahas topik ini) atau dibahas secara teoritis dalam kuliah Disain dan Analisis Algoritma.

    Proses pengurutan seringkali menjadi bagian yang krusial dalam setiap pengolahan data sehingga mengapa ini merupakan topik yang penting. Contohnya dalam berbagai aplikasi dengan data ribuan bahkan jutaan, pengurutan bisa menghabiskan CPU-time paling banyak dari keseluruhan pengolahan data.

    Masalah pengurutan itu sendiri selama ini memunculkan bervariasi algoritma. Yang akan dibahas disini adalah algoritma-algoritma yang memiliki keunikan tersendiri. Di luar algoritma-algoritma yang dibahas ada puluhan algoritma lain yang pada dasarnya variant-variant dari algoritma-algoritma yang akan dibahas berikut ini.

    Mengikuti pembahasan buku teks yang digunakan, algoritma-algoritma tersebut dikategorikan ke dalam sejumlah kelompok:

    • Algoritma-algoritma berdasarkan Priority Queue Akan dibahas: Selection Sort, dan Heap Sort.
    • Algoritma-algoritma penyisipan dalam keterurutan Akan dibahas: Insertion Sort, dan Tree Sort.
    • Algoritma-algoritma transposisi Akan dibahas: Bubble Sort.
    • Algoritma-algoritma dengan increment yang mengecil (diminished increment) Akan dibahas: Shell Sort.
    • Algoritma-algoritma "Divide & Conquer" Akan dibahas: Quick Sort, dan Merge Sort.
    • Algoritma-algoritma penghitungan alamat Akan dibahas: Radix Sort, dan Proximity Map Sort.

    Sebagai asumsi dasar dalam pembahasan selanjutnya tanpa menghilangkan sifat umumnya, pengurutan-pengurutan dilakukan menaik. Pengurutan menurun pada dasarnya sama kecuali pemeriksaan lojik adalah kebalikannya. Demikian halnya data yang diurutkan hanyalah array dari bilangan. Secara umum data dapat merupakan array dari suatu data record dari sejumlah field dan salah satunya digunakan kebagai key untuk pengurutan. Ragam dari field untuk pengurutan itu pun dapat pula berupa alfanumeris yang berimplikasi ekspresi-ekspresi lojik perlu disubstitusi oleh metoda-metoda lojik yang sesuai.

    Selection Sort

    Ide algoritma ini amat sederhana. Mencari data terkecil dari data set yang belum terurut dan disusun dalam data set terurut. Tentu, data set terurut pada mulanya kosong. Setelah satu demi satu data disusun maka akan terbentuk keterurutan tersebut.

    Dalam pengurutan ini kedua data set (terurut maupun yang belum) berada dalam array yang sama. Misalnya array tersebut adalah X, maka pada setiap saat terdapat i buah data terurut pada X[0], X[1], ..., X[i-1], dan data tak terurut pada X[i], X[i+1], ..., X[n-1]. Algoritma melakukan pencarian X[j] terkecil dari data set yang belum terurut tersebut, misalnya didapat X[m] lalu melakukan penukaran X[i] dengan X[m] sehingga kemudian sudah terurut i+1 buat data dalam X.

    Algoritma selengkapnya adalah:

    for (i=0; i < n-2; i++) { m = i;
    for (j = m+1; j < n-1; j++) { if (X[m] > X[j]) m = j; }
    if (m != i) { t = X[m]; X[m] = X[i]; X[i] = t; }     }     Dalam semua kondisi algoritma ini tepat akan melakukan iterasi luar sebanyak n-1 dan iterasi dalam sebanyak (n-i). Jumlah operasi "m = j;" bergantung pada kondisi data. Average case adalah setengah dari jumlah iterasi dalam yang dilakukan pada setiap iterasi luar, yang menghasilkan jumlah total 1/4 n2) operasi tersebut. Kompleksitas dari algoritma ini O(n2).

    Heap Sort

    Algoritma ini sudah di bahas pada saat pembahasan Heap Tree (dalam topik Struktur Data Hirarkis). Secara konseptual algoritma ini memanfaatkan Heap Tree sebagai Priority Queue. Jika dalam Selection Sort, data yang sudah terurut di taruh di bagian kiri array dan data tak terurut di sebelah kanan array, dalam Heap Sort, data yang sudah terurut di taruh di bagian kanan array dan tak terurut (atau lebih tepatnya tersusun dalam heaptree) di sebelah kiri array. Dengan demikian data yang diambil dari Priority Queue adalah data yang terbesar untuk ditaruh ke dalam bagian yang terurut sementara dalam Selection Sort, yang diambil adalah data yang terkecil.

    Kompleksitas waktu dari algoritma ini adalah O(n log n) yang diperoleh dari n-1 kali iterasi dikalikan dengan proses reheapify yang merupakan proses logaritmis. Inisialisasi dengan heapify hanya memerlukan O(n) (worse case adalah O(n log n), sehingga kompleksitas waktu total masih merupakan O(n log n). Algoritma ini termasuk stabil; perbedaan antara worse case dengan best case tidak besar.

    Insertion Sort

    Ide dari algoritma ini seperti layaknya yang dilakukan oleh pemain kartu. Mulai dari dua kartu terkiri diurutkan, lalu kartu ketiga dari kiri disisipkan pada posisi yang sesuai, dan dilanjutkan dengan kartu ke empat, ke lima, dst. jadi pada suatu saat data x[0],...,x[i-1] sudah terurut. X[i] akan diselipkan di antara x[j] dan x[j+1] jika x[i] berharga di antara keduanya.

    Contoh:

    Jika sudah terurut 3,6,9, dan selanjutnya belum terurut 5,7,2,....
    5 akan disisipkan di antara 3 dan 6, sehingga menjadi 3,5,6,9.
    7 akan disisipkan di antara 6 dan 9, sehingga menjadi 3,5,6,7,9.
    2 akan disisipkan sebelum 3, sehingga menjadi 2,3,5,6,7,9.

    Dalam implementasinya pemeriksaan x[i] diefisienkan dengan menyimpan isi x[i] ke dalam suatu temporary variable, kemudian setiap x[j] di kirinya yang lebih besar dari t digeser ke kanan, hingga didapatkan kondisi j < 0 atau x[j] <= t. Jadi algoritma selengkapnya:

    for (i = 1; i < n; i++) {
    t = x[i];
    for (j =i-1; j >= 0 && !stop; j--) {
    if (t < x[j]) x[j+1] = x[j];
    else {
    x[j+1] = t;
    break;
     }
     }
     }

    Suatu variant mengurangi pemeriksaan j >= 0 dengan menambahkan sentinel di awal array. Sentinel tersebut berharga bilangan yang tak hingga negatif, sehingga iterasi selalu berhenti. Masalahnya, kita harus melakukan inisialisasi dengan menggeserkan isi array satu posisi terlebih dahulu untuk dapat ditempati sentinel tersebut, dan di akhir algoritma kita harus menggeserkan kembali ke posisi semula.

    loop-for dalam dilakukan dalam jumlah iterasi yang bervariasi: best case adalah 1 kali (langsung keluar), dan worse case adalah i-1 kali yaitu jika disisipkan di x[0]. Sehingga kompleksitas best case adalah O(n), worse-case adalah O(n2).

    Pertanyaan: Apa yang menentukan kondisi worse/best case dalam hal ini? Beri contoh data yang best case dan contoh untuk yang worse case? Bagaimana dengan data acak?

    Tree Sort

    Jika insertion Sort yang melakukan penyisipan dalam array data ybs. membutuhkan banyak operasi penggeseran, maka Tree Sort melakukan penyisipan tanpa menggeseran dengan digunakannya suatu struktur tambahan Binary Search Tree. Setelah seluruh data masuk dalam BST, traversal secara inorder pada BST dan menyimpannya dalam array akan menghasilkan array dengan data terurut.

    Seperti yang kita ketahui kompleksitas operasi penyisipan pada BST adalah O(log n) dan operasi traversal adalah O(n). Untuk n data operasinya adalah O(n log n + n) = O(n log n).

    Walaupun kompleksitasnya ini adalah O(n log n), algoritma ini kurang populer karena adanya kebutuhan ruang untuk BST.

    Bubble Sort

    Ide dari algoritma ini sangat menarik. Setiap pasangan data: x[j] dengan x[j-1], untuk semua i=1,...,n-1 harus memenuhi keterurutan, yaitu x[j] > x[j-1]. Apabila tidak memenuhi maka posisi kedua data harus ditukar. Untuk pemrograman konvensional maka pemeriksaan-pemeriksaan pasangan tersebut harus dilakukan satu demi satu, misalnya oleh bubble-sort dilakukan dari kanan ke kiri serta di dalam sejumlah iterasi.

    Pada iterasi ke-i, pemeriksaan tsb. dilakukan pula dalam loop-for sbb.

    for (j=n-1; j > i; j--) {
    if (x[j] < x[j-1]) {
    tmp = x[j];
    x[j] = x[j-1];
    x[j-1] = tmp;
     }
     }
     Loop-for tersebut akan menggeser bilangan terkecil ke posisi i. Loop-for dilakukan hanya sampai ke i karena pada iterasi ke-i data dalam x[0], x[1], ..., x[i-1] merupakan yang paling kecil dan sudah terurut hasil pengeseran yang dilakukan setiap loop sebelumnya. Oleh sebab itu iterasi hanya dilakukan untuk harga i=0, 1, ..., n-2 atau sampai tidak terjadi penukaran dalam suatu iterasi.

    void BubbleSort() { ch = true;
    for (i=0; i < n-2 && ch; i++) { ch = false;
    for (j=n-1; j > i; j--) { if (x[j] < x[j-1]) { tmp = x[j];
    x[j] = x[j-1];
    x[j-1] = tmp;
    ch = true;     }     }     }     }

    Contoh untuk mengurutkan data 34,43,65,90,48,82,93,86,26,76,49,23,56,37.

    Pada iterasi i=0:
    j=13: tukar 56-37 menjadi 34,43,65,90,49,82,93,86,26,76,49,23,37,56
    j=12: tidak ada penukaran
    j=11: tukar 49-23 menjadi 34,43,65,90,48,82,93,86,26,76,23,49,37,56
    j=10: tukar 76-23 menjadi 34,43,65,90,48,82,93,86,26,23,76,49,37,56
    j= 9: tukar 26-23 menjadi 34,43,65,90,48,82,93,86,23,26,76,49,37,56
    j= 8: tukar 86-23 menjadi 34,43,65,90,48,82,93,23,86,26,76,49,37,56
    j= 7: tukar 93-23 menjadi 34,43,65,90,48,82,23,93,86,26,76,49,37,56
    j= 6: tukar 82-23 menjadi 34,43,65,90,48,23,82,93,86,26,76,49,37,56
    j= 5: tukar 49-23 menjadi 34,43,65,90,23,48,82,93,86,26,76,49,37,56
    j= 4: tukar 90-23 menjadi 34,43,65,23,90,48,82,93,86,26,76,49,37,56
    j= 3: tukar 65-23 menjadi 34,43,23,65,90,48,82,93,86,26,76,49,37,56
    j= 2: tukar 43-23 menjadi 34,23,43,65,90,48,82,93,86,26,76,49,37,56
    j= 1: tukar 34-23 menjadi 23,34,43,65,90,48,82,93,86,26,76,49,37,56

    Pada iterasi i=1:
    j=13: tidak ada penukaran
    j=12: tukar 49-37 menjadi 23,34,43,65,90,48,82,93,86,26,76,37,49,56
    j=11: tukar 76-37 menjadi 23,34,43,65,90,48,82,93,86,26,37,76,49,56
    j=10: tidak ada penukaran
    j= 9: tukar 86-26 menjadi 23,34,43,65,90,48,82,93,26,86,37,76,49,56
    j= 8: tukar 93-26 menjadi 23,34,43,65,90,48,82,26,93,86,37,76,49,56
    j= 7: tukar 82-26 menjadi 23,34,43,65,90,48,26,82,93,86,37,76,49,56
    ...
    j= 2: tukar 34-26 menjadi 23,26,34,43,65,90,48,82,93,86,37,76,49,56

         Dan seterusnya. Hingga, pada setiap akhir iterasi berikutnya berturut-turut menjadi:
    i=2: 23,26,34,37,43,65,90,48,82,93,86,49,76,56
    i=3: 23,26,34,37,43,48,65,90,49,82,93,86,56,76
    i=4: 23,26,34,37,43,48,49,65,90,56,82,93,86,76
    i=5: 23,26,34,37,43,48,49,56,65,90,76,82,93,86
    i=6: 23,26,34,37,43,48,49,56,65,76,90,82,86,93
    i=7: 23,26,34,37,43,48,49,56,65,76,82,90,86,93
    i=8: 23,26,34,37,43,48,49,56,65,76,82,86,90,93
    i=9: 23,26,34,37,43,48,49,56,65,76,82,86,90,93

    Dari kedua iterasi dengan increment linear demikian dapat mudah dilihat bahwa algoritma ini memiliki kompleksitas O(n2) dan proses akan menjadi amat cepat kalau data sudah sebagian besar terurut. Masalah yang dihadapi algoritma ini adalah banyaknya penukaran yang dilakukan selama proses dalam kondisi normal. Efisiensi dapat ditingkatkan dengan mengurangi proses penukaran dengan penggeseran dan penyisipan seperti halnya insertion sort. Untuk lingkungan pemrograman paralel dengan array processor pengurutan ini menjadi amat menarik untuk dikaji.

    Jika Bobble Sort dalam setiap iterasi melakukan loop-for penukaran ke satu arah, Shaker Sort (suatu variant dari Bubble Sort) melakukan loop-for penukaran dengan arah bolak-balik dengan batas loop-for kiri dan kanan semakin menyempit.

    Shell Sort

    Algoritma ini bisa dipandang sebagai modifikasi dari algoritma Insertion Sort, lebih tepatnya memanfaatkan kondisi-kondisi positif dari Insertion Sort. Walaupun Insertion Sort dalam kondisi normal merupakan algoritma O(n2), algoritma ini memiliki keuntungan-keuntungan sbb.:
    • Insertion Sort bisa sangat efisien untuk data dalam kondisi hampir terurut.
    • Karena Insertion Sort sangat sederhana, maka overhead cost untuk proses-proses tambahannya pun amat kecil sehingga untuk jumlah data n yang kecil masih bisa lebih cepat dari algoritma O(n log n).

    Dengan suatu bilangan integer positif D, maka setiap X[i], X[i+D], X[i+2D, ..., dimasukkan dalam satu subset yang sama dari D subset yang ada. Pengurutan a'la Insertion Sort dilakukan pada masing-masing subset. Jika D=1 maka yang terjadi adalah Insertion Sort murni.

    Sejumlah harga D: D1, D2, ..., Dh, di mana D1 > D2 > ... > Dh = 1, masing-masing diaplikasikan dengan cara di atas berturut-turut mulai dari yang terbesar hingga yang terkecil maka akhirnya terjadi hal-hal sebagai berikut:

    • Saat D berharga besar maka terjadi sejumlah insertion sort pada subset-subset yang masing-masing dengan data berjumlah sedikit (n/D). Dengan demikian mendekati kondisi positif Insertion Sort kedua.
    • Untuk D yang kecil ukuran subset membesar namun akibat proses pada D sebelumnya dapat menyebabkan data sebagian terurut, dan ini adalah mendekati kondisi positif Insertion Sort pertama.

    Kompleksitas dari algoritma ini secara worse case adalah dengan waktu O(n2) tetapi dengan pemilihan harga-harga D yang tepat dapat menghasilkan kompleksitas waktu yang kurang dari itu. Namun sejumlah literatur berdasarkan pengukuran eksperimental mendapatkan average case dengan waktu O(n1.25).

    Quick Sort

    Ide dari algoritma ini adalah secara rekursif membagi (atau mempartisi) data set ke dalam dua sub data set; kita sebut sub data set kiri dan sub data set kanan. Partisi ini dilakukan dengan kriteria:
    • digunakan salah satu data sebagai pivot value
    • sub data set kiri adalah data yang berharga <= pivot value
    • sub data set kanan adalah data yang berharga > pivot value

    Jika data set berada dalam array X berindeks dari l sampai dengan r maka pembagian ini mempertukarkan sejumlah isi array sehingga sub data set kiri berada dalam array yang sama berindeks l sampai dengan t-1 dan sub data set kanan berada dalam array berindeks t+1 sampai dengan r. X[t] sendiri ditempati oleh pivot.

    Setelah dilakukan pembagian tersebut maka algoritma Quick Sort diaplikasikan untuk masing-masing sub data set tsb dan seterusnya secara rekursif hingga terbentuk sub data set yang tidak dapat dibagi lagi yaitu jika hanya berisi satu sel (l = r).

    Bagian yang paling tricky adalah pada pembagian data set, kita sebut fungsi tersebut adalah Partition(l,r) yang menghasilkan t yaitu posisi pivotnya. Maka, algoritma Quick Sort adala sebagai berikut.

    void QuickSort(int l,int r) {
    if (l < r) {
    t = Partition(l,r);
    QuickSort(l,t-1);
    QuickSort(t+1,r);
     }
     }

    Proses Partisi diserahkan kepada anda untuk mempelajarinya sendiri. Dalam beberapa literatur terdapat variant-varuant yang pada dasarnya terjadi karena perbedaan cara menentukan harga pivot: bisa data pertama (X[l]), data terakhir (X[r]) atau data ditengah (X[(l+r)/2]) data set).

    Kompleksitas algoritma Quick Sort adalah bergantung pada hasil partisi tersebut. Kondisi best case adalah jika dalam setiap partisi tidak dilakukan operasi pertukaran tempat dan pivot tepat berada ditengah subset (O(n)). Kondisi average case adalah jika partisi menghasilkan sub data set yang balance (o(n log n)). Kondisi worse case adalah jika partisi menghasilkan sub data set kosong dan yang lain besar (o(n2). Walaupun demikian, algoritma ini cenderung untuk average case.

    Merge Sort

    Ide algoritma ini hampir mirip dengan QuickSort, yaitu melakukan partisi. Kecuali bahwa algoritma ini melakukan partisi tanpa kriteria. Jadi, data set (X[l] ... X[r]) di partisi langsung ke du sub data set dengan jumlah data yang sama (X[l] ... X[(l+r)/2], dan X[(l+r)/2+1] ... X[r]). Lalu secara rekursif melakukan Merge Sort untuk masing-masing data set. Karena kedua data set itu bisa overlapping (tidak seperti pada Quick Sort) maka setelah kedua sub data set terurut masih memerlukan proses penggabungan (Merging). Merging ini memerlukan ruang tambahan yaitu suatu array yang sama panjangnya dengan panjang kedua subset untuk menyimpan hasilnya.

    void MergeSort(int l,int r) { if (l < r) { MergeSort(l, (l+r)/2);
    MergeSort((l+r)/2,r);
    Merging();     }     }     Algoritma ini memiliki kompleksitas O(n log n).

    Radix Sort

    Berbeda dengan algoritma-algoritma di atas, Radix Sort adalah algoritma O(n) dengan kompensasi diperlukan ruang tambahan untuk ruang kerjanya. Sorting dilakukan dengan :
    • membagi data set ke sub-sub data set sesuai dengan harga radixnya, kemudian
    • menyatukannya subset subset tersebut menjadi satu set kembail (hanya mekonkatenasi) untuk dilakukan pembagian berikutnya berdasarkan radix yang lebih signifikan.
    Setelah radix demi radix dilakukan, mulai dari radix yang paling tidak signifikan ke yang paling signifikan, maka kemudian akan dihasilkan data terurut.

    Contoh radix disini adalah digit-digit dari data. Misalnya data berisi bilangan antara 000 sampai 999, maka ada 3 digit yang bisa digunakan sebagai radix (000, 001, 002, ... 999). Digit terkanan adalah radix paling tidak signifikan, dan digit terkiri adalah yang paling signifikan.

    Contoh untuk mengurutkan data: 121, 076, 823, 367, 232, 824, 434, 742, 936, 274, 736, 576, 875, 268, 764, 548, 648, 358, 637, 534.

    Pertama kali dibagi sesuai digit terkanan: Kemudian dibagi sesuai digit kedua: Terakhir sesuai digit terkiri:
    Subset#0: (kosong)
    Subset#1: 121
    Subset#2: 232 742
    Subset#3: 823
    Subset#4: 824 434 274 764 534
    Subset#5: 875
    Subset#6: 076 936 736 576
    Subset#7: 367 637
    Subset#8: 268 548 648 358
    Subset#9: (kosong)

    Hasil penggabungannya adalah: 121 232 742 823 824 434 274 764 534 875 076 936 736 576 367 637 268 548 648 358

    		Subset#0: (kosong)
    Subset#1: (kosong)
    Subset#2: 121 823 824
    Subset#3: 232 434 534 936 736 637
    Subset#4: 742 548 648
    Subset#5: 358
    Subset#6: 764 367 268
    Subset#7: 274 875 076 576
    Subset#8: (kosong)
    Subset#9: (kosong)

    Hasil penggabungannya adalah: 121 823 824 232 434 534 936 736 637 742 548 648 358 764 367 268 274 875 076 576

    		Subset#0: 076
    Subset#1: 121
    Subset#2: 232 268 274
    Subset#3: 358 367
    Subset#4: 434
    Subset#5: 534 548 576
    Subset#6: 637 648
    Subset#7: 736 742 764
    Subset#8: 823 824 875
    Subset#9: 936

    Hasil penggabungannya adalah: 076 121 232 268 274 358 367 434 534 548 576 637 648 736 742 764 823 824 875 936

    Dalam contoh tersebut pengetian radix adalah digit. Dalam penggunaannya bisa saja radix adalah dalam ukuran-ukuran 3 bit (oktal) dari data, atau bisa juga karakter ASCII (1 byte) dari data. Yang perlu diperhatikan adalah jika radix berukuran r bit maka akan diperlukan 2r buah subset yang masing-masing harus disediakan dalam ukuran maksimumnya (yaitu sebanyak datanya). Jadi diperlukan space tambahan untuk 2r*n data. Jika r terlalu besar jelas akan memakan banyak ruang, sebaliknya jika r terlalu kecil maka akan diperlukan lebih banyak iterasi.

    Jika jumlah radix adalah d dan jumlah data adalah n maka operasi pengurutan ini memerlukan penempatan data dalam subset sebanyak dn kali yang berarti memiliki kompleksitas waktu O(n). Namun dicapainya waktu linear tersebut harus diiringi pertimbangan kebutuhan ruang yang besar.

    Proximity Map Sort

    Ide algoritma ini adalah melakukan penghitungan posisi berdasarkan sebaran harga data. Jadi dengan sejumlah tahapan penghitungan harga dari setiap data dipetakan ke address dari data seharusnya dia berada dalam array yang terurut. Jadi tahapan untuk array X berisi n data adalah sebagai berikut.
    1. Penentuan interval-interval pemetaan awal data. Pemahaman akan pola sebaran data amat bermanfaat untuk mendapatkan fungsi pemetaan yang optimal. Namun tanpa hal itu kita dapat berasumsi bahwa data tersebar secara merata dari data yang terkecil ke yang terbesar. Jadi kita buat pemetaan uniform dengan setiap interval memiliki panjang yang sama. Untuk itu dilakukan penentuan range harga data dan interval rata-rata antar harga data, dan kemudian dilanjutkan dengan pemetaan awal data ke dalam masing-masing interval dan hasilnya disimpan dalam array mapKey. minValue = INFINITY; maxValue = -INFINITY;
      for (i=0; i < n; i++) { if (X[i] > maxValue) maxValue = X[i];
      if (X[i] < minValue) minValue = X[i];       }
      intervalLength = (maxValue-minValue)/(n-1));
      for (i=0; i < n; i++) mapKey[i] = (int)((X[i]-minValue)/intervalLength);

    2. Pencacahan data dalam masing-masing interval berdasarkan mapKey[i]; jika data tersebar secara sempurna pasti setiap interval berisikan satu data. Hasil pencacahan disimpan dalam array hitCount. for (i=0; i < n; i++) hitCount[mapKey[i]]++;

    3. Penentuan hit position setiap data dalam pemetaan (yaitu posisi awal setiap interval dalam data terurut. proxMap[0] = 0;
      for (i=1; i < n; i++) proxMap[i] = proxMap[i-1]+hitCount[i-1];

    4. Mapping setiap data X[i] ke Y[j] dengan j = proxMap[mapKey[i]]. Jika data tersebaran sempurna tentu pemetaan ini akan terjadi relasi 1-1. Karena ada interval-interval yang berisi lebih dari satu data (dan berarti ada interval-interval yang kosong) maka di dalam interval akan dilakukan Insertion Sort. Oleh sebab itu agar apakah suatu posisi sudah terisi atau belum, setiap sel dalam Y perlu diinisialisasi suatu harga yang menunjukkan bahwa ia kosong. for (i=0; i < n; i++) Y[i] = INFINITY;
      for (i=0; i < n; i++) { j = proxMap[mapKey[i]];
      for(k = j+hitCount[mapKey[i]]-2; k >= j; k--) { if (X[i] < Y[k]) Y[k+1] = Y[k];
      else break;       }
      Y[k+1] = X[i];       }

    Jika pengurutan berkaitan dengan array dari data record yang berukuran besar, maka array Y dapat digantikan oleh array Location yang hanya menyimpan posisi seharusnya data itu berada dalam array hasil pengurutan.

    Algoritma ini jika diimplementasikan untuk data key alfanumeris memerlukan fungsi pemetaan yang dapat memetakan key alfanumeris ke dalam bilangan dalam mapKey (atau sering disebut juga sebahai ordinalisasi yang dilakukan pada Hashing).

    Algoritma ini melakukan enam (6) loop-for dan setiap loop-for beriterasi sebanyak n. Best case algoritma ini algoritma ini adalah O(n). Dalam kondisi ekstrim bisa jadi terbentuk interval yang amat gemuk sehingga pada akhirnya akan mendekati operasi Insertion Sort murni bahkan lebih buruk lagi akibat overhead untuk melakukan penghitungan-penghitungan di atas. Secara normal diharapkan interval tidak terbentuk terlalu panjang sehingga operasi Insertion Sort itu pun masih cukup efisien.


    Handout berikutnya, atau sebelumnya, atau kembali ke halaman utama