버블 정렬(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

    댓글

    Designed by JB FACTORY