Rabu, 26 November 2014

ALGORITMA DAN PEMROGRAMAN 1A

NAMA: CYNTHIA MANURUNG

KELAS: 1IA17

NPM: 52414474

DOSEN: KUNTO BAYU

1. Argumen dan Fungsi

Tabel merupakan data pembantu dalam pengolahan data. Contohnya dalam suatu lembar dokumen terdapat data mahasiswa sebagai berikut :

Dari data pegawai tersebut tidak dapat diketahui nama setiap mahasiswa. Untuk itu dapat dibuat suatu tabel yang berisi khusus untuk nama mahasiswa seperti dibawah ini :

Item NIP merupakan item yang dipakai sebagai acuan untuk mencari data nama pegawai di dalam tabel. Item ini berfungsi sebagai kontrol field yang sering disebut ARGUMEN. Sedang item NAMA merupakan FUNCTION dari tabel tersebut.

2. Penggunaan Storage untuk Penyimpanan Tabel

Data di dalam media penyimpanan seperti disk, kartu, dokumen dll yang berfungsi sebagai tabel disebut Eksternal Tabel.

Dalam proses pengolahan data, eksternal tabel ini sebaiknya dipindahkan ke memori agar proses menjadi cepat.

Di dalam memori eksternal tabel menempati lokasi yang disebut storage. Di storage ini terbentuk suatu tabel yang disebut sebagai Internal Tabel. Selanjutnya proses pengolahan data menggunakan internal tabel.

Perhatikan flowchart diatas. Terlihat bahwa setiap data yang dibaca dari external tabel disimpan didalam NPMTAB(I) dan NMTAB(I). Variabel ini merupakan variabel berindeks atau sering disebut sebagai variabel array.

Variabel array merupakan satu variabel dengan beberapa tempat penyimpanan.

Gambar dibawah ini memperlihatkan ilustrasi variabel array NPMTAB.

Penyimpanan ke dalam variabel array NPMTAB dilakukan berdasarkan nilai indeksnya. Pada flowchart di atas nilai indeks ditentukan melalui variabel I. Pada saat data NPM pertama diinput, nilai I = 1. Dengan demikian NPM yang pertama diinput disimpan didalam variabel NPMTAB(1), demikian seterusnya. Sehingga terbentuk variabel NPMTAB dan NMTAB dengan isi seperti yang terlihat dibawah ini.

3. Proses Pencarian (Searching)

Proses pencarian (searching) didalam internal tabel dilakukan dengan berpatokan pada nilai indeksnya. Misalnya untuk mencari nama pegawai dengan NPM = 163483 maka dapat digambarkan melalui flowchart berikut :

Flowchart di atas disusun dengan asumsi internal tabel telah terbentuk. Proses pencarian nama mahasiswa dapat diurutkan sebagai berikut :

a. Pada awal proses, variabel NO diisi nilai sesuai dengan NPM yang akan dicari. Sedangkan variabel I digunakan sebagai indeks untuk menentukan posisi variabel array internal tabel.

b. Nilai I ditambah 1.

c. Periksa isi variabel NIPTAB dengan lokasi sesuai indeks pada variabel I. Jika isinya sama dengan isi variabel NO, lakukan :

· cetak isi variabel NMTAB dengan lokasi sesuai indeks pada variabel I

· proses selesai. Sebaliknya, jika isinya tidak sama lakukan langkah d

d. Kembali ke langkah b

Contoh Penerapan Konsep Tabel :

Dalam suatu lembar dokumen terdapat data Gaji Pegawai dan Tabel Nama Pegawai

Data Gaji Pegawai

Tabel Nama Pegawai

Jika Gaji dihitung berdasarkan GAJI POKOK + TUNJANGAN, maka buat flowchart untuk mencetak laporan seperti berikut :

Flowchart yang terbentuk :

4. Pengurutan dengan Eksternal Tabel

a. Pembentukan File Indeks

· Proses pengurutan bilangan dilakukan di internal tabel. Semua bilangan yang akan diurutkan disimpan dahulu ke suatu penyimpanan di dalam memori yaitu variabel array.

· Di memori, proses pengurutan dapat dilakukan dengan lebih cepat. Namun jika datanya banyak, maka proses ini akan membutuhkan ukuran memori yang besar. 8Untuk menghindarinya, proses pengurutan dilakukan di dalam eksternal tabel.

· Eksternal tabel dibentuk dengan cara membuat file baru. File ini desebut sebagai File Indeks. Isi file indeks adalah field yang berfungsi sebagai field kunci (key field) dari record data yang akan diurutkan. Key Field merupakan field yang dipakai sebagai dasar pengurutan. Misal data yang harus diurutkan berdasarkan NIP, maka field kuncinya adalah field yang berisi NIP.

Secara garis besar, proses pengurutan dengan eksternal tabel terdiri dari langkah-langkah

· Bentuk file indeks yang hanya berisi field kunci.

· Lakukan pengurutan pada file indeks. Pengurutan dapat dilakukan dengan metode bubble sort atau straight selection.

· Pindahkan record dari file lama ke file baru dengan posisi record sesuai pada file indeks.

b. Proses Pembentukan File Indeks

PEG.DTA

Jika data di file PEG.DTA ingin diurutkan berdasarkan NIP, maka harus dibentuk file indeks yang hanya berisi field NIP. Proses pembentukan file indeks ini dapat digambarkan melalui flowchart :

Berdasarkan flowchart diatas, terbentuk file indeks yaitu INDEKS.DTA

Sumber: http://athiananfa.blogspot.com/2014/11/penerapan-konsep-tabel-pada-algoritma.html

ALGORITMA DAN PEMROGRAMAN 1A

NAMA: CYNTHIA MANURUNG
KELAS : 1IA17
NPM: 52414474
DOSEN: KUNTO BAYU

TEKNIK SWITCHING

Definisi :
Tehnik Switching merupakan cara memperpendek jalur proses yang memakai suatu indikator untuk mengantisipasi proses yang akan dilakukan selanjutnya. Indikator ini dimisalkan seperti switch pada tombol lampu yang dapat mengatur dua kondisi yaitu nyala dan padam.

Dalam flowchart, switch merupakan variabel yang (biasanya) diisi dengan dua kondisi yaitu 0 dan 1. Melalui isi variabel tersebut dapat diketahui kondisi proses yang telah dilakukan. Sehingga dapat dilakukan pengalihan proses tanpa melalui proses sebelumnya atau mempersingkat alur proses.

contoh:
Suatu perusahaan akan membuat laporan gaji pegawainya berdasarkan golongannya. Data yang dibaca terdiri dari nomor pegawai, nama pegawai, golongan dan gaji bersih. Data yang dibaca sudah urut per golongan yang terdiri dari : golongan 1, 2, 3, 4. Jika golongan berubah maka cetak TOTAL GAJI per golongan dan ganti halaman baru serta NOMOR dimulai dari 1.
Pada akhir laporan cetak TOTAL SELURUH GAJI yaitu jumlah total gaji seluruh golongan.

Flowchart :

Database :

CREATE TABLE `gaji` (
`nopeg` varchar(10) NOT NULL,
`nama` varchar(10) NOT NULL,
`golongan` int(1) NOT NULL,
`gaji` decimal(12,0) NOT NULL,
PRIMARY KEY (`nopeg`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1

Script :
Flowchart diatas saya terjemahkan ke script. Untuk mudahnya saya menggunakan bahasa PHP + database MySQL. Script saya tulis dengan aplikasi gPHPEdit, Kompozer dibantu dengan tool Adee HTML to PHP Converter dan Adee HTML Parser :-)

$dbhost = 'localhost';
$dbuser = 'root';
$dbpass = 'server';
$dbname = 'latihan';
$sw = 0;
$tot_gaji_gol=0;
$tot_gaji_all=0;
$no=0;
$gol_current=0;
$flag_awal=0;

$conn = mysql_connect($dbhost, $dbuser, $dbpass) or die ('Error Koneksi');
mysql_select_db($dbname);

$perintah = "select * from gaji order by golongan asc";
$hasil=mysql_query($perintah);

while ($row=mysql_fetch_array($hasil)){
$nopeg=$row["nopeg"];
$nama=$row["nama"];
$golongan=$row["golongan"];
$gaji=$row["gaji"];
$no=$no+1;

if($golongan <> $gol_current) {
$gol_current = $golongan;
$sw=0;
}

//cek switch, jika 0 cetak judul & header tabel, ubah switch jadi 1
if($sw==0){
//tutup tabel
if ($flag_awal > 0) {
echo "

";
echo "";
echo "Total Gaji : " . $tot_gaji_gol;
echo "
";
}
//cetak judul
echo "Tabel Gaji PT.ABC";
echo "
";
echo "";
echo " ";
echo "";
echo "";
echo "";
echo "";
echo "";
echo " ";
$sw=1;
$flag_awal=$flag_awal+1;
$gol_current=$golongan;
$tot_gaji_gol = 0;
}

echo " ";
echo "";
echo "";
echo "";
echo "";
echo "";
echo " ";
$tot_gaji_gol=$tot_gaji_gol + $gaji;
$tot_gaji_all =$tot_gaji_all + $gaji;

}
// tutup tabel
echo "";
echo "

NO	NOPEG	NAMA	GOLONGAN	GAJI
$no	$nopeg	$nama	$golongan	$gaji

";
echo "Total Gaji : " . $tot_gaji_gol;
echo "
";
echo "Total Seluruh Gaji : " . $tot_gaji_all;

?>

sumber: irma14.blogspot.com

Senin, 24 November 2014

Ilmu Sosial Dasar

PERGAULAN BEBAS

Remaja adalah masa peralihan dari kanak-kanak ke dewasa. Para ahli pendidikan sependapat bahwa remaja adalah mereka yang berusia antara 13 tahun sampai dengan 18 tahun.Seorang remaja sudah tidak lagi dapat dikatakan sebagai kanak-kanak, namun masih belum cukup matang untuk dapat dikatakan dewasa.berbicara tentang pergaulan dikalangan remaja terutama pergaulan yang bebas tentu saja kita akan banyak membicarakan sebab akibatnya .Di zaman globalisasi ini, remaja harus diselamatkan dari dampak globalisasi. Karena globalisasi ini ibaratnya kebebasan dari segala aspek. Sehingga banyak kebudayaan-kebudayaan yang asing yang masuk, sementara tidak cocok dengan kebudayaan di negara tertentu yang melanggar aturan norma yang berlaku.Terutama negara-negara yang masih menerapkan adat ketimuran termasuk negara kita yaitu indonesia. Sebagai contoh kebudayaan asing yaitu free sexs itu tidak cocok dengan kebudayaan kita. Pada saat ini,menurut saya kebebasan bergaul sudah sampai pada tingkat yang mengkhawatirkan. Para remaja dengan bebas dapat bergaul antar jenis,Tidak jarang dijumpai pemandangan di tempat-tempat umum, para remaja saling berangkulan mesra tanpa memperdulikan masyarakat sekitarnya yang banyak merupakan orang tua. Mereka sudah mengenal istilah pacaran sejak awal masa remaja. Pacar, bagi mereka merupakan salah satu bentuk gengsi yang membanggakan. Akibatnya, di kalangan remaja kemudian terjadi persaingan untuk mendapatkan pacar.

Bahaya Pergaulan Bebas Di kalangan Remaja

Kasus yang muncul akibat pergaulan bebas di kalangan remaja semakin meningkat dimana-mana.Perilaku menyimpang dikalangan remaja atau yang biasa disebut dengan kenakalan remaja bentuknya bermacam-macam seperti perkelahian secara perorangan atau kelompok, tawuran pelajar, mabuk-mabukan, pemerasan, pencurian, perampokan, penganiayaan, penyalahgunaan narkoba, dan seks bebas pranikah, Bentuk-bentuk kenakalan yang demikian biasa disebut juga dengan pergaulan bebas. Bentuk kenakalan remaja itu sering kita jumpai di kalangan remaja saat ini baik di lingkungan kita maupun jauh dari lingkungan kita.

Perilaku yang penuh dengan kebebasan seringkali mengarah pada kenakalan yang sangat mencemaskan dan Sangat menyedihkan saat perilaku ini mengakibatkan tingginya jumlah penyimpangan dikalangan remaja. Penyimpangan-penyimpangan yang kasusnya makin marak dan menarik untuk dibahas adalah pergaulan bebas atau lebih spesifiknya disebut seks bebas.

Karena Dari tahun ke tahun kasus seks bebas di negeri ini makin banyak saja jumlahnya, dan tak dapat dipungkiri bahwa sebagian pelakunya adalah remaja (pelajar dan mahasiswa) para pelajar pun dimulai dari saat mereka SMP,sungguh miris!. Di berbagai media pemberitaan baik media massa ataupun media elektronik, yang namanya kasus seks bebas selalu saja muncul dan menimbulkan kekhawatiran orang tua.Banyak orang tua yang cenderung menutup anak-anaknya dari dunia luar dengan tujuan menjauhkan dari kemungkinan terkena pergaulan bebas,tapi cara ini juga dapat menjadikan anak menjadi individu yang anti sosial.Masalah ini semakin complicated,setiap orang sellau bertanya bagaimana mengurangi maraknya kasus seks bebas di kalangan pelajar maupun siswa?jawaban dari pertanyaan ini adalah kembali ke pribadi masing-masing. Tetapi masih banyak cara yang dapat dilakukan untuk mencegah pergaulan bebas ini,andil orang tua dalam pencegahan sangatlah besar karena mulai dari rumah pencegahan ini dilakukan,orang tua dapat memberikan didikan yang benar dan menanamkan norma agama seta norma kesopanan sejak dini kepada anak-anak mereka. Sehingga saat mereka keluar dari rumah dan berinteraksi denganberbagai orang yang memiliki sifat dan perilaku beragam dia telah memiliki pondasi yang kuatdari keluarga dan agamanya. Banyak orang bilang bahwa masa remaja merupakan masa yang rentan, seorang anak dalam menghadapi gejolak biologisnya dan masa remaja itu masa dimana anak-anak selalu ingin tahu dan mencoba sesuatu yang membuat mereka penasaran biasa di sebut masa pencarian jatidiri. Apalagi ditunjang dengan era globalisasi dan era informasi yang sedemikian rupa menyebabkan remaja sekarang terpancing untuk coba-coba mempraktekkan apa yang dilihatnya dari internet. Terlebih bila apa yang dilihatnya merupakan informasi tentang indahnya seks bebas yang bisa membawa dampak pada remaja itu sendiri.Lebih parahnya tentang seks bebas, menurut beberapa penelitian menunjukkan bahwa tujuh dari dari sepuluh perempuan telah melakukan hubungan seksual sebelum berumur 20 tahun. Sementara satu dari enam pelajar perempuan aktif bergaul seks bebas. Paling sedikit mereka berganti pasangan dengan empat laki-laki yang berbeda-beda. Kenyataan tersebut menunjukkan betapa ironisnya kondisi remaja kita saat ini.

Ciri-Ciri Pergaulan Bebas

Penghamburan harta untuk memenuhi keinginan sexs bebasnya
Upaya mendapatkan harta dan uang dengan menghalalkan segala cara termasuk dari jalan yang haram dan keji
Menimbulkan perilaku munafik dalam masyarakat
Rasa ingin tahu yang besar
Rasa ingin mencoba dan merasakan
Terjadi perubahan-perubahan emosi, pikiran, lingkungan pergaulan dan tanggung jawab yang dihadapi
Mudah mengalami kegelisahan, tidak sabar, emosional, selalu ingin melawan, rasa malas, perubahan dalam keinginan, ingin menunjukkan eksistensi dan kebanggaan diri serta selalu ingin mencoba dalam banyak hal.
Kesukaran yang dialami timbul akibat konflik karena keinginannya menjadi dewasa dan berdiri sendiri dan keinginan akan perasaan aman sebagai seorang anak dalam keluarganya.
Banyak mengalami tekanan mental dan emosi
Terjerat dalam pesta hura-hura ganja, putau, ekstasi, dan pil-pil setan lain

Dampak Dari Pergaulan Bebas

Pergaulan bebas identik sekali dengan yang namanya “dugem” (dunia gemerlap). Yang sudah menjadi rahasia umum bahwa di dalamnya marak sekali pemakaian narkoba dan mengkonsumsi minuman keras. Ini identik sekali dengan adanya seks bebas,yang akhirnya berujung kepada HIV/AIDS, dan penyakit lainnya. Dan pastinya setelah terkena virus ini kehidupan remaja akan menjadi sangat timpang dari segala segi.mulai dari kehidupannya di dalam keluarga maupun lingkungan sosial yang mengakibatkan mereka mendapatkan tekanan akibat dari perilaku menyimpang mereka.

Tekanan itu Bisa berupa banyaknya teman-teman dia yang tiba-tiba menjauhi,mulai dikucilkan di lingkungan pergaulan sehari-hari. Ini bukan rahasia umum lagi bagaimana lingkungan sosial menghukum anak-anak remaja tersebut.Dampak dari pergaulan bebas ini mencoreng kehidupan remaja yang semestinya masih di penuhi dengan kegiatan bermain dan belajar .

Solusi Untuk Menyelesaikan Masalah Pergaulan Bebas

Selain daripada solusi dengan meningkatkan ketaqwaan kepada Tuhan YME masih banyak solusi lainnya, Solusi-solusi tersebut adalah sebagai berikut:

1. Memperbaiki Cara Pandang

Memperbaiki cara pandang dengan mencoba bersikap optimis dan hidup dalam kenyataan, maksudnya sebaiknya remaja dididik dari kecil agar tidak memiliki angan-angan yang tidak sesuai dengan kemampuannya sehingga bila ia mendapatkan kekecewaan dapat menghadapi dengan positif.

2. Menjaga Keseimbangan Pola Hidup

Yaitu perlunya remaja belajar disiplin dengan mengelola waktu, emosi, energi serta pikiran dengan baik dan bermanfaat.

3. Jujur Pada Diri Sendiri

Yaitu menyadari pada dasarnya tiap-tiap individu ingin yang terbaik untuk diri masing-masing.

4. Memperbaiki Cara Berkomunikasi

Memperbaiki cara berkomunikasi dengan orang lain sehingga terbina hubungan baik dengan masyarakat

5. Perlunya Remaja Berpikir Untuk Masa Depan

Yaitu remaja harus memiliki cita-cita ,dan dia harus memiliki keinginan yang kuat untuk mewujudkannya sehingga waktu sehari-harinya digunakan dengan bermaanfaat guna untuk mencapai cita-citanya di masa depan.

6. Menanamkan Nilai Ketimuran

Kalangan remaja kita kebanyakan sudah tak mengindahkan lagi akan pentingnya nilai-nilai ketimuran. Tentu saja nilai ketimuran ini selalu berkaitan dengan nilai Keislaman yang juga membentuk akar budaya ketimuran.

7. Mengurangi Menonton Televisi

Televisi idealnya bisa menjadi sarana mendapatkan informasi yang mendidik dan bisa meningkatkan kualitas hidup seseorang. Namun, kenyataannya, saat ini harapan itu sangat jauh. Televisi kita terutama stasiun televisi swasta, mereka lebih banyak menampilkan acara hiburan, maupun sinetron-sinetron yang menawarkan nilai-nilai gaya hidup bebas, hedonis. Begitu juga beragam tayangan infotainment yang kadang menayangkan acara perselingkuhan, sex bebas di kalangan artis.

8. Banyak Beraktivitas Secara Positif

9. Sosialisasi Bahaya Pergaulan Bebas

Dikalangan muda, pergaulan bebas sering dilakukan karena bisa jadi mereka tidak tahu akibat yang ditimbulkannya.jadi sosialisasi pergaulan bebas sangat perlu .

10. Menegakkan Aturan Hukum

Bagi yang bangga tersebut, tak ada hal lain yang bisa menghentikan selain adanya perangkat hukum dan aturan hukum yang bisa menjeratnya. Setidaknya sebagai efek jera. Yang demikian harus dirumuskan dan dilaksanakan melalui hokum yang berlaku di negara kita. Langkah ini sebagai benteng terakhir untuk menyelamatkan anak-anak muda dari amoralitas karena perilaku pergaulannbebas yang lambat laun otomatis akan merusak bangsa ini. Demikian yang bisa saya sampaikan tentang pembahasan ini dengan berbagai bantuan sumber yang saya dapat.semoga bermanfaat dan kita semua sama-sama dapat mengurangi maraknya kasus pergaulan bebas di lingkungan kita.

http://vannoorsyamsu.blogspot.com/2013/04/makalah-bahaya-pergaulan-bebas.html

Rabu, 12 November 2014

Algoritma & Pemrograman 1a

Nama: Cynthia Manurung

NPM : 52414474

Dosen: Kunto Bayu

Kelas : 1IA17

Quicksort

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

QuickSort
Quicksort
Visualisasi Algoritma Quicksort. Garis horisontal merupakan nilai sumbu.
Kelas	Algoritma Sorting
Waktu	O(n²)
Kasus rata-rata	O(n log n)
Kasus terburuk	O(n log n)

Quicksort merupakan Algoritma Sorting yang dikembangkan oleh Tony Hoare yang, secara kasus rata-rata, membuat pengurutan O(n log n) untuk mengurutkan n item. Algoritma ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting Pergantian Pembagi. Pada kasus terburuknya, algoritma ini membuat perbandingan O(n²), malaupun kejadian seperti ini sangat langka. Quicksort sering lebih cepat dalam praktiknya dari pada algoritma O(n log n) yang lainnya. Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n).
Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan algoritma sorting yang stabil.

Quicksort ialah versi optimisasi memori dari Binary Tree Sort. Alih-alih memasukkan item secara berurutan pada tree yang jelas, quicksort mengatur mereka secara bersamaan pada tree yang tersirat dengan pemanggilan rekursif. Algoritma membuat perbandingan yang persis sama, tetapi pada urutan yang berbeda. Sifat yang paling diinginkan dari Algoritma Sorting ialah kestabilannya - yang urutan elemennya pada nilai yang sama tidak berubah, memberikan urutan kontrol dari tabel multikey (contoh direktori atau listing folder) pada umumnya. Sifat ini sangat sulit untuk diatur pada quicksort (atau in-place) (yang hanya menggunakan memori tambahan tetap untuk pointer dan buffer, dan memori tambahan lognN untuk pengaturan untuk rekursif yang tampak maupun tidak. Untuk ragam Quicksort melibatkan memori lebih dikarenakan perwakilannya menggunakan pointer (contoh list atau tree) atau file (list yang sering digunakan), yang menjaga stabilitas dengan mudah. Untuk contoh yang lebih kompleks dan rumit, struktur data cenderung meningkatkan waktu yang dibutuhkan, secara umum meningkatkan memori virtual atau disk.
Pesaing quicksort langsung ialah Heapsort. Waktu kalkulasi Worst case Heasort selalu bernilai O(n log n). Tetapi average casenya heapsort diasumsikan lebih lambat dari Quicksort in-place standarnya. Masalah ini masih diperdebatkan dan masih diteliti, karena ada beberapa jurnal ilmiah yang mengatakan sebaliknya.Introsort merupakan variasi dari quicksort yang menukar heapsort ketika terdapat kasus buruk yang dideteksi untuk menghindari worst case quicksort. Lebih lanjut diketahui heapsort akan sangat dibutuhkan, menggunakan heapsort secara langsung akan lebih cepat dari pada harus menunggu introsort untuk menukarnya.
Quicksort juga bersaing dengan Mergesort, algoritma sorting rekursif yang lainnya tetapi dengan keuntungan waktu kalkulasi worst casenya O(n log n). Mergesort merupakan sorting stabil, tidak seperti quicksort in-place dan heapsort standar, dan dapat dengan mudah diadaptasikan untuk berjalan pada linked list dan list dengan penyimpanan yang sangat besar pada media dengan akses lambat seperti disk penyimpanan atau penyimpanan pada jaringan. Seperti pula mergesort, quicksort dapat diimplementasikan sebagai sorting stabil in-place,tetapi hal ini jarang digunakan. Walaupun quicksort dikatakan dapat berjalan pada linked list, tapi sering mendapatkan pivot yang buruk tanpa menggunakan akses acak. Kerugian utama dari mergesort ialah, ketika berjalan pada array, implementasi yang efisient membutuhkan ruang tambahan O(n), sedangkan variasi dari quicksort dengan patitisasi in-place dan rekursif ekor hanya menggunakan memori sebesar O(log n). (dengan catatan bahwa ketika menjalankannya pada linked list, mergesort hanya membutuhkan ruang tambahan yang konstan, namun kecil).
Bucket Sort dengan dua keranjang atau bucket hampir sama dengan quicksort; pivot pada kasus ini secara efektif mengambil nilai tengah dari range nilai, yang dimana berjalan dengan sangat baik pada average case untuk input yang terdistribusi secara umumnya.

Terdapat empat ragam quicksort yang paling terkenal:

Balanced Quicksort: memilih pivot mungkin untuk mewakili pertengah dari nilai yang akan dipilih, dan kemudian mengikuti algoritma quicksort seperti biasa.

External Quicksort: sama seperti quicksort yang biasanya kecuali pivot digantikan dengan buffer. Pertama, baca M/2 elemen pertama dan kedua menjadi buffer dan urutkan mereka. Baca elemen selanjutnya dari awal atau akhir untuk menyeimbangkan penulisan. Jika elemen selanjutnya lebih kurang dari buffer terendah, maka tulis elemen itu pada ruang yang tersedia pada awal. Jika lebih besar dari buffer tertinggi, maka tulis elemen itu pada akhir. Atau tidak tulis buffer terbesar atau terkecil, dan tempatkan elemen selanjutnya pada buffer. Tetap tulis elemen maksimum dan minimum untuk menghindari diurutkannya lagi elemen tengah yang telah terurut. Ketika selesai, tulis buffernya. Secara recursif urutkan kembali partisi yang lebih kecil, dan ulangi urutannya pada partisi yang tersisa. Cara ini merupakan tiga cara quicksort yang yang dimana buffer (partisi tengah) mewakili subarray yang telah diurut dari elemen yang kkira-kira sama dengan pivotnya.

Tiga cara Quicksort radiks (ditemukan oleh Sedgewick dan juga dikenal sebagai Multikey Quicksort): ialah kombinasi dari Radix sort dan Quicksort. Ambil sebuah elemen dari array (pivotnya) dan tempatkan karakter pertama pada string (multikey). Partisikan elemen sisa menjadi tiga set: karakter yang lebih kecil, sama, dan lebih besar dari karakter pivot. Urut secara rekursif partisi "kurang dari" dan "lebih dari" pada karakter yang sama. Urutkan secara rekursif partisi "sama dengan" dengan karakter selanjutnya (tanda). Pertimbangkan dengan mengurut menggunakan bytes atau words dari panjang W bit, best casenya ialah O(KN) dan worst casenya ialah O(2^KN) atau paling tidak O(N²) sebagai quicksort standar, dengan diberikan untuk tanda khusus N<2 sup="">K

, dan K adalah konstanta yang tersembunyi pada seluruh algortima sorting pembanding semuanya termasuk quicksort. Ini merupakan salah satu dari tiga cara quicksort yang partisi tengah mewakili urutan subarray elemen (mudah) yang persis sama dengan pivot.
Terdapat juga versi yang lebih rumit yang menggunakan algoritma partisi in-place dan dapat mencapai urutan lengkap menggunakan ruang O(logn) (tidak dihitung input) pada rata-rata (untuk sekali pemanggilan tumpukan). Kita mulai dengan fungsi partisi:

   // left is the index of the leftmost element of the array
   // right is the index of the rightmost element of the array (inclusive)
   //   number of elements in subarray = right-left+1
   function partition(array, 'left', 'right', 'pivotIndex')
      'pivotValue' := array['pivotIndex']
      swap array['pivotIndex'] and array['right']  // Move pivot to end
      'storeIndex' := 'left'
      for 'i' from 'left' to 'right' - 1  // left ≤ i < right
          if array['i'] < 'pivotValue'
              swap array['i'] and array['storeIndex']
              'storeIndex' := 'storeIndex' + 1
      swap array['storeIndex'] and array['right']  // Move pivot to its final place
      return 'storeIndex'

Ini merupakan Algoritma Partisi In-Place. algortima ini memisahkan bagian dari array antara index kiri dan kanan secara inklusif, dengan memindahkan seluruh elemen kurang dari array[pivotIndex] sebelum pivot, dan elemen yang sama atau lebih besar darinya. Dalam prosesnya, algoritma ini juga mencari posisi akhir untuk elemen pivot, yang kembali. algoritma ini secara sementara memindahkan elemen pivot pada akhir dari subarray, sehingga tidak mengganggu proses algoritma. Karena hanya menggunakan penukaran, list akhir memiliki elemen yang sama seperti elemen awalnya. Perlu diperhatikan bahwa elemen ditukan beberapa kali sebelum mencapai tempat akhirnya. Dan juga, jika pivot itu ganda pada inputan array, mereka dapat menyebar pada subarray kanan, pada urutan apapun. Cara ini tidak mewakili kesalahan dalam membagi, dimana pengurutan lebih lanjut akan memindahkan dan akhirnya merekatkan mereka bersama.
Setelah kita memiliki ini, menulis quicksort sendiri ialah mudah:

  function quicksort(array, 'left', 'right')
 
      // If the list has 2 or more items
      if 'left' < 'right'
 
          // See "Choice of pivot" section below for possible choices
          choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right'
 
          // Get lists of bigger and smaller items and final position of pivot
          'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex')
 
          // Recursively sort elements smaller than the pivot
          quicksort(array, 'left', 'pivotNewIndex' - 1)
 
          // Recursively sort elements at least as big as the pivot
          quicksort(array, 'pivotNewIndex' + 1, 'right')

Setiap pemanggilan rekursif pada fungsi quicksort ini mengurangi besar dari array yang akan diurutkan paling tidak satu elemen, semenjak setiap elemen pada pivotNewIndex diletakkan pada posisi akhirnya. Oleh karena itu, algoritma ini menjamin mengakhiri pemanggilan rekursif pada paling banyak n pemanggilan. Bagaimanapun, versi dari quicksort ini tidak stabil semenjak pengurutan elemen partisi hanya dilakukan pada satu partisi.

Ruang yang digunakan oleh quicksort tergantung dari versi yang digunakan.
Versi In-Place dari Quicksort menggunakan kerumitan ruang dari O(long n), bahkan pada worst case, ketika diimplementasikan menggunakan beberapa strategi berikut:

Menggunakan Partisi In-place. Partisi yang tak stabil ini memerlukan ruang O(1).
Setelah melakukan partisi, partisi yang memiliki elemen yang lebih kecil secara rekursif diurutkan terlebih dahulu, yang membutuhkan ruang paling banyak O(log n). Kemudian partisi lainnya diurutkan menggunakan rekursif ekor atau iterasi, yang tidak ditambahkan pada panggilan tumpukan. Ide ini, seperti yang telah diceritakan diatas, dijelaskan oleh Robert Sedgewick, dan menjaga kedalaman tumpukan dengan O(log n).

Quicksort dengan Sistem Partisi In-Place dan unstable menggunakan ruang tambahan konstan sebelum membuat panggilan rekursif manapun. Quicksort haru menyimpan jumlah informasi tetap untuk setiap pemanggilan rekursif bersarang. Sejak best case dapat membuat paling banyak O(long n) pemanggilan rekursif bersarang, yang menggunakan ruang O(log n). Bagaimanapun cara Sedgewick untuk membatasi pemanggilan rekursif, pada worst case quicksort dapat membuat pemanggilan bersarang O(n) dan membutuhkan ruang tambahan O(n).
Dari sudut pandang yang lumayan rumit, variabel seperti kiri dan kanan tidak menggunakan ruang konstan; tetapi menggunakan O(log n) bit pada indeks list dari n kali. Karena terdapat variabel pada setiap tumpukan frame, quicksort menggunakan cara Sedgewick yang membutuhkan

O((\log n)^2)

bit ruang. Kebutuhan ruang ini tidaklah buruk, walaupun sejak jika list yang mengandung elemen berbeda, maka akan membutuhkan paling kurang O(n log n) bits ruang.
Lainnya, kurang lebih, yang bukan algoritma In-Place, versi Quicksort yang menggunakan ruang O(n) untuk menyimpan dan dapat mengimplementasikan urutan yang stabil. Tempat penyimpanan menyediakan inputan array dengan mudah dipartisi pada cara yang stabil dan kemudian menyalinnya kembali pada inputan array untuk pemanggilan rekursif yang berurutan. Optimisasi Sedgewick masih sangat sesuai.

Rabu, 05 November 2014

Ilmu Sosial Dasar