Merge Sort

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).

Algoritma Merge Sort

Algoritma Merge adalah algoritma yang dijalankan sebagai akibat dari terlalu banyaknya daftar yang diurutkan, dengan menghasilkan lebih banyak daftar yang diurutkan sebagai output. Algoritma merge ini disesuaikan untuk mesin drive tape. Penggunaannya dalam akses memori acak besar yang terkait telah menurun, karena banyak aplikasi algoritma merge yang mempunyai alternatif lebih cepat ketika kamu memiliki akses memori acak yang menjaga semua data mu. Hal ini disebabkan algoritma ini membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel.

Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan.

Algoritma Merge umumnya memiliki satu set pointer p0..n yang menunjuk suatu posisi di dalam satu set daftar L0..n . Pada awalnya mereka menunjuk item yang pertama pada setiap daftar. Algoritmanya sebagai berikut:

Selama p0..n masih menunjuk data yang di dalam sebagai pengganti pada akhirnya:

   1. Melakukan sesuatu dengan data item yang menunjuk daftar mereka masing-masing.

   2. Menemukan pointers points untuk item dengan kunci yang paling rendah; membantu salah satu pointer untuk item yang berikutnya dalam daftar.

Daftar isi

[sembunyikan]

    * 1 Pseudocode

    * 2 Implementasi Algoritma Merge menggunakan MATLAB

    * 3 Analisis

    * 4 Penggunaan

    * 5 Referensi

Suatu implementasi pseudocode sederhana yang tak berulang dari penggabungan dengan dua daftar yang mungkin tertulis sebagai berikut:

function merge(a, b)

        var list result

        var int i, j := 0

       

        while (i < length(a)) and (j < length(b))

                if a[i] < b[j]

                        add a[i] to result

                       i := i + 1

                else

                        add b[j] to result

                        j := j + 1

        while i < length(a)

                add a[i] to result

                i := i + 1

        while j < length(b)

                add b[j] to result

                j := j + 1

        

        return result

[sunting] Implementasi Algoritma Merge menggunakan MATLAB M-File

 function p=merge(a,b)

 % MERGE Penggabungan

 % MERGE(A,B) menggabungkan dua list

 if nargin<2

     error('Kekurangan argumen input');

 end % pengecekan error

    a=a(:); % meyakinkan bahwa input merupakan vektor baris

    b=b(:);

    na=length(a); % menemukan panjang a dan b

    nb=length(b);

    df=a+b; % hasil dari daftar

    ndf=length(df);

    p=[zeros(1,nb-na) a]+[zeros(1,na-nb) b];

Command window

  >> a=[1 2 3]

     a =

          1     2     3

  >> b=[2 3 4]

     b =

          2     3     4

  >> merge(a,b)

     ans =

          3

          5

          7

  >> p=[3 5 7]

     p =

          3     5     7

  >> for i=1:3

         x=a(i)+p(i)

     end

     x =

          4

     x =

          7

     x =

         10

  >> for j=1:3

         y=b(j)+p(j)

     end

     y =

         5

     y =

          8

     y =

         11

Pada umumnya algoritma merge berjalan dalam waktu proposional untuk penjumlahan pada panjangnya daftar; Algoritma merge beroperasi pada bilangan besar dalam daftar yang akan segera mengalikan penjumlahan panjangnya daftar pada saat itu untuk keluaran gambar pointers points yang mana menunjuk pada item yang paling rendah, yang dapat terpengaruhi dengan suatu heap(tumpukan) yang didasarkan prioritas antrian dalam O(lg n) waktu, untuk O(m lg n) waktu (dimana n adalah bilangan pada daftar yang digabungkan, m adalah penjumlahan panjangnya daftar, dan lg adalah log basis 2). Ketika menggabungkan panjang m dua daftar, terdapat suatu perbandingan lompatan yang lebih rendah 2m-1 yang ada dalam kasus terburuk.

Keluaran data item Merge klasik (satu yang digunakan dalam merge sort) dengan kunci yang paling rendah pada langkah masing-masing, memberikan beberapa daftar yang diurutkan, hasil daftar yang diurutkan berisi semua unsur-unsur di dalam daftar input manapun, dan hal itu dilakukan agar waktunya proporsioal untuk input penjumlahan panjangnya daftar.

Penggabungan dapat juga digunakan untuk berbagai hal:

    * Diberikan satu set saldo-saldo rekening yang beredar dan satu set transaksi, kedua-duanya disortir oleh nomor rekening, menghasilkan satu saldo-saldo rekening baru setelah transaksi diterapkan; ini selalu diperlukan untuk mempercepat ”transaksi baru” penunjuk ketika keduanya mempunyai kunci yang sama, dan menambahkan semua angka-angka pada tape yang manapun dengan nomor rekening yang sama untuk menghasilkan saldo yang baru.

    * Menghasilkan suatu daftar catatan yang disortir dengan menyajikan kunci disemua daftar ini yang memerlukan outputting kapan saja suatu catatan yang semua kunci p0..n adalah sama.

    * Dengan cara yang sama untuk menemukan bilangan besar pada satu tape yang lebih kecil dibandingkan masing-masing nomor pada satu tape yang lainnya (contoh untuk mengeluarkan gambar pengelompokan pajak masing-masing orang di dalamnya).

    * Dengan cara yang sama untuk menghitung perbedaan set semua arsip dalam satu daftar dengan arsip yang tidak sesuaian dengan yang lainnya.

    * Operasi penyisipan dalam mesin pencarian untuk menghasilkan suatu indeks balikkan.

    * Menggabungkan permainan-permainan adalah suatu peranan pusat dalam fungsi pemrograman teknik Dijkstra untuk menghasilkan bilangan-bilangan tetap.

Source Code Merge Sort

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

void printv(char* in, int *v, int n) {

            printf("%s", in);

            int i = 0;

            for (; i < n; ++i)

                        printf("%d ", v[i]);

            printf("\n");

}

void merge(int *v, int p, int q, int r) {

            int i = p;

            int j = q + 1;

           

            int *tmp = (int*)malloc((r - p + 1) * sizeof(int));

            int k = 0;

           

            while ((i <= q) && (j <= r)) {

                        if (v[i] < v[j])

                                    tmp[k++] = v[i++];

                        else

                                    tmp[k++] = v[j++];

            }

           

            while (i <= q)

                        tmp[k++] = v[i++];

           

            while (j <= r)

                        tmp[k++] = v[j++];

           

            memcpy(v + p, tmp, (r - p + 1) * sizeof(int));

            free(tmp);

}

void mergeS(int *v, int p, int r) {

            if (p < r) {

                        int q = (p + r) / 2;

                        mergeS(v, p, q);

                        mergeS(v, q + 1, r);

                        merge(v, p, q, r);

            }

}

int main(int argc, char *argv[]) {

            int n = 10;

            int v[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1};

            printv("V: ", v, n);

            mergeS(v, 0, n - 1);

            printv("V: ", v, n);

           

            return 0;

}

MULTIRING FILE

MULTIRING FILE

I.        Pengertian Multiring File

      Multiring File merupakan metode pengorganisasian file yang berorientasi pada pemrosesan subset dari record secara efisien. Subset tersebut digambarkan sebagai grup dari beberapa record yang terdiri dari nilai atribut yang biasa. Contohnya “Semua pekerja yang berbicara bahasa Perancis”.

      Subset dari record dihubungkan bersama secara eksplisit menggunakan pointer. Rantai penghubung ini menentukan urutan anggota dari subset. Setiap subset mempunyai record kepala yang merupakan record awal dari suatu rantai. Sebuah record kepala berisi informasi yang berhubungan dengan seluruh record anggota di bawahnya. Record-record kepala ini juga dapat dihubungkan menjadi sebuah rantai.

      Tipe rantai tertentu yang digunakan untuk menggambarkan hal ini dinamakan  ring, yang merupakan rantai di mana pointer anggota terakhir digunakan untuk menunkuk record kepala dari rantai. Ring-ring dapat disarangkan dalam banyak level kedalaman. Dalam hal ini record anggota dari ring level ke-i record kepala ring bawahan pada level i-1. Ring level terbawah, yang berisi data terakhir, selalu dianggap berada pada level 1.

      Gambar berikut menunjukkan hirarki sederhana dari struktur ring yang berhubungan.

      Bila contoh di atas menjadi record secara individual, maka ilustrasinya sebagai berikut.

      Pencarian dalam Multiring File adalah dengan menelusuri rantai sampai atribut nilai yang dicari ditemukan. Kemudian rantai baru dimasuki untuk menemukan atribut recod bawahan. Proses ini diulang terus sampai record yang diinginkan ditemukan.

II.     Interlinked Rings

      Untuk pertanyaan (query) yang lebih spesifik, yaitu pertanyaan anggota rantai bawahan seperti “Daftar semua tukang patri di suatu perusahaan”, dara sebelumnya kurang efisien karena memerlukan pencarian yang melelahkan. Untuk keperluan ini digunakan struktur ring sebagai berikut.

Panah Bachman digunakan untuk menunjukkan bahwa pada kotak yang ditunjuk memiliki banyak record.

      Bila kita ekspansikan contoh di atas dengan memisahkan pekerja dalam berbagai lokasi ke dalam departemen-departemen yang lebih spesifik, memungkinkan akses dengan urutan senioritas, dan tambahkan warehouse pada setiap lokasi dan biarkan informasi stock tersedia. Struktur diagramnya tampak sebagai berikut.

      Hubungan di antara ring-ring tidak harus hirarkis. Hubungan dapat diimplementasi dengan merelasikan anggota dalam ring-ring yang sama, yang menyediakan banyak lintasan di antara record-record, atau menghubungkan ring-ring pada level yang lebih rendah kembali ke ring-ring dengan level lebih tinggi.

      Efektivitas dari sebuah proses dalam melokasikan sebuah record sangat bergantung pada kecocokan pasangan atribut yang membentuk argument pertanyaan dengan struktur dari file. Bila file tidak diorganisasikan secara benar, maka proses tidak dapat berjalan secara efisien, dan dibutuhkan intervensi dari pengguna.

III.  Struktur dari Multiring File

      Semua record mempunyai struktur yang sama dalam Multiring File, tetapi isi dan ukuran merupakan fungsi dari ring-ring di mana mereka berada. Sebuah Multiring File dapat mempunyai sejumlah kategori record yang berbeda. Di sini definisi file telah menyimpang dari definisi awal. Di sini record-record tidak sama formatnya, dan keanggotaan ring serta keanggotaan file harus diketahui sebelum pemrosesan.

      Format record yang sebenarnya bergantung pada kombinasi dari tipe-tipe ring di mana record tersebut menjadi anggota. Pasangan nilai atrinbut mengidentifikasi dirinya seperti pada pile. Tetapi biasanya tidak seperti itu, dan tiap record akan mempunyai pengidentifikasi tipe record.

      Pada contoh berikut, field t mengidentifikasi record ini sebagai record pekerja. Tiap record dengan tipe t akan mempunyai field data yang sama dan 7 field pointer. Pengidentifikasi ini akan memungkinkan referensi ke sebuah deskripsi format recod yang tepat, disimpan dengan deskripsi umum  dari file.

      Untuk menghubungkan record-record ke dalam ring-ring mereka, pointer-pointer akan muncul dalam sebuah record yang umum. Sebuah record dapat dimiliki oleh ring-ring sebanyak jumlah pointer yang dimilikinya.

      Dapat juga terdapat field-field data NULL, tetapi karena terdapat bayak tipe record dengan tujuan spesifik, file secara keseluruhan relative padat.

      Setiap ring pasti memiliki kepala. Kepala ini dapat berupa poin masukan, anggota dari ring lain, atau keduanya. Ketika sebuah ring dimasuki dalam sebuah pencarian, poin masukan dicatat sehingga ring ini tidak dimasuki 2 kali.

IV.  Manipulasi Ring

      Umumnya organisasi Multiring File menghindari penggandaan data dengan menempatkan data biasa kepada semua anggota ring ke dalam record kepala dari ring. Efek negatifnya adalah dalam desain dasar ring, ketika sebuah record diambil berdasarkan kombinasi kata kunci pencarian, hasilnya yang dapat diaplikasikan dengan record tidak selalu dapat dilakukan dengan hanya atribut yang disimpan dalam anggota atau record kepala yang diakses selama pencarian sepanjang 1 lintasan.

      2 alternatif yang digunakan, yaitu:

1.        Pencarian Paralel melalui semua ring yang diidentifikasi dalam kata kunci pencarian dapat dilakukan, dengan menghilangkan pada record-record pada persimpangan ring-ring tersebut.

2.        Pencarian Inisial dapat dilakukan berdasarkan atribut dengan efektivitas mempartisi terbaik. Record-record yang dikumpulkan kemudian dicek untuk ketepatan dengan menempatkan record kepala untuk tipe atribut lain yang diperlukan dan menolak record dengan nilai data yang tidak tepat.

Proses yang kedua di atas diaplikasikan dengan langkah-langkah sebagai berikut.

            Query:

            Find an Employee with Location ="Thule" and Profession="Welder".

                Enter Location chain;

                For each member record determine if key = Thule;

                When found followEmplo yee chain;

                        For every Employee record the profession must be determined

                            Follow the profession chain;

                            When its header record is reached,

                                    then inspect profession header for key = Welder

                                    If the field matches the search key

                                        then Employee member record becomes output;

                        Continue with the next Employee record;

                When its header record, the Location = Thule is reached,

                        then the result is complete.

V.     Keputusan Desain Ring File

      Lama penelusuran rantai berbanding lurus dengan ukuran rantai. Ukuran rantai-rantai individu dapat dikurangi dengan menambah jumlah rantai-rantai dan jumlah level dalam struktur file.

      Hal ini digambarkan dengan rumus sebagai berikut.

                  y = ^x√n            dengan x = level

                                                      y = panjang rantai

                                                      n = record count

      Waktu pencarian untuk record dengan level terendah berkurang secara proporsional sampai akar ke-x dari record count, n, dan bertambah secara proporsional sampai level x.

      Sebuah atribut yang tidak mempartisi file ke dalam banyak level tidak sangat berguna seperti elemen ring.

       Peng-Cluster-an Ring

            Record yang sering diakses bersama paling baik disimpan dengan derajat lokalitas yang tinggi. Satu ring umumnya dapat diletakkan seluruhnya dalam 1 silinder, seingga semua pencarian dihindari saat penelusuran cluster ring ini.

            Ketika referensi berulang-ulang kepada record kepala ring dibutuhkan, kepala record itu dapat berpartisipasi dalam cluster. Ring berikutnya dengan level lebih tinggi akan sulit untuk berpartisipasi, kecuali jika ruangan total yang dibutuhkan semua anggota record dan pendahulunya cukup kecil untuk disimpan dalam satu atau beberapa silinder.

            Dalam perubahan database yang dinamis, peng-cluster-an yang optimal sulit untu dijaga dan keuntungannya sedikit. Sebuah reorganisasi diperlukan untuk mengembalikan cluster-cluster.

       Pengkategorian Atribut Real

            Atribut yang merepresentasikan data real atau kontinyu tidak menyediakan partisi yang efektif kecuali jika dikategorikan secara artificial.

VI.        Penggunaan Multiring File

      Struktur Multiring merupakan dasar untuk beberapa database terbesar yang digunakan saat ini. Sistem informasi manajemen di mana banyak melibatkan tabulasi, penjumlahan, dan laporan pengecualian telah diimplementasikan menggunakan daftar Multiring ini.

      Beberapa masalah dalam representasi ruang geografis dan arsitektur juga telah diselesaikan dengan pendekatan Multiring. Perkembangan saat ini dalam system multifile terintegrasi bergantung pada kapabilitas yang disediakan oleh struktur ring. Masalahnya adalah desain yang cermat berdasarkan pengetahuan tentang data dan pola penggunaan diperlukan sebelum Multiring File dapat diimplementasikan.

VII.          Kinerja Multiring

      Kinerja system Multiring sangat bergantung pada kecocokan dari penandaan atribut ke ring-ring tertentu.

       Ukuran record dalam Multiring File

            Karena banyak tipe record yang berbeda dalam Multiring File, estimasi akurat didapatkan hanya dengan mendaftar semua tipe, dengan frekuensi dan ukuran masing-masing.

       Pengambilan record dalam Multiring File

            Waktu untuk mengambil sebuah record adalah fungsi dari jumlah dan panjang rantai yang dicari. Panjang daripada ring bergantung pada ukuran file, jumlah level, dan seberapa baik file dipartisi ke dalam ring-ring.

       Pengambilan record berikutnya dari Multiring File

            Record berikutnya untuk urutan yang berhubungan dapat ditemukan dengan menelusuri rantai tersebut.

       Pemasukan ke dalam Multiring File

            Penambahan record ke dalam Multiring File dilakukan dengan menentukan spasi kosong yang cocok untuk record, menempatkan semua pendahulu untuk record baru, mengambil nilai dari link yang tepat dari pendahulu, menetapkannya ke dalam record baru, dan menempatkan nilai dari posisi record baru ke dalam area-area link pendahulu.

       Meng-Update record dalam Multiring File

            Jika hanya field data yang akan dirubah, update hanya memerlukan penemuan record dan penulisan ulang.

       Membaca seluruh Multiring File

            Pembacaan menurut rantai memerlukan bahwa sebuah record kepala diakses untuk setiap ring tambahan. Baik record kepala baru maupun lama diperlukan untuk bergerak di antara 2 ring.

       Reorganisasi Mutiring File

            Reorganisasi sebenarnya tidak diperukan sebagau bagian dari prosedur operasi normal. Hanya saat pemformatan ulang tipe record diperlukan, record-record seperti itu harus ditulis ulang, Ini hanya memerlukan reorganisasi parsial dari file, karena perubahan terbatas pada ring-ring pada level-level yang menggunakan tipe-tipe record itu.