[알고리즘] bubble_sort 버블정렬(pseudo-code, 파이썬, Java)

버블정렬

1. 매 단계마다 처음부터 마지막까지 차례대로 인접한 두 원소를 비교하여 뒤에 있는 원소가 앞의 원소보다 작은 경우 두 원소를 교환

2. 각 단계 수행 후 최대값이 마지막으로 이동하므로, 마지막 원소는 정렬대상에서 제외

Pseudo-code

Algorithm bubbleSort(a, n)
   for i = n – 1 downto 1
      for j = 0 to i-1
         if(a[j] > a[j+1])  then 
            int temp = a[index]
            a[index] = a[i]
            a[i] = temp

Python

def bubble_sort(arr):
    for i in range(len(arr)-1,0,-1):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Java

public class Bubble{
    public void sort(int[] arr){
        for(int i = arr.length -1; i > 0; i--){
            for(int j = 0; j <= i; j++){
                   if(arr[j] < arr[j+1]){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }             
            }
        }
    }
}

개선된 버블정렬

앞 뒤 자리의 비교가 일어나지 않았다면, 정렬되지 않는 값이 하나도 없었다고 간주할 수 있으므로, 정렬을 종료한다.(최적화)

Pseudo-code

Algorithm bubbleSort(a, n)
      for i = n – 1 downto 1
          sorted = true  //flag 생성
          for j = 0 to i-1
             if(a[j] > a[j+1])  then
                 temp = a[j]
                 a[j] = a[j+1]
                 a[j+1] = temp              
                 sorted = false
          if  (sorted)
             return

Python

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        sorted = True
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                sorted = False
        if sorted:
            break

Java

public class Bubble{
    public void sort(int[] arr){
        for(int i = arr.length -1; i > 0; i--){
            boolean sorted = true;
            for(int j = 0; j <= i; j++){
                   if(arr[j] < arr[j+1]){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    sorted = false;
                }             
            }
            if(sorted){
                break;
            }
        }
    }
}

수행시간분석

• 최악의 경우 (역순으로 정렬)

  • W(n) = O(n^2)

• 최선의 경우 (이미 정렬)

  • B(n) = O(n)