วิธีการใช้ Bubble Sort Algorithm ใน Java – Ascending และ Descending Order Example

เผยแพร่แล้ว: 2019-01-19
วิธีการใช้ Bubble Sort Algorithm ใน Java - Ascending และ Descending Order Example

Bubble sort บางครั้งเรียกว่า sinking sort อย่างไม่ถูกต้อง เป็นอัลกอริธึมการเรียงลำดับอย่างง่ายที่ทำงานโดยการก้าวผ่านรายการเพื่อจัดเรียงซ้ำๆ เปรียบเทียบแต่ละรายการที่อยู่ติดกันและสลับกันหากรายการเหล่านั้นอยู่ในลำดับที่ไม่ถูกต้อง

การส่งผ่านรายการจะถูกทำซ้ำจนกว่าจะไม่มีการสลับ ซึ่งบ่งชี้ว่ารายการถูกจัดเรียง อัลกอริทึมได้ชื่อมาจากองค์ประกอบที่มีขนาด bubble ลงไปจนถึงด้านบนของรายการ

เนื่องจากใช้การเปรียบเทียบเพื่อดำเนินการกับองค์ประกอบเท่านั้น จึงเป็นการจัดเรียงแบบเปรียบเทียบ แม้ว่าอัลกอริธึมจะเรียบง่าย แต่อัลกอริธึมการจัดเรียงอื่นๆ ส่วนใหญ่มีประสิทธิภาพมากกว่าสำหรับรายการขนาดใหญ่

ตรรกะเป็นเรื่องง่าย:

ในการจัดเรียงแบบฟอง โดยทั่วไปเราจะสำรวจรายการอาร์เรย์จากตำแหน่งแรกถึงตำแหน่ง (ขนาด – 1) และเปรียบเทียบองค์ประกอบกับตำแหน่งถัดไป สลับองค์ประกอบกับองค์ประกอบถัดไปก็ต่อเมื่อองค์ประกอบถัดไปมีค่ามากกว่า

นี่คือรหัส Java:

  • สร้างไฟล์ CrunchifyBubbleSort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package crunchify . com . tutorials ;
 
import java . util . Arrays ;
 
/**
* @author Crunchify.com
* How to Implement Bubble sort algorithm in Java? Ascending and Descending Order Tutorial
*/
 
public class CrunchifyBubbleSort {
 
     public static void main ( String [ ] args ) {
         int [ ] crunchifyArray = { 15 , 3 , 9 , 7 , 19 , 8 , 1 , 5 } ;
         int [ ] crunchifyArrayDesc = { 20 , 13 , 19 , 37 , 69 , 18 , 21 , 5 , 99 } ;
         crunchifyPrint ( "Let's get started on Bubble Sort implementation in Java - by Crunchify \n" ) ;
         crunchifyPrint ( "============ Ascending Order result: " + Arrays . toString ( CrunchifyBubbleSortAscMethod ( crunchifyArray ) ) + "\n" ) ;
         crunchifyPrint ( "============ Descending Order result: " + Arrays . toString ( CrunchifyBubbleSortDescMethod ( crunchifyArrayDesc ) ) + "\n" ) ;
     }
 
     // Bubble Sort Algorithm in Ascending Order
     public static int [ ] CrunchifyBubbleSortAscMethod ( int [ ] crunchifyArr ) {
         for ( int i = 0 ; i < crunchifyArr . length - 1 ; i ++ ) {
 
             for ( int j = 1 ; j < crunchifyArr . length - i ; j ++ ) {
                 if ( crunchifyArr [ j - 1 ] > crunchifyArr [ j ] ) {
                     int temp = crunchifyArr [ j - 1 ] ;
                     crunchifyArr [ j - 1 ] = crunchifyArr [ j ] ;
                     crunchifyArr [ j ] = temp ;
                 }
             }
             crunchifyPrint ( "Iteration " + ( i + 1 ) + ": " + Arrays . toString ( crunchifyArr ) ) ;
         }
         return crunchifyArr ;
     }
 
     // Bubble Sort Algorithm in Descending Order
     public static int [ ] CrunchifyBubbleSortDescMethod ( int [ ] crunchifyArr ) {
         for ( int i = 0 ; i < crunchifyArr . length - 1 ; i ++ ) {
             for ( int j = 1 ; j < crunchifyArr . length - i ; j ++ ) {
                 if ( crunchifyArr [ j - 1 ] < crunchifyArr [ j ] ) {
                     int temp = crunchifyArr [ j - 1 ] ;
                     crunchifyArr [ j - 1 ] = crunchifyArr [ j ] ;
                     crunchifyArr [ j ] = temp ;
                 }
             }
             crunchifyPrint ( "Iteration " + ( i + 1 ) + ": " + Arrays . toString ( crunchifyArr ) ) ;
         }
         return crunchifyArr ;
     }
 
     // Simple log util
     private static void crunchifyPrint ( String result ) {
         System . out . println ( result ) ;
 
     }
}
 

ผลลัพธ์ของคอนโซล Eclipse:

เพียงเรียกใช้โปรแกรม Java Bubble Sort ในคอนโซล Eclipse หรือ IntelliJ IDE แล้วคุณจะเห็นผลลัพธ์ดังนี้

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Let ' s get started on Bubble Sort implementation in Java - by Crunchify
 
Iteration 1 : [ 3 , 9 , 7 , 15 , 8 , 1 , 5 , 19 ]
Iteration 2 : [ 3 , 7 , 9 , 8 , 1 , 5 , 15 , 19 ]
Iteration 3 : [ 3 , 7 , 8 , 1 , 5 , 9 , 15 , 19 ]
Iteration 4 : [ 3 , 7 , 1 , 5 , 8 , 9 , 15 , 19 ]
Iteration 5 : [ 3 , 1 , 5 , 7 , 8 , 9 , 15 , 19 ]
Iteration 6 : [ 1 , 3 , 5 , 7 , 8 , 9 , 15 , 19 ]
Iteration 7 : [ 1 , 3 , 5 , 7 , 8 , 9 , 15 , 19 ]
============ Ascending Order result : [ 1 , 3 , 5 , 7 , 8 , 9 , 15 , 19 ]
 
Iteration 1 : [ 20 , 19 , 37 , 69 , 18 , 21 , 13 , 99 , 5 ]
Iteration 2 : [ 20 , 37 , 69 , 19 , 21 , 18 , 99 , 13 , 5 ]
Iteration 3 : [ 37 , 69 , 20 , 21 , 19 , 99 , 18 , 13 , 5 ]
Iteration 4 : [ 69 , 37 , 21 , 20 , 99 , 19 , 18 , 13 , 5 ]
Iteration 5 : [ 69 , 37 , 21 , 99 , 20 , 19 , 18 , 13 , 5 ]
Iteration 6 : [ 69 , 37 , 99 , 21 , 20 , 19 , 18 , 13 , 5 ]
Iteration 7 : [ 69 , 99 , 37 , 21 , 20 , 19 , 18 , 13 , 5 ]
Iteration 8 : [ 99 , 69 , 37 , 21 , 20 , 19 , 18 , 13 , 5 ]
============ Descending Order result : [ 99 , 69 , 37 , 21 , 20 , 19 , 18 , 13 , 5 ]
 
 
Process finished with exit code 0
 

ความซับซ้อนของเวลาของอัลกอริธึม Bubble Sort คืออะไร?

  • หากคุณพิจารณาสถานการณ์ Best case มันจะเป็น O(n)
  • หากคุณพิจารณาสถานการณ์ Worst case มันจะเป็น O(n 2 )

แจ้งให้เราทราบหากคุณมีปัญหาหรือข้อยกเว้นในการใช้งานโปรแกรมข้างต้น