Quick Sort

Walah setelah tadi ngubek ngubek kembali tugas kuliah, eh ternyata ada satu lagi metode sorting yang kelupaan namanya Quick Sort. wadoh kok bisa jadi pelupa gini sih. Ok mulai aja penjelasnnya

Algoritma Quick Sort ini terdiri dari 4 langkah utama:

1. Jika struktur data terdiri dari 1 atau 0 elemen yang harus diurutkan, kembalikan struktur data itu apa adanya.

2. Ambil sebuah elemen yang akan digunakan sebagai pivot point (poin poros). (Biasanya elemen yang paling kiri.)

3. Bagi struktur data menjadi dua bagian – satu dengan elemen-elemen yang lebih besar

daripada pivot point, dan yang lainnya dengan elemen-elemen yang lebih kecil daripada pivot point.

4. Ulangi algoritma secara rekursif terhadap kedua paruh struktur data.

Function quicksort(num: TabInt,
left,right: integer -> TabInt
{mengurut tabel integer [1 .. N]
dengan Quick Sort}
Kamus:
pivIdx: integer {indeks pivot}
pivNewIdx: integer {indeks pivot
yang baru}
Algoritma:
if (right > left) then
pivIdx <- left
{pengambilan pivot point bisa
apa saja / random}
pivNewIdx <- partition (num,left,right,pivIdx) quicksort(num,left,pivNewIdx-1) quicksort(num,pivNewIdx+1,right) -> num
Function partition(num: TabInt,
left,right,pivIdx: integer)-> integer
Kamus:
pivVal: integer {penyimpan
sementara nilai pivot}
storeIdx,i: integer
Algoritma:
pivVal <-num[pivIdx]
swap(num[pivIdx],num[right])
{memindahkan pivot ke akhir}
storeIdx <- left
i traversal [left..right]
{left ≤ i < right}
if (num[i] ≤ pivVal)
swap (num[i],num[storeIdx])
storeIdx <- storeIdx + 1 swap (num[storeIdx],num[right]) -> storeIdx

Hehehe ini beneran metode yang terkahir. Mudah mudahan gag pelupa lagi.

Merge Sort

Algoritma Merge Sort ditemukan oleh John von Neumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut,

1. Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada

sebuah list yang besar.

2. Untuk membentuk sebuah list terurut dari dua buah list terurut membutuhkan langkah yang lebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut. Contoh: hanya diperlukan satu kali traversal untuk masing-masing list jika keduanya sudah terurut

Function mergesort(num,temp: TabInt,
N: integer) -> TabInt
{mengurut tabel integer [0 .. N-1]
dengan Merge Sort}
Kamus:
Algoritma:
-> m_sort(num, temp, 0, N-1)
Function m_sort(num,temp: TabInt,
left,right: integer) -> TabInt
Kamus:
left,right,result: TabInt
mid: integer
Algoritma:
if (right > left)
mid <- (right + left) / 2 m_sort(num,temp,left,mid) m_sort(num,temp,mid+1,right) ->merge(num,temp,left,mid+1,
right)
Function merge (num,temp: TabInt,
left,mid,right: integer)-> TabInt
Kamus:
i,left_end: integer
num_el,tmp_pos: integer
Algoritma:
left_end <- mid-1
tmp_pos <- left
num_el <- right-left+1
while (left ≤ left_end) and (mid ≤
right) do
if (num[left] ≤ num[mid]) then
temp[tmp_pos] <- num[left]
tmp_pos <- tmp_pos + 1
left <- left +1
else
temp[tmp_pos] <- num[mid]
tmp_pos <- tmp_pos + 1
mid <- mid + 1
while (left ≤ left_end) do
temp[tmp_pos] <- num[left]
left <- left + 1
tmp_pos <- tmp_pos + 1
while (mid ≤ right) do
temp[tmp_pos] <- num [mid]
mid <- mid + 1
tmp_pos <- tmp_pos + 1
i traversal [0..num_el]
num[right] <- temp[right]
right <- right – 1 -> num

Akhirnya tentang sorting selesai . Moga bermanfaat bagi semua

Insertion Sort

Cara kerja insertion sort sebagaimana namanya. Pertama-tama, dilakukan iterasi, dimana di setiap iterasi insertion sort memindahkan nilai elemen, kemudian menyisipkannya berulang-ulang sampai ke tempat yang tepat. Begitu seterusnya dilakukan. Dari proses iterasi, seperti biasa, terbentuklah bagian yang telah di-sorting dan bagian yang belum.

Procedure InsertionSort
(Input/Output T: TabInt, Input N:
integer)
{mengurut tabel integer [1 .. N]
dengan Insertion Sort secara
ascending}
Kamus:
i: integer
Pass: integer
Temp: integer
Algoritma:
Pass traversal [2..N]
Temp <- TPass
i <- i-1 while (j ≥ 1) and (Ti > Temp) do
Ti+1 <- Ti
i <- i-1
Ti+1 <-Temp
{T[1..Pass-1] terurut}

Selection Sort

Algoritma sorting sederhana yang lain adalah Selection Sort. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending

(menaik), elemen yang paling kecil di antara elemen elemen yang belum urut, disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian ditukar. Perhatikan Larik di bawah ini

Dalam satu kali pass, ditentukan elemen yang paling kecil di dalam bagian list yang belum urut. Elemen yang paling kecil ini, diwarnai merah muda. Untuk bagian larik yang telah diurutkan diberi warna biru muda.

Procedure
SelectionSort
(Input/Output T: TabInt, Input N:
integer)
{mengurut tabel integer [1 .. N]
dengan Selection Sort secara
ascending}
Kamus:
i: integer
Pass: integer
min: integer
Temp: integer
Algoritma:
Pass traversal [1..N-1]
min <- Pass
i traversal [Pass+1..N]
if (Ti < Tmin) then
min <- j
Temp <- TPass
TPass<- Tmin
Tmin <- Temp
{T[1..Pass] terurut}

Bubble Sort (Gelembung Air)

Bubble sort merupakan salah satu jenis sorting. Bubble sort ada metode sorting termudah. Diberikan nama “bubble” karena konsep dari algoritmanya diibaratkan seperti gelembung air untuk elemen struktur data yang seharusnya pada posisi awal. Bubble sort mengurut data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Dimana cara kerjanya adalah dengan berulang-ulang melakukan proses looping ( perulangan) terhadap elemen-elemen struktur data yang belum diurutkan. Nilai dari masing-masing elemen akan dibandingkan selama proses looping tersebut .jika selama proses looping tersebut ditemukan ada urutannya tidak sesuai dengan permintaan, maka akan dilakukan proses pemukaran (swap).
Dari setiap iterasi, Nilai yang terbesar akan menempati posisi paling kanan

Dari setiap iterasi, Nilai yang terbesar akan menempati posisi paling kanan
• Jika terdapat N data, maka iterasi harus diulang sebanyak N-1

Algortitma Bubble Sorting

Procedure BubbleSort (Input/Output
T: TabInt, Input N: integer)
{mengurut tabel integer [1 .. N]
dengan Bubble Sort}
Kamus:
i: integer
Pass: integer
Temp: integer
Algoritma:
Pass traversal [1..N-1]
i traversal [N..Pass+1]
if (Ti < Ti-1) then
Temp <- Ti
Ti <- Ti-1
Ti-1 <- Temp
{T[1..Pass] terurut}

Manajemen Sistem Berkas

File atu berkas adalah representasi program dan data yang berupa kumpulan informasi yang saling berhubungan dan disimpan di perangkat penyimpanan. Sistem berkas ini sangatlah penting, karena informasi atau data yang disimpan dalam berkas adalah sesuatu yang sangat berharga bagi pengguna. Sistem operasi harus dapat melakukan operasi-operasi pada berkas, seperti membuka, membaca, menulis, dan menyimpan berkas tersebut pada sarana penyimpanan sekunder. Oleh karena itu, sistem operasi harus dapat melakukan operasi berkas dengan baik.

Sistem operasi melakukan manajemen sistem berkas dalam beberapa hal:

• Pembuatan berkas atau direktori. Berkas yang dibuat nantinya akan diletakkan pada direktori-direktori yang diinginkan pada sistem berkas. Sistem operasi akan menunjukkan tempat dimana lokasi berkas atau direktori tersebut akan diletakkan. Setelah itu, sistem operasi akan membuat entri yang berisi nama berkas dan lokasinya pada sistem berkas.

• Penghapusan berkas atau direktori. Sistem operasi akan mencari letak berkas atau direktori yang hendak dihapus dari sistem berkas, lalu menghapus seluruh entri berkas tersebut, agar tempat dari berkas tersebut dapat digunakan oleh berkas lainnya.

• Pembacaan dan menulis berkas. Proses pembacaan dan penulisan berkas melibatkan pointer yang menunjukkan posisi dimana sebuah informasi akan dituliskan di dalam sebuah berkas.

Membuat Berkas (Create):

Pertama, tempat baru di dalam sistem berkas harus di alokasikan untuk berkas yang akan dibuat.

Kedua, sebuah direktori harus mempersiapkan tempat untuk berkas baru, kemudian direktori tersebut akan mencatat nama berkas dan lokasinya pada sistem berkas.

Untuk membuat suatu berkas baru, program aplikasi memanggil logical file system. Logical file system mengetahui format dari struktur direktori. Untuk membuat berkas baru, logical file system akan mengalokasikan FCB, membaca direktori yang benar ke memori, memperbaharui dengan nama berkas dan FCB yang baru dan menulisnya kembali ke dalam disk. Beberapa sistem operasi, termasuk UNIX, memperlakukan berkas sebagai direktori. Sistem operasi Windows NT mengimplementasi beberapa system calls untuk berkas dan direktori. Windows NT memperlakukan direktori sebagai sebuah kesatuan yang berbeda dengan berkas. Logical file system dapat memanggil file-organization module untuk memetakan direktori I/O ke disk-block numbers, yang dikirimkan ke sistem berkas dasar dan I/O control system. File- organization module juga mengalokasikan blok untuk penyimpanan data-data berkas. Setelah berkas selesai dibuat, mula-mula harus dibuka terlebih dahulu. Perintah open dikirim nama berkas ke sistem berkas. Ketika sebuah berkas dibuka, struktur direktori mencari nama berkas yang diinginkan. Ketika berkas ditemukan, FCD disalin ke ke tabel system-wide open-file pada memori. Tabel ini juga mempunyai entri untuk jumlah proses yang membuka berkas tersebut. Selanjutnya, entri dibuat di tabel per-process open-file dengan penunjuk ke entri di dalam tabel system-wide open-file. Seluruh operasi pada berkas akan diarahkan melalui penunjuk ini.

Menulis sebuah berkas (Write):

Menulis pada sebuah berkas Untuk menulis pada berkas, kita menggunakan system call beserta nama berkas yang akan ditulisi dan informasi apa yang akan ditulis pada berkas. Ketika diberi nama berkas, system mencari ke direktori untuk mendapatkan lokasi berkas. Sistem juga harus menyimpan penunjuk tulis pada berkas dimana penulisan berikut akan ditempatkan. Penunjuk tulis harus diperbaharui setiap terjadi penulisan pada berkas. •

Membaca Sebuah berkas (Read):

Membaca sebuah berkas Untuk dapat membaca sebuah berkas, dapat menggunakan system call beserta nama berkas di blok memori mana berkas berikutnya diletakkan. Direktori mencari berkas yang akan dibaca dan system menyimpan penunjuk baca pada berkas dimana pembacaan berikutnya akan terjadi. Ketika pembacaan dimulai, penunjuk harus diperbaharui. Sehingga secara umum, suatu berkas ketika sedang dibaca atau ditulis, kebanyakan system hanya mempunyai satu penunjuk, baca dan tulis menggunakan penunjuk yang sama, hal ini menghemat tempat dan mengurangi kompleksitas system

Menghapus Berkas (Delete):

Untuk menghapus berkas kita perlu mencari berkas tersebut di dalam direktori. Setelah ditemukan kita membebaskan tempat yang dipakai berkas tersebut (sehingga dapat digunakkan oleh berkas lain ) dan menghapus tempatnya lagi di direktori