버블 정렬

https://unsplash.com/photos/ZDUXvlyU_iI

버블 정렬에 대해 알아보자.

 

 

 

 

 

---

얻어갈 지식

• 버블 정렬

 

 

 

 

버블 정렬

 

가장 간단한 정렬 알고리즘이다.

평균적으로 그리고 최악의 경우 시간 복잡성이 매우 높기 때문에 대규모 데이터 셋에는 적합하지 않다.

버블 정렬 예시

• [ 5, 1, 4, 2, 8 ]로 되어있는 어레이가 있을 때 오름차순으로 정렬하면 아래와 같다.
  
  
• 첫 번째 패스 ( 가장 큰 수를 제일 마지막 자리로 옮기기 )
  • 5는 1보다 크므로 서로 자리를 바꾼다. [ 1, 5, 4, 2, 8 ]
  • 5는 4보다 크므로 서로 자리를 바꾼다. [ 1, 4, 5, 2, 8 ]
  • 5는 2보다 크므로 서로 자리를 바꾼다. [ 1, 4, 2, 5, 8 ]
  • 5는 8보다 크지 않으므로 자리를 바꾸지 않는다. [ 1, 4, 2, 5, 8 ]
    
    
• 두 번째 패스 ( 두 번째로 큰 수를 뒤에서 두 번째 자리로 옮기기 )
  • 1은 4보다 크지 않으므로 자리를 바꾸지 않는다. [ 1, 4, 2, 5, 8 ]
  • 4는 2보다 크므로 자리를 바꾼다. [ 1, 2, 4, 5, 8 ]
  • 4는 5보다 크지 않으므로 자리를 바꾸지 않는다. [ 1, 2, 4, 5, 8 ]
  • 5는 8보다 크지 않으므로 자리를 바꾸지 않는다. [ 1, 2, 4, 5, 8 ]
    
    

• 세 번째 패스
  • 어레이는 이미 정렬되어 있으니 더 이상 정렬을 진행하지 않아도 된다.
  • 이를 가능케 하려면 스왑 없이 패스를 1회 통과하면 된다.
  • 이미 정렬이 다 되어있으므로 세 번째 패스에서는 스왑이 일어나지 않고
    스왑이 일어나지 않았으므로 정렬을 마친다.

 

 

코드로 작성 

def bubbleSort(arr):
	n = len(arr)

	for i in range(n):
		swapped = False
		
		for j in range(n-i-1):
			if arr[j] > arr[j+1]:
				arr[j], arr[j+1] = arr[j+1], arr[j]
				swapped = True

		if swapped == False:
			break

 

시간 복잡도와 보조 공간

• 시간 복잡도
  • 첫 번째 반복 시 비교 횟수 n - 1
  • 두 번째 반복 시 비교 횟수 n - 2
  • ......
  • n - 1 번째 반복 시 비교 횟수 1
  • 총 비교 횟수 = n(n-1)/2
  • 빅오 표기법으로 표현하면 O(N^2)이다
    
    
• 보조 공간
  • 제공받는 어레이 외에 따로 저장공간이 필요 없기 때문에 O(1)이다.

 

 

 

 

 

---

https://www.geeksforgeeks.org/bubble-sort/

Bubble Sort - GeeksforGeeks