Bubble Sort

Dalam tutorial ini, Anda akan belajar tentang algoritma bubble sort dan implementasinya dalam Python, Java, C, dan C ++.

Semacam gelembung adalah algoritme pengurutan yang membandingkan dua elemen yang berdekatan dan menukarnya jika tidak sesuai dengan urutan yang diinginkan.

Bekerja dari Bubble Sort

Misalkan kita mencoba mengurutkan elemen dalam urutan menaik.

1. Iterasi Pertama (Bandingkan dan Tukar)

Mulai dari indeks pertama, bandingkan elemen pertama dan kedua.
Jika elemen pertama lebih besar dari elemen kedua, mereka ditukar.
Sekarang, bandingkan elemen kedua dan ketiga. Tukar mereka jika tidak berurutan.
Proses di atas berlangsung hingga elemen terakhir.

Bandingkan Elemen yang Berdekatan

2. Sisa Iterasi

Proses yang sama berlangsung untuk iterasi yang tersisa.

Setelah setiap iterasi, elemen terbesar di antara elemen yang tidak disortir ditempatkan di akhir.

Lanjutkan penukaran dan letakkan elemen terbesar di antara daftar yang tidak disortir di bagian akhir — Letakkan elemen terbesar di akhir

Dalam setiap iterasi, perbandingan berlangsung hingga elemen tak disortir terakhir.

Swapping hanya terjadi jika elemen pertama lebih besar dari elemen berikutnya — Bandingkan elemen yang berdekatan

Larik diurutkan ketika semua elemen yang tidak diurutkan ditempatkan pada posisi yang benar.

Array diurutkan jika semua elemen disimpan dalam urutan yang benar. — Array diurutkan jika semua elemen disimpan dalam urutan yang benar

Algoritme Sortir Gelembung

bubbleSort(array)
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
end bubbleSort

Bubble Sort Code dengan Python, Java dan C / C ++

Python

Jawa

C ++

# Bubble sort in Python

def bubbleSort(array):
    
  # loop to access each array element
  for i in range(len(array)):

    # loop to compare array elements
    for j in range(0, len(array) - i - 1):

      # compare two adjacent elements
      # change > to < to sort in descending order
      if array[j] > array[j + 1]:

        # swapping elements if elements
        # are not in the intended order
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp


data = [-2, 45, 0, 11, -9]

bubbleSort(data)

print('Sorted Array in Ascending Order:')
print(data)

// Bubble sort in Java

import java.util.Arrays;

class Main {

  // perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;
    
    // loop to access each array element
    for (int i = 0; i < size - 1; i++)
    
      // loop to compare array elements
      for (int j = 0; j < size - i - 1; j++)

        // compare two adjacent elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {

          // swapping occurs if elements
          // are not in the intended order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }

  public static void main(String args[]) {
      
    int[] data = { -2, 45, 0, 11, -9 };
    
    // call method using class name
    Main.bubbleSort(data);
    
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

// Bubble sort in C

#include <stdio.h>

// perform the bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < size - 1; ++step) {
      
    // loop to compare array elements
    for (int i = 0; i < size - step - 1; ++i) {
      
      // compare two adjacent elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {
        
        // swapping occurs if elements
        // are not in the intended order
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// print array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("n");
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the array's length
  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);
  
  printf("Sorted Array in Ascending Order:n");
  printArray(data, size);
}

// Bubble sort in C++

#include <iostream>
using namespace std;

// perform bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < (size-1); ++step) {
      
    // loop to compare array elements
    for (int i = 0; i < size - (step-1); ++i) {

      // compare two adjacent elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {

        // swapping elements if elements
        // are not in the intended order
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// print array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << array[i];
  }
  cout << "n";
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find array's length
  int size = sizeof(data) / sizeof(data[0]);
  
  bubbleSort(data, size);
  
  cout << "Sorted Array in Ascending Order:n";  
  printArray(data, size);
}

Algoritma Bubble Sort yang Dioptimalkan

Dalam algoritme di atas, semua perbandingan dibuat meskipun array sudah diurutkan.

Ini meningkatkan waktu eksekusi.

Untuk mengatasi ini, kita dapat memperkenalkan variabel tambahan bertukar. Nilai dari bertukar disetel benar jika terjadi pertukaran elemen. Jika tidak, itu sudah diatur Salah.

Setelah iterasi, jika tidak ada pertukaran, nilai bertukar akan Salah. Ini berarti elemen sudah diurutkan dan tidak perlu melakukan iterasi lebih lanjut.

Ini akan mengurangi waktu eksekusi dan membantu mengoptimalkan jenis gelembung.

Algoritma untuk pengurutan gelembung yang dioptimalkan adalah

bubbleSort(array)
  swapped <- false
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
      swapped <- true
end bubbleSort

Bubble Sort yang Dioptimalkan di Python, Java, dan C / C ++

Python

Jawa

C ++

# Optimized Bubble sort in Python

def bubbleSort(array):
    
  # loop through each element of array
  for i in range(len(array)):
        
    # keep track of swapping
    swapped = False
    
    # loop to compare array elements
    for j in range(0, len(array) - i - 1):

      # compare two adjacent elements
      # change > to < to sort in descending order
      if array[j] > array[j + 1]:

        # swapping occurs if elements
        # are not in the intended order
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp

        swapped = True
          
    # no swapping means the array is already sorted
    # so no need for further comparison
    if not swapped:
      break

data = [-2, 45, 0, 11, -9]

bubbleSort(data)

print('Sorted Array in Ascending Order:')
print(data)

// Optimized Bubble sort in Java

import java.util.Arrays;

class Main {

  // perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;
    
    // loop to access each array element
    for (int i = 0; i < (size-1); i++) {
    
      // check if swapping occurs
      boolean swapped = false;
      
      // loop to compare adjacent elements
      for (int j = 0; j < (size-i-1); j++) {

        // compare two array elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {

          // swapping occurs if elements
          // are not in the intended order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
          
          swapped = true;
        }
      }
      // no swapping means the array is already sorted
      // so no need for further comparison
      if (!swapped)
        break;

    }
  }

  public static void main(String args[]) {
      
    int[] data = { -2, 45, 0, 11, -9 };
    
    // call method using the class name
    Main.bubbleSort(data);
    
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

// Optimized Bubble sort in C

#include 

// perform the bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < size - 1; ++step) {
    
    // check if swapping occurs  
    int swapped = 0;
    
    // loop to compare array elements
    for (int i = 0; i < size - step - 1; ++i) {
      
      // compare two array elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {
        
        // swapping occurs if elements
        // are not in the intended order
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        
        swapped = 1;
      }
    }
    
    // no swapping means the array is already sorted
    // so no need for further comparison
    if (swapped == 0) {
      break;
    }
    
  }
}

// print array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("n");
}

// main method
int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the array's length
  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);
  
  printf("Sorted Array in Ascending Order:n");
  printArray(data, size);
}

// Optimized bubble sort in C++

#include 
using namespace std;

// perform bubble sort
void bubbleSort(int array[], int size) {
    
  // loop to access each array element
  for (int step = 0; step < (size-1); ++step) {
      
    // check if swapping occurs
    int swapped = 0;
    
    // loop to compare two elements
    for (int i = 0; i < (size-step-1); ++i) {
        
      // compare two array elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {

        // swapping occurs if elements
        // are not in intended order 
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        
        swapped = 1;
      }
    }

    // no swapping means the array is already sorted
    // so no need of further comparison
    if (swapped == 0)
      break;
  }
}

// print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << array[i];
  }
  cout << "n";
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the array's length
  int size = sizeof(data) / sizeof(data[0]);
  
  bubbleSort(data, size);
  
  cout << "Sorted Array in Ascending Order:n";
  printArray(data, size);
}

Kompleksitas Sortir Gelembung

Kompleksitas Waktu
Terbaik	Di)
Terburuk	Di²)
Rata-rata	Di²)
Kompleksitas Ruang	O (1)
Stabilitas	Iya

Kompleksitas dalam Detail

Bubble Sort membandingkan elemen yang berdekatan.

Siklus	Jumlah Perbandingan
1st	(n-1)
2nd	(n-2)
3	(n-3)
…….	……
terakhir	1

Karenanya, jumlah perbandingannya adalah

(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2

hampir sama dengan n²

Karenanya, Kompleksitas: Di²)

Juga, jika kita mengamati kodenya, bubble sort membutuhkan dua loop. Oleh karena itu, kompleksitasnya n*n = n²

1. Kompleksitas Waktu

Kompleksitas Kasus Terburuk: O(n²)

Jika kita ingin mengurutkan dalam urutan menaik dan array dalam urutan menurun maka kasus terburuk terjadi.
Kompleksitas Kasus Terbaik: O(n)

Jika larik sudah diurutkan, maka tidak perlu penyortiran.
Kompleksitas Kasus Rata-rata: O(n²)

Ini terjadi ketika elemen array berada dalam urutan campur aduk (baik naik maupun turun).

2. Kompleksitas Ruang

Kompleksitas ruang adalah O(1) karena variabel ekstra digunakan untuk bertukar.
Dalam algoritma pengurutan gelembung yang dioptimalkan, dua variabel tambahan digunakan. Oleh karena itu, kompleksitas ruang akan menjadi O(2).

Aplikasi Bubble Sort

Jenis gelembung digunakan jika

kompleksitas tidak masalah
kode pendek dan sederhana lebih disukai

Algoritma Pengurutan Serupa

Quicksort
Sortir Penyisipan
Gabungkan Sortir
Sortir Pilihan