Cum să implementați algoritmul de sortare cu bule în Java - Exemplu de ordine ascendentă și descendentă

Publicat: 2019-01-19
Cum se implementează algoritmul de sortare cu bule în Java - Exemplu de ordine ascendentă și descendentă

Sortare cu Bubble sort , denumit uneori incorect sinking sort , este un algoritm de sortare simplu care funcționează prin parcurgerea în mod repetat a listei de sortat, comparând fiecare pereche de articole adiacente și schimbându-le dacă sunt în ordinea greșită.

Trecerea prin listă se repetă până când nu este nevoie de schimburi, ceea ce indică faptul că lista este sortată. Algoritmul își ia numele de la felul în care elementele mai mici se bubble în partea de sus a listei.

Deoarece folosește doar comparații pentru a opera pe elemente, este un sort de comparație. Deși algoritmul este simplu, majoritatea celorlalți algoritmi de sortare sunt mai eficienți pentru liste mari.

Logica este simplă:

În sortarea cu bule, practic parcurgem lista de matrice de la prima poziție la (dimensiune – 1) și comparăm elementul cu următorul. Schimbați elementul cu următorul element numai dacă următorul element este mai mare.

Iată un cod Java:

  • Creați fișierul 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 ) ;
 
     }
}
 

Rezultat consola Eclipse:

Doar rulați deasupra programului java Bubble Sort în consola Eclipse sau IntelliJ IDE și ar trebui să vedeți rezultatul ca mai jos.

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
 

Ce este o complexitate temporală a algoritmului de sortare cu bule?

  • Dacă luați în considerare Best case scenariu, atunci ar fi O(n)
  • Dacă luați în considerare Worst case scenariu, atunci ar fi O(n 2 )

Anunțați-mă dacă aveți vreo problemă sau excepție la rularea programului de mai sus.