[자료구조] 버블 정렬(Bubble Sort)

목차

정렬 종류
비교 기반 정렬(Comparison Based Sorts) 
- Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort
비비교 기반 정렬(Non-comparison Based Sorts)
- Counting Sort, Radix Sort, Bucket Sort

버블 정렬(Bubble Sort)

개념

• 버블 정렬은 두 개의 인접한 요소를 비교하여 작은 값을 앞으로 보내주는 과정을 기반으로 정렬하게 됩니다. 이러한 과정을 앞에서부터 뒤에까지 쭈욱 진행하면, 작은 값들이 한 칸씩 앞으로 이동하게 될 것입니다. 
  • 이러한 과정은 swap 과정이 발생하지 않을때까지 진행되게 됩니다.
• 만약 제일 작은 값이 제일 뒤에 있다고 한다면 제일 앞으로 오기 위해서는 총 N-1번 진행해야지 제일 앞까지 이동할 수 있습니다.
• 따라서 시간복잡도는 O(n^2)으로 비효율적인 정렬 알고리즘입니다.
• 공간복잡도는 해당 배열에 그대로 swap을 하면서 진행되기 때문에 O(1)입니다.
• 

코드

• Bubble Sort

  • def bubble_sort(arr):
        swap_flag = True
        while swap_flag:
            swap_flag = False
            for i in range(len(arr) - 1):
                if arr[i] > arr[i + 1]:
                    arr[i], arr[i + 1] = arr[i + 1], arr[i]
                    swap_flag = True
    
    
    arr = [7, 3, 2, 5, 6, 10, 9, 8, 1]
    bubble_sort(arr)
    print(arr)
    
    -->
    [1, 2, 3, 5, 6, 7, 8, 9, 10]

출처

• https://leetcode.com/explore/learn/card/sorting/694/comparison-based-sorts/4434/