Jurnal Issn Nadia.docx

International Journal of Computer Sciences and Engineering Open Access Review Paper

Volume-5, Issue-6

E-ISSN: 2347-2693

An Enhancement of Bubble Sorting Algorithm Harsh N. Nankani1*, Mukesh Bhandari2 1*

2

IT department, Vadodara Institute of Engineering, Gujarat Technological University, Vadodara, India CE/IT department, Vadodara Institute of Engineering, Gujarat Technological University, Vadodara, Gujarat, India *Corresponding Author: [email protected], Mobile no.: +919033622478 Available online at: www.ijcseonline.org Received: 20/May/2017, Revised: 03/Jun/2017, Accepted: 20/Jun/2017, Published: 30/Jun/2017

Abstrak: Sorting adalah teknik penting struktur data yang menemukan tempatnya dalam banyak aplikasi kehidupan nyata. Ada berbagai algoritma pengurutan yang ada sampai tanggal. Dalam karya ini, kami telah mencoba untuk meningkatkan waktu eksekusi gelembung mengurutkan algoritma berdasarkan dengan menerapkan algoritma menggunakan peningkatan it analisis yang luas telah dilakukan oleh kami pada algoritma baru dan algoritma ini telah dibandingkan dengan metode tradisional gelembung semacam itu. Pengamatan telah diperoleh pada membandingkan pendekatan baru ini dengan pendekatan yang ada gelembung semacam itu. Pendekatan yang diusulkan baru telah diuji untuk rata-rata analisis kasus, kasus terbaik analisis dan analisis kasus terburuk. Ini telah menganalisis bahwa pendekatan baru telah memberikan hasil yang sangat baik kasus rata-rata dan analisis kasus terburuk. Pendekatan baru diuji pada data acak dari berbagai rentang dari kecil hingga besar. Itu telah diamati bahwa pendekatan baru telah memberikan hasil yang efisien dalam hal waktu eksekusi. Oleh karena itu, kita memilikiMencapai ke kesimpulan melalui pengamatan eksperimental bahwa algoritma baru diberikan dalam makalah ini adalah lebih baik daripada Bubble sort tradisional. Keywords— Sorting, Bubble sort I. INTRODUCTION Sebuah algoritma adalah set instruksi terbatas mendefinisikan Solusi masalah tertentu. Sebuah algoritma yang dapat diungkapkan dalam bahasa yang sederhana apa yang kita sebut kode pseudo, dalam bahasa pemrograman, atau dalam bentuk Flowchart.

Algoritma pengurutan sederhana melibatkan dua langkah yang membandingkan dua item dan swap dua item atau menyalin satu item. Itu terus mengeksekusi berulang-ulang sampai data diurutkan. Classification of sorting algorithm: Kompleksitas sistem komputasi.

Setiap algoritma harus memenuhi kriteria berikut: A. Input-nol atau lebih nilai, eksternal disediakan. B. Output-setidaknya satu nilai harus diproduksi. C. Definitas-itu harus jelas dan jelas. Pertumbuhan informasi pesat di dunia ini dan untuk mencari info ini, harus memerintahkan dalam cara yang bermakna. Sebelumnya, diperkirakan bahwa lebih dari separuh waktu pada banyak mesin komersial dihabiskan untuk menyortir. Untungnya ini tidak lagi benar, karena metode canggih yang telah dirancang untuk mengatur data, metode yang tidak mengharuskan data disimpan dalam setiap pesanan khusus [1]. Dalam ilmu komputer, sebuah algoritma sorting adalah algoritma yang efisien yang melakukan tugas penting yang Menempatkan elemen-elemen dari daftar dalam urutan tertentu atau mengatur koleksi item ke dalam urutan tertentu. Menyortir data telah dikembangkan untuk mengatur nilainilai array dalam berbagai cara untuk database. Misalnya, © 2017, IJCSE All Rights Reserved

Kompleksitas komputasi dalam hal jumlah Swap. Penggunaan memori juga merupakan faktor dalam mengklasifikasikan pengurutan pengurutan akan memesan sebuah array nomor terendah untuk tertinggi atau dari tertinggi ke terendah, atau mengatur sebuah array string ke dalam urutan abjad. Biasanya, itu mengurutkan sebuah array ke dalam meningkatkan atau mengurangi pesanan. Paling Berbagai kasus yang populer di sorting Algoritma adalah:  (n) adalah adil, grafik meningkat di jalan halus.  (n log n): Ini dianggap sebagai efisien, karena menunjukkan peningkatan kecepatan lebih lambat grafik seperti yang kita Meningkatkan ukuran array atau data.  (n persegi): Ini tidak efisien karena jika kita memasukkan data yang lebih besar grafik menunjukkan signifikan meningkatkan 314

International Journal of Computer Sciences and Engineering Dalam matematika, komputasi, linguistik, dan disiplin ilmu terkait, sebuah algoritma adalah daftar terbatas baikDidefinisikan petunjuk untuk menyelesaikan beberapa tugas yang, mengingat sebuah keadaan awal, akan melanjutkan melalui serangkaian didefinisikan dengan baik berturut-turut, mungkin akhirnya mengakhiri di akhir-negara negara. Tidak ada umumnya diterima definisi formal "algoritma" Ada belum. Kita bisa, bagaimanapun, memperoleh petunjuk untuk isu-isu Terlibat dan makna informal dari kata dari kutipan berikut diberikan oleh boolos dan Jeffrey (1974, 1999) [2]: "tidak manusia dapat menulis cukup cepat, atau cukup lama, atau cukup kecil untuk daftar semua anggota yang tak terbatas innumerably yang ditetapkan oleh menuliskan nama mereka, satu demi satu, dalam beberapa notasi. Tetapi manusia dapat melakukan sesuatu Sama-sama berguna, dalam kasus innumerably tertentu tak terbatas set: Mereka dapat memberikan petunjuk eksplisit untuk menentukan anggota nth ditetapkan, untuk sewenangwenang terbatas seperti instruksi yang akan diberikan cukup n. Secara eksplisit, dalam bentuk di mana mereka dapat diikuti oleh mesin komputasi, atau dengan manusia yang mampu melaksanakan hanya operasi sangat dasar pada simbol ". Efisien penyortiran adalah penting untuk mengoptimalkan penggunaan algoritma lain (seperti algoritma pencarian dan menggabungkan) yang memerlukan daftar diurutkan untuk bekerja dengan benar; hal ini juga sering berguna untuk canonicalizing data dan untuk memproduksi output manusia yang dapat dibaca. Lebih formal, output harus memenuhi dua kondisi: 1. Output dalam rangka nondecreasing setiap elemen tidak lebih kecil daripada elemen sebelumnya sesuai urutan total yang diinginkan; 2. Output adalah permutasi, atau penataan kembali input. Karena porsi yang signifikan dari pengolahan data komersial melibatkan menyortir jumlah besar data, efisien algoritma pengurutan yang cukup penting ekonomi. Ada koleksi baik algoritma pada teknik sortings dikategorikan dalam perilaku eksekusi mereka yang dikenal sebagai kompleksitas. Beberapa algoritma seperti Bubble sort, seleksi macam, jenis penyisipan memiliki kompleksitas o (n ^ 2) dimana algoritma lain seperti urut cepat, tumpukan semacam memiliki complexty o (nlogn).

© 2017, IJCSE All Rights Reserved

Vol.5(6), Jun 2017, E-ISSN: 2347-2693 II.

RELATED WORK

Gelembung semacam adalah metode pengurutan tertua dan paling sederhana di gunakan. Sayangnya, itu juga paling lambat. Thebubble urut bekerja dengan membandingkan setiap item dalam daftar dengan item di sebelah itu, dan swapping mereka jika diperlukan. Algoritma mengulangi proses ini sampai itu membuat lulus semua jalan melalui daftar tanpa bertukar item apapun (dengan kata lain, semua item yang dalam urutan yang benar). Hal ini menyebabkan nilai-nilai yang lebih besar untuk "gelembung" untuk akhir daftar sementara nilai-nilai yang lebih kecil "tenggelam" menuju awal daftar. Jumlah perbandingan, adalah (n -1) + (n-2)! (2) + (1) = n (n-1)/2 atau o (N2). Semacam gelembung umumnya dianggap sebagai algoritma sorting paling efisien di penggunaan umum. Di bawah kondisikasus terbaik (daftar ini sudah diurutkan), menyortir gelembung dapat pendekatan konstan o (n) tingkat kompleksitas. Umum-kasus adalah sebuah Kepalang o (N2). Sementara penyisipan, seleksi, dan shell jenis Juga memiliki o (N2) kompleksitas, mereka secara signifikan lebih efisien daripada gelembung semacam itu. [2]. Don knuth, dalam bukunya yang terkenal seni komputer Pemrograman, menyimpulkan bahwa "gelembung semacam tampaknya telah Apa-apa untuk merekomendasikan hal ini, kecuali nama yang mudah diingat dan fakta bahwa itu mengarah ke beberapa masalah teoritis menarik ", beberapa di antaranya ia membahas di dalamnya. Bubble sort adalah setara dalam menjalankan waktu untuk menyortir penyisipan secara asimtotik dalam kasus terburuk, tetapi dua algoritma sangat berbeda dalam jumlah swap diperlukan. Kebutuhan semacam penyisipan hanya o (n) operasi jika daftar sudah diurutkan, sedangkan implementasi naif Bubble sort (seperti palsu di bawah) memerlukan o (n ^ 2) operasi. (ini dapat dikurangi untuk o (n) jika kode ditambahkan untuk menghentikan loop luar ketika loop batin tidak melakukan swap.) [3]. Owen mengatakan bahwa gelembung sort’s perdana kebajikan adalah bahwa mudah diimplementasikan, tapi apakah itu benar-benar lebih mudah untuk menerapkan daripada penyisipan atau seleksi urut adalah diperdebatkan [5]. Sebagai contoh, dalam [6] kita menemukan: ―the Bubble sort lebih buruk daripada jenis pilihan untuk campur aduk-itu akan memerlukan banyak lagi komponen pertukaran array-tapi it’s sama baiknya dengan menyortir penyisipan untuk array yang cukup teratur. LebihPenting, it’s biasanya satu yang paling mudah untuk menulis dengan benar. Penulis telah mencoba untuk membawa gelembung semacam lebih dekat dengan jenis lain dengan menggunakan variasi baru.

315

International Journal of Computer Sciences and Engineering Astrachanm pada tahun 2003 [8] telah meneliti asal Bubble sort dan popularitas yang abadi meskipun peringatan terhadap penggunaannya oleh banyak ahli. Jehad alnihoud dan rami Mansi pada tahun 2010 [9] telah menyajikan dua algoritma pengurutan baru yaitu gelembung ditingkatkan menyortir dan ditingkatkan seleksi semacam itu. ESS memiliki o (n ^ 2) kompleksitas, tetapi lebih cepat daripada SS, terutama jika array input disimpan dalam memori sekunder, karena melakukan jumlah kurang operasi swap. EBS pasti lebih cepat daripada bs, karena bs melakukan o (n ^ 2) operasi tetapi EBS melakukan o (nlogn) operasi untuk menyortir elemen n. III.

EXISTING BUBBLE SORT ALGORITHM

Gelembung semacam adalah semacam pertukaran. Ini melibatkan perbandingan ulang dan, jika perlu, pertukaran elemen yang berdekatan. Unsur-unsur seperti gelembung dalam tangki air-setiap mencari tingkat sendiri.

Vol.5(6), Jun 2017, E-ISSN: 2347-2693 V.

CONCLUSION

Dalam karya ini, upaya dibuat untuk mengetahui beberapa kekurangan dalam pekerjaan sebelumnya berkaitan dengan gelembung algoritma pengurutan. Dengan pergi melalui semua hasil eksperimen dan analisis mereka yang dapat dengan mudah menyimpulkan bahwa algoritma yang diusulkan lebih baik untuk elemen data dihasilkan yang memerintahkan secara acak. Di algoritma yang ada, daftar lengkap pertama dimasukkan, maka daftar diproses untuk menyortir, dengan membandingkan setiap elemen dengan elemen berturut-turut tetapi dalam kasus pendekatan yang diusulkan, selain itu, daftar diurutkan dengan membandingkan setiap elemen juga dengan elemen element’s berturut-turut segera. Algoritma yang diusulkan dapat memproses tiga elemen dalam setiap iterasi. Algoritma yang diusulkan menyimpan waktu untuk melintasi dan membandingkan daftar setelah mendapatkan semua elemen.

Algorithm Bubble_Sort(A[ ] , n) Step 1: Repeat For i = 1 to n – 1 Begin Step 2: Repeat For j = 1 to n – i Begin Step 3: If (A[ j ] > A[ j + 1 ]) Swap (A[ j ] , A[ j + 1 ]) End For End For Step 4: Exit IV. PROPOSED WORK Algorithm proposed_Bubble_Sort(A[ ] , n) Step1:Set c= Step 2: Repeat For i= 0 to n – 1 Begin Step 3: Repeat For j = 0 to n – 2 Begin Step 4: If (A[ j ] > A[ j + 1]) Set c=1 If(j != n – 2 && A[ j + 1 ] > A[ j + 2 ]) Swap (A[ j ] , A[ j + 2 ]) Else if(j != n – 2 && A[ j ] > A[ j + 2 ]) Swap (A[ j ] , A[ j + 1 ], A[ j + 2]) Else Swap (A[ j ] , A[ j + 1 ]) End For If(c==0) Set i = n End For Step 7: Exit

© 2017, IJCSE All Rights Reserved

316

International Journal of Computer Sciences and Engineering VI. [1] [2]

[3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

Vol.5(6), Jun 2017, E-ISSN: 2347-2693

REFERENCES Kruse R., and Ryba A., Data Structures and Program Design in C++, Prentice Hall, 1999. Boolos, George & Jeffrey, Richard (1974, 1980, 1989, 1999), Computability and Logic (4th ed.), Cambridge University Press, London, ISBN 0-521-20402-X: cf. Chapter 3 Turing machines where they discuss "certain enumerable sets not effectively (mechanically) enumerable". Knuth, D. The Art of Computer Programming, Vol. 3: Sorting and Searching, Third edition. Addison- Wesley, 1997. ISBN 0-20189685-0. pp. 106-110 of section. Cormen T., Leiserson C., Rivest R., and Stein C., Introduction to Algorithms, McGraw Hill,2001 Owen Astrachan Bubble Sort: An Archaeological Algorithmic Analysis, SIGCSE ’03, February 19-23, Reno, Nevada, USA. Copyright 2003 ACM 1-58113-648-X/03/0002. Cooper, D. Oh My! Modula-2! W.W. Norton, 1990. Aho A., Hopcroft J., and Ullman J., The Design and Analysis of Computer Algorithms, Addison Wesley, 1974. Astrachanm O., Bubble Sort: An Archaeological Algorithmic Analysis, Duk University, 2003. Jehad Alnihoud and Rami Mansi, “An Enhancement of Major Sorting Algorithms,” The International Arab Journal of Information Technology, Vol.7, No. 1, January 2010. Knuth, D. The Art of Computer Programming: Sorting and Searching, 2 ed., vol. 3. Addison-Wesley, 1998. Iverson, K. A Programming Language. John Wiley,1962. http://linux.wku.edu/~lamonml/algor/sort/bubble.html

Authors Profile Mr. Harsh N Nankani Mengejar diploma dalam teknologi informasi dari Politeknik maharaja sayajirao University of Baroda, India pada tahun 2015. Saat ini ia sedang mengejar Bachelor of teknologi informasi dari Vadodara Institute of Teknik Universitas Teknologi Gujarat, India sejak tahun 2015. Dia adalah anggota masyarakat India pendidikan teknis (iste) sejak 2015. Riset utamanya berfokus pada menyortir dan mencari algoritma. Mr Mukesh Bhandari mengejar Bachelor of teknologi dalam teknologi informasi dari era grafis University of dehradun, India pada tahun 2008 dan master of Technology di teknik komputer dari teknik pemerintah College of Rajasthan Universitas teknik, India pada tahun 2011. Saat ini ia sedang bekerja sebagai asisten profesor di departemen CE dan dari Vadodara Institute of Engineering, Universitas Teknologi Gujarat, India. Dia adalah anggota anggota iste, CSI dan IEEE Computer Society. Dia telah menerbitkan lebih dari 13 makalah penelitian. Riset utamanya berfokus pada algoritma, kecerdasan buatan, dalam belajar. Dia memiliki 6 tahun pengalaman mengajar, 2 tahun pengalaman penelitian dan 1,5 tahun pengalaman industri.

© 2017, IJCSE All Rights Reserved

317