Heap Sort

Heap Sort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort. Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n.

Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT). Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priorit y queue. Algoritma pengurutan heap dimulai dari membangun sebuah heap dari kumpulan data yang ingin diurutkan, dan kemudian menghapus data yang mempunyai nilai tertinggi dan menempatkan dalam akhir dari larik yang telah terurut. Setelah memindahkan data dengan nilai terbesar, proses berikutnya adalah membangun ulang heap dan memindahkan nilai terbesar pada heap tersebut dan menempatkannya dalam tempat terakhir pada larik terurut yang belum diisi data lain.  Proses ini berulang sampai tidak ada lagi data yang tersisa dalam heap dan larik yang terurut penuh. Dalam implementasinya kita membutuhkan dua larik – satu untuk menyimpan heap dan satu lagi untuk menyimpan data yang sudah terurut. Tetapi untuk optimasi memori, kita dapat menggunakan ha nya satu larik saja. Yaitu dengan cara menukar isi akar dengan elemen terakhir dalam heap tree. Jika memori tidak menjadi masalah maka dapat tetap menggunakan dua larik yaitu larik masukan dan larik hasil.

Heap Sort memasukkan data masukan ke dalam struktur data heap. Nilai terbesar (dalam max-heap) atau nilai terkecil (dalam min-heap) diambil satu per satu sampai habis, nilai tersebut diambil dalam urutan yang terurut.

 Contoh :

 

Konversi array menjadi Heap. Tentukan node terakhir dalam array, yaitu K.

Read More

Pseudocode BFS dan DFS

ALGORITHM DFS(G)

//Implements a depth-first search traversal of a given graph

//Input: Graph G =V,E

/*Output: Graph G with its vertices marked with consecutive integers in the order they are first encountered by the DFS traversal*/

mark each vertex in V with 0 as a mark of being “unvisited”

count ←0

for each vertex v in V do

if v is marked with 0

dfs(v)

dfs(v)

//visits recursively all the unvisited vertices connected to vertex v

//by a path and numbers them in the order they are encountered

//via global variable count

count ←count + 1; mark v with count

for each vertex w in V adjacent to v do

if w is marked with 0

dfs(w)

ALGORITHM BFS(G)

//Implements a breadth-first search traversal of a given graph

//Input: Graph G = V,E

/*Output: Graph G with its vertices marked with consecutive integers in the order they are visited by the BFS traversal*/

mark each vertex in V with 0 as a mark of being “unvisited”

count ←0

for each vertex v in V do

if v is marked with 0

bfs(v)

bfs(v)

//visits all the unvisited vertices connected to vertex v

//by a path and numbers them in the order they are visited

//via global variable count

count ←count + 1; mark v with count and initialize a queue with v

while the queue is not empty do

for each vertex w in V adjacent to the front vertex do

if w is marked with 0

count ←count + 1; mark w with count

add w to the queue

remove the front vertex from the queue

Sumber : Levitin A. Introduction to the design and analysis of algorithms

Read More

Sekilas Ilmu: Fungsi dan Prosedur

            Prosedur

Prosedur dalam bahasa C adalah suatu program terpisah dalam blok sendiri yang berfungsi sebagai subprogram dan digunakan di dalam blok program yang lainnya dengan cara menyebutkan judul prosedurnya. Prosedur tidak mengembalikan suatu nilai keluaran yang didapat dari hasil proses fungsi tersebut. Prosedur banyak digunakan pada program yang terstruktur, karena:

1.      Merupakan penerapan konsep program modular, yaitu memecah program yang rumit menjadi program-program bagian yang lebih sederhana dalam bentuk prosedur-prosedur.

2.    Untuk hal-hal yang sering dilakukan berulang-ulang, cukup dituliskan sekali saja dalam prosedur dan dapat dipanggil atau dipergunakan sewaktu-waktu bila diperlukan.

            Fungsi

       Fungsi dalam bahasa C adalah suatu kumpulan program yang mengerjakan suatu tugas spesifik tertentu yang bertujuan sama dengan prosedur yaitu untuk memecah program yang rumit menjadi lebih sederhana. Fungsi mempunyai output dengan tipe variabel yang kita tentukan harus menggunakan parameter dalam penggunaannya, berbeda dengan prosedur yang bisa tidak menggunakan parameter. 

Read More

Program Mencari Huruf dalam Sebuah Kata

Program ini menggunakan pointer, dimana kita perlu menginput kata yang akan digunakan, kemudian input posisi huruf yang ingin dicari.

Hasil akhir (Output) dari program ini adalah :

-----------------------------------------------------------------------------------

#include<stdio.h>

#include<conio.h>

main(){

       char*ptr;

       char ptr2;

       int angka;

       char kata[10];

       printf("\nKata awal : ");

       gets(kata);

       ptr=kata;

       printf("\nPosisi huruf yang ingin dicari: ke- ");

       scanf("%d", &angka);

       ptr2=*(ptr+(angka-1));

       printf("\nMencetak huruf ke-%d: \n\n", angka);

       printf("Kata: %s\n\n", kata);

       printf("Huruf ke-%d: %c\n",angka, ptr2);

       return 0;

}

------------------------------------------------------------------------------------

Selamat mencoba!

Read More