버블 정렬(bubble sort) 이해하기

버블 정렬(혹은 거품 정렬)이란

 

- 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬하는 방식

- 두개의 인접한 원소를 검사하여 정렬을 하는 방식으로 시간 복잡도가 O(n$^2$)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용하는 방식이다.

 

 

버블정렬 코드, Java

예제 1

class BubbleSort {
  void bubbleSort(int array[]) {
    int size = array.length;

    // Run loops two times: one for walking throught the array
    // and the other for comparison
    for (int i = 0; i < size - 1; i++) {
 
      // swapped keeps track of swapping
      boolean swapped = true;
      for (int j = 0; j < size - i - 1; j++) {

        // To sort in descending order, change > to < in this line.
        if (array[j] > array[j + 1]) {
          
          // Swap if greater is at the rear position
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
          
          swapped = false;
        }
      }
      
      // If there is not swapping in the last swap, then the array is already sorted.
      if (swapped == true)
        break;
    }
  }

  // Driver code
  public static void main(String args[]) {
    int[] data = { -2, 45, 0, 11, -9 };
    BubbleSort bs = new BubbleSort();
    bs.bubbleSort(data);
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

 

예제 2

void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length; i++) {
		for(int j= 1 ; j < arr.length-i; j++) {
			if(arr[j]<arr[j-1]) {
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}

 

버블정렬 코드, Python

예제 1

def bubbleSort(array):
    
    # run loops two times: one for walking throught the array 
    # and the other for comparison
    for i in range(len(array)):
        for j in range(0, len(array) - i - 1):

            # To sort in descending order, change > to < in this line.
            if array[j] > array[j + 1]:
                
                # swap if greater is at the rear position
                (array[j], array[j + 1]) = (array[j + 1], array[j])


data = [-2, 45, 0, 11, -9]
bubbleSort(data)
print('Sorted Array in Asc ending Order:')
print(data)

 

예제 2

def bubbleSort(x):
	length = len(x)-1
	for i in range(length):
		for j in range(length-i):
			if x[j] > x[j+1]:
				x[j], x[j+1] = x[j+1], x[j]
	return x

 

전통 춤으로 이해하는 버블 정렬

 

어느 대학교에서 전통 춤으로 정렬을 설명하는 퍼포먼스를 하였는데 버블 정렬이 어떤지 이해가 안되는 분은 이 영상을 보면 100% 이해가 가능할 거라 생각한다. 

 

 

 

참고자료

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC
https://www.programiz.com/dsa/bubble-sort