Prefix, Infix, dan Postfix - Struktur Data

Dalam struktur data yang kita pelajari secara umum ada 3 notasi operasi yang dilakukan untuk suatu operasi aritmatika,yaitu Prefix,Infix,dan postfix.Dan untuk mengetahui notasi-notasi yang diatas itu,sebelumnya kita harus mengenal dan mengetahui indikator yang ada di notasi itu tersebut.

Notasi ini terbentuk dari Operand dan Operator.

Operand adalah data atau nilai yang membantu dalam proses,sedangkan Operasi adalah fungsi yang digunakan dalam proses.

contohnya:

A+B*C

2 + 5 * 3

Keterangan: A ,B ,C ,2 ,3 ,5 adalah Operand.

+,* adalah Operator.

Setelah kita mengenal dan mengetahui dengan Operand dan Operator, maka mari kita mengenal juga tingkat/ level yang ada didalam notasi tersebut:

-( ) (Kurung).

- ^ (Pangkat).

- * / (Perkalian / Pembagian).

- + - (Penjumlahan / Pengurangan).

Notasi ada 3 jenis, yaitu Prefix,Infix dan Postfix yang seperti kita ketahui di atas:

1. Prefix

Prefix adalah notasi yang terbentuk atas operator dengan operand, dimana oprator didepan operand.

contoh: A + B * C (infix).

maka notasi prefixnya adalah: +A*BC.

Pemecahannya:

A+B*C

Diketahui ada 3 operand yaitu: A, B, C dan 2 operand yaitu: +, *.proses dimulai dengan melihat dari hirarkhi oprator.Contoh diatas operator yang tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand yaitu B*C, prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari operand,sehingga fungsi B*C, notasi prefixnya menjadi *BC.

Sehingga hasil sementara dari notasi prefix adalah:

A+*BC

Selanjutnya mencari prefix untuk operator yang berikutnya yaitu +, cara yang dilakukan sama seperti diatas, operator + diapit oleh operand, yaitu A dan *BC, gabungkan operand,sehingga menjadi A*BC,lalu pindahkan operator kedepan operand,sehingga hasil akhir menjadi :

+A*BC.

2. Infix 

Infix adalah notasi yang membentuk atas operator dengan operand,dimana operator berada diantara operand.

Contoh : 

- A + B * C

- (A + B) * C

- A - (B + C) * D ^ E

3.Postfix

Postfix adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.

Contoh : A + B * C ( infix).

maka notasi postfix adalah ABC*+.

Pemecahannya:

A + B * C

Diketahui ada 3 operand yaitu : A,B,C dan 2 operator yaitu : +, *. proses dimulai dengan melihat dari hirarkhi operator.Contoh diatas operator yang tertinggi adalah * kemudian +.

Tanda * diapit oleh kedua operand yaitu B dan C yaitu B*C, postfix dengan menggabungkan operand B dan C menjadi BC,lalu memindahkan operator ke belakang operand C, sehingga fungsi B*C, notasi postfixnya menjadi BC*.Sehingga hasil sementara dari notasi postfix adalah A + BC*

Selanjutnya mencari postfix untuk operator yang berikutnya, yaitu +, dengan cara yang dilakukan sama seperti di atas, operator + diapit oleh 2 operand, yaitu : A dan BC* gabungkan operand tersebut,sehingga menjadi ABC*,lalu pindahkan operator + kebelakang operand ABC*.

Sehingga hasil akhir menjadi : ABC*+.

contoh Notasi Huruf :

Contoh Notasi Angka:

Sumber

Baca

Sorting - Pengurutan Data - Struktur Data

Pengurutan atau “Sorting“ adalah suatu proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu ( untuk data yang bertipe numerik atau karakter).

Dua Macam Pengurutan

• Ascending (urut naik) merupakan pengurutan dari angka yang nilainya lebih kecil kemudian menuju ke nilainya yang lebih besar.
• Descending (urut turun) adalah sebaliknya, yaitu pengurutan dari nilainya yang lebih besar kemudian menuju ke nilainya yang lebih kecil.

Macam-Macam Sorting


1. Bubble Sort

Memindahkan element sekarang dengan elemen berikutnya , jika elemen sekarang itu lebih besar / lebih kecil dari elemen berikutnya maka di tukar (berpindah posisi).

 Ascending

• Data yang paling awal dibandingkan dengan data berikutnya jika ternyata lebih besar maka tukar.
• Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih kecil maka tukar.

Descending

• Data yang paling awal dibandingkan dengan data berikutnya jika ternyata lebih kecil maka tukar.
• Data yang paling akhir dibandingkan dengan data sebelumya jika ternyata lebih besar maka tukar.

Contoh Bubble Sort
Ascending (Urutan Naik) 

2. Exchange Sort

Exchange sort itu sangat mirip dengan buble sort. Bahkan banyak yang mengatakan bahwa exchange sort sama dengan buble sort. Bedanya jika bubble sort proses pertukarannya harus sistematis, dari awal atau dari belakang. Sedangkan exchange sort proses pertukaran hanya akan dilakukan jika diperlukan saja.

1. Ascending

• Jika terdapat elemen sebelumnya lebih besar dari elemen berikutnya maka tukar.
• Jika terdapat elemen sesudahnya lebih kecil dari elemen sebelumnya maka tukar.

2. Descending

• Jika terdapat elemen sebelumnya lebih kecil dari elemen berikutnya maka tukar.
• Jika terdapat elemen sesudahnya lebih besar dari elemen sebelumnya maka tukar.

Contoh Exchange Sort

Ascending (Urutan Naik)

3. Selection Sort

Memindahkan elemen dengan cara membandingkan elemen sekarang dengan elemen yang berikutnya sampai dengan elemen terakhir . Jika ditemukan elemen lain yang lebih kecil / lebih besar dari elemen sekarang maka dicatat posisinya dan kemudian ditukar dan begitu seterusnya.

1. Ascending

• Elemen yang paling besar diletakkan di akhir.
• Elemen yang paling kecil diletakkan di awal.

2. Descending

• Elemen yang paling kecil diletakkan di akhir.
• Elemen yang paling besar diletakkan di awal.

Contoh Selection Sort
Ascending (Urutan Naik)

4. Insertion Sort

Pengurutan yang dilakukan dengan cara membandingkan dengan data ke-2 sampai data terakhir. Jika ditemukan data yang lebih kecil atau lebih besar maka data tersebut disisipkan kedepan sesuai posisi yang seharusnya.

Contoh Insertion Sort
Ascending (Urutan Naik)

5. Shell Sort

Merupakan proses pengurutan data yang sebelumnya acak menjadi data yang terurut dengan cara menentukan jarak antar elemen yang akan dibandingkan.

Contoh Shell Sort
Ascending (Urutan Naik)

6. Merge Sort

Merupakan proses pengurutan data yang menggunakan merging dua buah vector. Pada proses merge sort, data dibuat sepasang-sepasang, yang terdiri dari dua elemen. Jika N ganjil, maka ada satu vector yang terdiri dari 1 elemen. Lalu kemudian data tersebut di merging sampai terurut.

Contoh Merge Sort
Ascending (Urutan Naik)

7. Quick Sort

Merupakan proses penyusunan elemen yang membandingkan suatu elemen (pivot) denan elemen yang lain, dan menyusunnya sedemikian rupa sehingga elemen –elemen lain yang lebih kecil dari pivot terletak disebelah kiri pivot. Dan elemen yang lebih besar dari pivot terletak disebelah kanan pivot.

Dengan demikian akan terbentuk dua sublist, yang terletak disebelah kanan dan kiri pivot. Lalu pada sublist kiri dan kanan itu kita anggap sebuah list baru, dan kita kerjakan proses yang sama seperti yang sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi.

Baca