[Algorithm] 정렬 - 버블정렬

✅ 버블정렬

---

블 정렬은 인접한 데이터를 교환해서 정렬하는 알고리즘을 의미합니다.

알고리즘의 정렬되는 모습이 마치 거품처럼 보인다고 해서 붙여진 이름입니다.

아래의 동작 과정을 보면 버블이라는 이름이 붙은 이유를 이해할 수 있을 것입니다.

동작 과정은 다음과 같습니다

1. index의 0과 1의 값을 비교하여 큰 값을 1 위치로 옮깁니다.
2. index의 1과 2의 값을 비교하여 큰 값을 2 위치로 옮깁니다.
3. index의 2와 3의 값을 비교하여 큰 값을 3 위치로 옮깁니다.
   ...
   ...
   n-1 index의 n과 n-1의 값을 비교하여 큰 값을 마지막 위치로 옮깁니다.

어떤가요 그림이 그려지시나요?

하지만 버블정렬은 O(n^2)의 시간 복잡도를 지니고 있습니다.

이중 반복문이 불가피하게 사용되기 때문인데요.

그렇기 때문에 구현하기 단순한 정렬 방법 중 하나이지만,
처리 속도가 다른 정렬 방법보다 느리기 때문에 잘 사용하지 않는 방법이라고 합니다.

✅ 문제

---

nums라는 배열을 주면, 버블정렬 알고리즘으로 배열을 정렬하는 프로그램을 작성해주세요.

📌 풀이

---

index가 0인 수부터 n-1 (총 길이에서 1을 뺀 index)까지 반복문을 순회하면서 인접한 수와 비교를 해야합니다.

만약 반복문을 한번만 사용했을 경우 다음과 같은 문제가 발생할 수 있습니다.

예시:

input = [2, 1, 4, 6, 8, 3]
output = [1, 2, 4, 6, 3, 8]

반복문을 한번만 순회하면서 마지막에 있는 3을 앞의 값과 한번밖에 비교가 되지 않기 때문에 정렬이 되지 않게 됩니다.

이중 for문을 이용하여 버블 정렬을 구현하는 프로그램은 다음과 같습니다.

#1 비교해야 하는 각 원소를 선택해줍니다. (시작 위치 정하기)

#2 각 원소를 시작으로 인접한 두 원소를 선택해줍니다.

#3 인접한 두 원소의 크기 비교를 통해 조건에 부합하면 위치를 바꾸어줍니다.

def bubbleSort(arr):
	n = len(arr)
  
  	#1
	for i in range(0, n-1):
    
    	#2
  		for j in range(0, n-1):
      
      		#3
    		if arr[j] > arr[j+1] :
        		arr[j], arr[j+1] = arr[j+1], arr[j]
      
	return arr