STACK
PENGERTIAN STACK
Arti istilah stack dianggap berkaitan erat dengan pengertian Tumpukan, bertumpuk, dan bertimbun.
Seperti sama-sama dipahami, pekerjaan pada komputer diolah berdasarkan pengalamatan-pengalamatan yang diatur sedemikian rupa. Begitu juga saat terjadi suatu interrupt. Saat komputer menyelesaikan suatu interrupt yang ditemukannya, maka komputer kembali melacak pekerjaan sebelumnya. Informasi pengalamatan tentang pekerjaan sebelumnya tadi disimpan dalam suatu register khusus yang dikenal sebagai sebuah stack.
Stack merupakan tumpukan data yang disimpan pada media penyimpanan. Untuk kasus ini media yang digunakan adalah register khusus tadi.
“Top “ merupakan pintu untuk keluar masuknya elemen – elemen stack. A, B, dan C merupakan suatu koleksi. Dari ilustrasi dapat digambarkan bahwa C merupakan elemen yang terakhir memasuki stack namun pertama keluar dari stack. Begitu sebaliknya dengan A. A merupakan elemen pertama yang memasuki tumpukan namun terakhir saat keluar dari tumpukan.
Di dalam gambar juga terlihat urutan masuk dan keluar yang berkebalikan. Elemen yang masuk pertama akan keluar erakhir dan sebaliknya. Prinsip ini telah dikenal dalam struktur data dengan nama prinsip LIFO (Last In First Out).
Di dalam pengembangannya, stack dapat dikelompokkan menjadi dua bagian. Dua bagian tersebut yaitu Single Stack dan Double Stack.
Single Stack
Single Stack atau Stack Tunggal adalah stack yang hanya terdiri dari satu koleksi. Bila stack ini direpresentasikan dengan array, maka pengisian dan penghapusan harus dilakukan bertahap dari indeks TOP-nya.
Di dalam proses single stack terdapat tiga macam proses utama, yaitu :
- Inisialisasi
- PUSH (Insert, Masuk, Simpan, Tulis)
- POP (Delete, Keluar, Ambil, Baca, Hapus)
Istilah-istilah STACK
Grafik batang bertumpuk.
Melebihi kapasitas tumpukan. Melebihi kapasitas memory.
register penunjuk stack. Stack merupakan mekanisme penting pada sistem komputer, biasanya ...
Stack beberapa elemen OSI layer yang sudah didefinisikan, seperti gosip, Map, atau Top, dan ...
lihat stack
GRAPH
Pengertian Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :
G = (V, E)
Dimana
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
G = (V, E)
Dimana
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
Sebuah graph mungkin hanya terdiri dari satu simpul
Sebuah graph belum tentu semua simpulnya terhubung dengan busur
Sebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain
Sebuah graph mungkin semua simpulnya saling berhubungan
Graph tak berarah (undirected graph atau non-directed graph) :
Urutan simpul dalam sebuah busur tidak dipentingkan. Mis busur e1 dapat disebut busur AB atau BA
Sebuah graph belum tentu semua simpulnya terhubung dengan busur
Sebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain
Sebuah graph mungkin semua simpulnya saling berhubungan
Graph tak berarah (undirected graph atau non-directed graph) :
Urutan simpul dalam sebuah busur tidak dipentingkan. Mis busur e1 dapat disebut busur AB atau BA
Graph berarah (directed graph) :
Urutan simpul mempunyai arti. Mis busur AB adalah e1 sedangkan busur BA adalah e8.
Graph Berbobot (Weighted Graph)
Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.
Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.
Istilah pada graph
Urutan simpul mempunyai arti. Mis busur AB adalah e1 sedangkan busur BA adalah e8.
Graph Berbobot (Weighted Graph)
Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.
Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.
Istilah pada graph
Incident
Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.
Degree (derajat), indegree dan outdegree
Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.
Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.
Degree (derajat), indegree dan outdegree
Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.
PENGERTIAN SORTING SORT
Sorting Sort adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu.
Pada umumnya terdapat 2 cara pengurutan data yaitu
– Ascending : Pengurutan dilakukan mulai dari nilai terkecil menuju nilai terbesar
– Descending: Pengurutan dilakukan mulai dari nilai terbesar menuju nilai terkecil
Ada beberapa macem metoda pengurutan data diantaranya :
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
@. Bubble Sort
pengertian bubble sort
Bubble sort adalah sederhana algoritma sorting. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. Bekerja dengan berulang kali melakukan melalui daftar akan di sortir, membandingkan dua item sekaligus dan swapping mereka jika mereka berada di salah pesanan. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Yang melewati daftar diulang sampai swap tidak diperlukan, yang menunjukkan bahwa daftar disaring. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Algoritma yang mendapatkan namanya dari jalan kecil elemen "gelembung" ke bagian atas daftar. Because it only uses comparisons to operate on elements, it is a comparison sort . Karena hanya menggunakan perbandingan untuk beroperasi pada elemen, ia adalah perbandingan menyortir.
Bubble sort-kasus yang terburuk dan rata-rata kompleksitas kedua О (n ²), dimana n adalah jumlah item yang disortir. There exist many sorting algorithms with the substantially better worst-case or average complexity of O ( n log n ). Di sana ada banyak algoritma sorting dengan lebih baik substansial terburuk-kasus atau rata-rata kompleksitas O (n log n). Therefore bubble sort is not a practical sorting algorithm when n is large, except in rare specific applications where the array is known to be very close to being already sorted initially. Oleh karena itu gelembung menyortir tidak praktis algoritma sorting ketika n adalah besar, kecuali di langka di mana aplikasi spesifik deret diketahui sangat dekat dengan yang telah disortir awalnya.
Langkah-langkah oleh-contoh
Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm. Mari kita nomor yang deret "5 1 4 2 8", dan menyusun deret dari terendah ke nomor terbesar nomor menggunakan gelembung sort Algoritma. In each step, elements written in bold are being compared. Dalam setiap langkah, unsur-unsur yang ditulis dalam huruf tebal sedang dibandingkan.
First Pass: Pertama Pass:
( 5 1 4 2 8 ) (5 1 4 2 8) \ untuk ( 1 5 4 2 8 ) Here, algorithm compares the first two elements, and swaps them. (1 5 4 2 8) Di sini, Algoritma membandingkan dua elemen pertama, dan mereka swap.
( 1 5 4 2 8 ) (1 5 4 2 8) \ untuk ( 1 4 5 2 8 ) (1 4 5 2 8)
( 1 4 5 2 8 ) (1 4 5 2 8) \ untuk ( 1 4 2 5 8 ) (1 4 2 5 8)
( 1 4 2 5 8 ) (1 4 2 5 8) \ untuk ( 1 4 2 5 8 ) Now, since these elements are already in order, algorithm does not swap them. (1 4 2 5 8) Sekarang, sejak elemen ini sudah dalam rangka, algoritma tidak swap mereka.
Second Pass: Kedua Pass:
( 1 4 2 5 8 ) (1 4 2 5 8) \ untuk ( 1 4 2 5 8 ) (1 4 2 5 8)
( 1 4 2 5 8 ) (1 4 2 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
Now, the array is already sorted, but our algorithm does not know if it is completed. Kini, deret sudah disortir, tetapi kami tidak Algoritma tahu jika sudah selesai. Algorithm needs one whole pass without any swap to know it is sorted. Algoritma satu kebutuhan seluruh lulus tanpa swap untuk mengetahui itu disortir.
Third Pass: Ketiga Pass:
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
Finally, the array is sorted, and the algorithm can terminate. Akhirnya, deret disaring, dan algoritma dapat menghentikan.
[ edit ] Pseudocode implementation [Sunting] Pseudocode pelaksanaan
A simple way to express bubble sort in pseudocode is as follows: Cara mudah untuk menyortir ekspres gelembung di pseudocode adalah sebagai berikut:
procedure bubbleSort( A : list of sortable items ) defined as: do swapped := false for each i in 0 to length( A ) - 1 do: if A[ i ] > A[ i + 1 ] then swap( A[ i ], A[ i + 1 ] ) swapped := true end if end for while swapped end procedure
The algorithm can also be expressed as: Algoritma yang juga dapat dinyatakan sebagai:
procedure bubbleSort( A : list of sortable items ) defined as: for each i in 1 to length(A) do: for each j in length(A) downto i + 1 do: if A[ j - 1 ] > A[ j ] then swap( A[ j - 1], A[ j ] ) end if end for end for end procedure
The difference between this and the first pseudocode implementation is discussed later in the article . Perbedaan antara ini dan pertama pelaksanaan pseudocode dibahas dalam artikel nanti.
[ edit ] Alternative implementations [Sunting] Alternatif implementasi
One way to optimize bubblesort is to note that, after each pass, the largest element will always move down to the end. Salah satu cara untuk mengoptimalkan bubblesort adalah untuk dicatat bahwa, masing-masing setelah lulus, terbesar elemen akan selalu berpindah ke akhir. During each comparison, it is clear that the largest element will move downwards. Selama setiap perbandingan, jelas bahwa unsur terbesar akan berpindah ke bawah. Given a list of size n , the n th element will be guaranteed to be in its proper place. Mengingat daftar ukuran n, n th elemen yang akan dijamin untuk berada di tempat yang tepat. Thus it suffices to sort the remaining n - 1 elements. Oleh karena itu cukup untuk memilah sisa n - 1 elemen. Again, after this pass, the n - 1 th element will be in its final place. Sekali lagi, setelah lulus ini, yang n - 1 th elemen akan di tempat yang terakhir.
pengertian bubble sort
Bubble sort adalah sederhana algoritma sorting. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. Bekerja dengan berulang kali melakukan melalui daftar akan di sortir, membandingkan dua item sekaligus dan swapping mereka jika mereka berada di salah pesanan. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Yang melewati daftar diulang sampai swap tidak diperlukan, yang menunjukkan bahwa daftar disaring. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Algoritma yang mendapatkan namanya dari jalan kecil elemen "gelembung" ke bagian atas daftar. Because it only uses comparisons to operate on elements, it is a comparison sort . Karena hanya menggunakan perbandingan untuk beroperasi pada elemen, ia adalah perbandingan menyortir.
Bubble sort-kasus yang terburuk dan rata-rata kompleksitas kedua О (n ²), dimana n adalah jumlah item yang disortir. There exist many sorting algorithms with the substantially better worst-case or average complexity of O ( n log n ). Di sana ada banyak algoritma sorting dengan lebih baik substansial terburuk-kasus atau rata-rata kompleksitas O (n log n). Therefore bubble sort is not a practical sorting algorithm when n is large, except in rare specific applications where the array is known to be very close to being already sorted initially. Oleh karena itu gelembung menyortir tidak praktis algoritma sorting ketika n adalah besar, kecuali di langka di mana aplikasi spesifik deret diketahui sangat dekat dengan yang telah disortir awalnya.
Langkah-langkah oleh-contoh
Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm. Mari kita nomor yang deret "5 1 4 2 8", dan menyusun deret dari terendah ke nomor terbesar nomor menggunakan gelembung sort Algoritma. In each step, elements written in bold are being compared. Dalam setiap langkah, unsur-unsur yang ditulis dalam huruf tebal sedang dibandingkan.
First Pass: Pertama Pass:
( 5 1 4 2 8 ) (5 1 4 2 8) \ untuk ( 1 5 4 2 8 ) Here, algorithm compares the first two elements, and swaps them. (1 5 4 2 8) Di sini, Algoritma membandingkan dua elemen pertama, dan mereka swap.
( 1 5 4 2 8 ) (1 5 4 2 8) \ untuk ( 1 4 5 2 8 ) (1 4 5 2 8)
( 1 4 5 2 8 ) (1 4 5 2 8) \ untuk ( 1 4 2 5 8 ) (1 4 2 5 8)
( 1 4 2 5 8 ) (1 4 2 5 8) \ untuk ( 1 4 2 5 8 ) Now, since these elements are already in order, algorithm does not swap them. (1 4 2 5 8) Sekarang, sejak elemen ini sudah dalam rangka, algoritma tidak swap mereka.
Second Pass: Kedua Pass:
( 1 4 2 5 8 ) (1 4 2 5 8) \ untuk ( 1 4 2 5 8 ) (1 4 2 5 8)
( 1 4 2 5 8 ) (1 4 2 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
Now, the array is already sorted, but our algorithm does not know if it is completed. Kini, deret sudah disortir, tetapi kami tidak Algoritma tahu jika sudah selesai. Algorithm needs one whole pass without any swap to know it is sorted. Algoritma satu kebutuhan seluruh lulus tanpa swap untuk mengetahui itu disortir.
Third Pass: Ketiga Pass:
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
( 1 2 4 5 8 ) (1 2 4 5 8) \ untuk ( 1 2 4 5 8 ) (1 2 4 5 8)
Finally, the array is sorted, and the algorithm can terminate. Akhirnya, deret disaring, dan algoritma dapat menghentikan.
[ edit ] Pseudocode implementation [Sunting] Pseudocode pelaksanaan
A simple way to express bubble sort in pseudocode is as follows: Cara mudah untuk menyortir ekspres gelembung di pseudocode adalah sebagai berikut:
procedure bubbleSort( A : list of sortable items ) defined as: do swapped := false for each i in 0 to length( A ) - 1 do: if A[ i ] > A[ i + 1 ] then swap( A[ i ], A[ i + 1 ] ) swapped := true end if end for while swapped end procedure
The algorithm can also be expressed as: Algoritma yang juga dapat dinyatakan sebagai:
procedure bubbleSort( A : list of sortable items ) defined as: for each i in 1 to length(A) do: for each j in length(A) downto i + 1 do: if A[ j - 1 ] > A[ j ] then swap( A[ j - 1], A[ j ] ) end if end for end for end procedure
The difference between this and the first pseudocode implementation is discussed later in the article . Perbedaan antara ini dan pertama pelaksanaan pseudocode dibahas dalam artikel nanti.
[ edit ] Alternative implementations [Sunting] Alternatif implementasi
One way to optimize bubblesort is to note that, after each pass, the largest element will always move down to the end. Salah satu cara untuk mengoptimalkan bubblesort adalah untuk dicatat bahwa, masing-masing setelah lulus, terbesar elemen akan selalu berpindah ke akhir. During each comparison, it is clear that the largest element will move downwards. Selama setiap perbandingan, jelas bahwa unsur terbesar akan berpindah ke bawah. Given a list of size n , the n th element will be guaranteed to be in its proper place. Mengingat daftar ukuran n, n th elemen yang akan dijamin untuk berada di tempat yang tepat. Thus it suffices to sort the remaining n - 1 elements. Oleh karena itu cukup untuk memilah sisa n - 1 elemen. Again, after this pass, the n - 1 th element will be in its final place. Sekali lagi, setelah lulus ini, yang n - 1 th elemen akan di tempat yang terakhir.
Metode Bubble Sort
Perhatikan bahwa jumlah pertukaran dan perbandingan data tidaklah tetap, perbedaan tergantung pada keadaan awal data setelah diacak.
Tabel berikut memperlihatkan tabulasi hasil visualisasi menggunakan metode bubble sort.
Pengacakan | Jumlah Total | |
Pertukaran Data | Perbandingan Data | |
1 | 155 | 279 |
2 | 127 | 272 |
3 | 137 | 245 |
4 | 142 | 297 |
5 | 151 | 294 |
6 | 138 | 285 |
7 | 178 | 300 |
8 | 165 | 272 |
9 | 156 | 285 |
10 | 175 | 300 |
Rata-rata | 152 | 283 |
Jumlah rata-rata pertukaran untuk 10 kali pengacakan adalah 152 kali, sedangkan rata-rata jumlah perbandingan adalah sebanyak 283 kali. Tetapi bila data pada awalnya terurut, maka untuk 25 jumlah data, jumlah pertukaran data sebanyak 0 kali dengan jumlah perbandingan sebanyak 24 kali.
contoh program
#include
#define MAX_LINE 1024
void discardnewline(char s[])
{
int i;
for(i = 0; s[i] != ”; i++)
{
if(s[i] == ‘\n’)
s[i] = ”;
}
}
int reverse(char s[])
{
char ch;
int i, j;
for(j = 0; s[j] != ”; j++)
{
}
–j;
for(i = 0; i 0)
{
discardnewline(line);
reverse(line);
printf(”%s\n”, line);
}
return 0;
}
@. Selection Sort
Pengertian tentang selection sort adalah Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
SOURCE CODE
void insertsort (int x[], int n)
{
int i, k, y
for (k=1, k
y=x [k];
for (i=k-1;i>=0&&y
x[i+1]=y;
}
}
@. Insertion Sort
Pengertian Insertion Sort adalah Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
SOURCE CODE
void insertsort (int x[], int n)
{
int i, k, y
for (k=1, k
y=x [k];
for (i=k-1;i>=0&&y
x[i+1]=y;
}
}
@. Merge Sort
Pengertian Merge Sort 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. 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.
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.
B.Contoh Algoritma 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 dua 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 sub set untuk menyimpan hasilnya.
Untuk Merge Sort dalam beberapa bahasa pemrograman yang ada pada saat ini untuk listing programnya hampir sama. Berikut ini merupakan salah satu contoh Listing Program yang biasa digunakan.
Contoh:
void MergeSort(int l,int r) {
if (l <>
MergeSort(l,(l+r)/2);
MergeSort((l+r)/2,r);
Merging();
}
}
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.
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.
B.Contoh Algoritma 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 dua 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 sub set untuk menyimpan hasilnya.
Untuk Merge Sort dalam beberapa bahasa pemrograman yang ada pada saat ini untuk listing programnya hampir sama. Berikut ini merupakan salah satu contoh Listing Program yang biasa digunakan.
Contoh:
void MergeSort(int l,int r) {
if (l <>
MergeSort(l,(l+r)/2);
MergeSort((l+r)/2,r);
Merging();
}
}
@. Quick Sort
Pengerian Quick Sort 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. 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.
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.
B.Contoh Algoritma 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 dua 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 sub set untuk menyimpan hasilnya.
Untuk Merge Sort dalam beberapa bahasa pemrograman yang ada pada saat ini untuk listing programnya hampir sama. Berikut ini merupakan salah satu contoh Listing Program yang biasa digunakan.
Contoh:
void MergeSort(int l,int r) {
if (l <>
MergeSort(l,(l+r)/2);
MergeSort((l+r)/2,r);
Merging();
}
}
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.
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.
B.Contoh Algoritma 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 dua 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 sub set untuk menyimpan hasilnya.
Untuk Merge Sort dalam beberapa bahasa pemrograman yang ada pada saat ini untuk listing programnya hampir sama. Berikut ini merupakan salah satu contoh Listing Program yang biasa digunakan.
Contoh:
void MergeSort(int l,int r) {
if (l <>
MergeSort(l,(l+r)/2);
MergeSort((l+r)/2,r);
Merging();
}
}
TREE
PENGERTIAN TREE
Akar (Root nodes)
Simpul yang paling atas dalam pohon adalah akar (root node). Menjadi simpul teratas, simpul akar tidak akan memiliki orang tua. Ini merupakan simpul di mana biasanya merupakan tempat untuk memulai operasi dalam pohon (walaupun beberapa algoritma dimulai dengan daun dan berakhir pada akar). Semua simpul yang lain dapat dicapai dari akar dengan menelusuri pinggiran atau pranala. (Dalam definisi resmi, setiap jalan adalah khas). Dalam diagram, ini secara khusus di gambar paling atas. Di beberapa pohon, seperti heap, akar memiliki sifat khusus. Setiap simpul dalam sebuah pohon dapat dilihat sebagai akar dari sub pohon yang berakar pada simpul tersebut.
Daun (Leaf nodes)
9, 14, 19, 67 dan 76 adalah daun.
Semua simpul yang berada pada tingkat terendah dari pohon dinamakan daun (leaf node). Sejak mereka terletak pada tingkat paling bawah, mereka tidak memiliki anak satupun. Seringkali, daun merupakan simpul terjauh dari akar. Dalam teori grafik, sebuah daun adalah sebuah sudut dengan tingkat 1 selain akar (kecuali jika pohonnya hanya memiliki satu sudut; maka akarnya adalah daunnya juga). Setiap pohon memiliki setidaknya satu daun.
Dalam pohon berdasarkan genetic programming sebuah daun (juga dibilang terminal) adalah bagian terluar dari sebuah program pohon. Jika dibandingkan dengan fungsinya atau simpul dalam, daun tidak memiliki argumen. Di banyak kasus dalam daun-GP input ke programnya.
Simpul dalam (Internal nodes)
Sebuah simpul dalam adalah semua simpul dari pohon yang memiliki anak dan bukan merupakan daun. Beberapa pohon hanya menyimpan data didalam simpul dalam, meskipun ini mempengaruhi dinamika penyimpanan data dalam pohon. Sebegai contoh, dengan daun yang kosong, seseorang dapat menyimpan sebuah pohon kosong dengan satu daun. Bagaimanapun juga dengan daun yang dapat menyimpan data, tidak dimungkinkan untuk menyimpan pohon kosong kecuali jika seseorang memberikan beberapa jenis penanda data di daun yang menandakan bahwa daun tersebut seharusnya kosong (dengan demikian pohon itu seharusnya kosong juga).
Sebaliknya, beberapa pohon hanya menyimpan data dalam daun, dan menggunakan simpul dalam untuk menampung metadata yang lain, seperti jarak nilai dalam sub pohon yang berakar pada simpul tersebut. Jenis pohon ini berguna untuk jarak yang meragukan.
Sub pohon (Subtrees)
Sebuah sub pohon adalah suatu bagian dari pohon struktur data yang dapat dilihat sebagai sebuah pohon lain yang berdiri sendiri. Simpul apapun dalam pohon P, bersama dengan seluruh simpul dibawahnya, membentuk sebuah sub pohon dari P. Sub pohon yang terhubung dengan akar merupakan keseluruhan pohon tersebut. Sub pohon yang terhubung dengan simpul lain manapun dinamakan sub pohon asli (proper subtree).
Penyusunan pohon
Terdapat dua jenis pohon. Sebuah pohon tidak terurut (unordered tree) adalah sebuah pohon dalam arti struktural semata-mata, yang dapat dikatakan memberikan sebuah simpul yang tidak memiliki susunan untuk anak dari simpul tersebut. Sebuah pohon dengan suatu susunan ditentukan, sebagai contoh dengan mengisi bilangan asli berbeda ke setiap anak dari simpul tersebut, dinamakan sebuah pohon terurut (ordered tree), dan struktur data yang dibangun didalamnya dinamakan pohon terurut struktur data (ordered tree data structures). Sejauh ini pohon terurut merupakan bentuk umum dari pohon struktur data. Pohon biner terurut merupakan suatu jenis dari pohon terurut.
Hutan
Sebuah hutan adalah sebuah himpunan yang terdiri dari pohon terurut. Lintasan inorder, preorder, dan postorder didefinisikan secara rekursif untuk hutan.
* inorder
1. lewati inorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
2. kunjungi akar dari pohon pertama.
3. lewati inorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
* preorder
1. kunjungi akar dari pohon pertama.
2. lewati preorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
3. lewati preorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
* postorder
1. lewati postorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
2. lewati postorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
3. kunjungi akar dari pohon pertama.
Penggambaran pohon
Ada banyak cara untuk menggambarkan pohon; pada umumnya penggambaran mewakili simpul sebagai rekor yang dialokasikan pada heap (bedakan dengan heap struktur data) yang mengacu pada anaknya, ayahnya, atau keduanya, atau seperti data materi dalam array, dengan hubungan diantaranya ditentukan oleh posisi mereka dalam array (contoh binary heap)
Pohon sebagai grafik
Dalam teori grafik, sebuah pohon adalah sebuah grafik asiklis yang terhubung. Pohon yang berakar merupakan sebuah grafik dengan sudut tunggal diluar sebagai akar. Dalam kasus ini, dua sudut apapun yang terhubung dengan sebuah sisi mewarisi hubungan orang tua dan anak. Sebuah grafik asiklis dengan bermacam-macam komponen yang terhubung atau himpunan dari pohon-pohon yang berakar kadang-kadang dipanggil hutan Metode traversal
Melangkah melalui materi dari pohon, dengan arti dari hubungan antara orang tua dan anak, dinamakan menelusuri pohon, dan tindakannya adalah sebuah jalan dari pohon. Seringkali, sebuah operasi mungkin dapat dilakukan sebagai penunjuk ysng mengacu pada simpul khusus. Sebuah penelusuran dimana setiap simpul ayah dikunjungi sebelum anaknya dinamakan pre-order walk; sebuah penelusuran dimana anaknya dikunjungi sebelum ayahnya masing-masing dinamakan post-order walk.
Operasi umum
* Menghitung seluruh materi (item)
* Pencarian untuk sebuah materi
* Menambahkan sebuah materi pada sebuah posisi tertentu dalam pohon
* Menghapus sebuah materi
* Mengeluarkan seluruh bagian dari sebuah pohon pruning
* Menambahkan seluruh bagian ke sebuah pohon grafting
* Menemukan akar untuk simpul apapun
Penggunaan umum
* Memanipulasi data secara hierarki
* Membuat informasi mudah untuk dicari
* Memanipulasi data sorted lists
