버블 정렬 bubblesort with swift

버블 정렬은 옆에 있는 값과 비교해서 정렬하는 알고리즘입니다. 

 

버블 정렬은 계속해서 옆 원소랑 비교하며 정렬합니다.

또한 한 번의 external for loop가 끝났을 때 가장 큰 값이 맨뒤로 갑니다.

 

코드를 살펴봅시다.

 

arr는 우리가 정렬해야 할 배열이며, 1부터 7까지 정렬되지 않은 상태로 존재합니다.

arr의 크기는 7이고 인덱스는 0부터 6까지 입니다.

external for loop는 6부터 시작해서 아래로 내려오며,

internal for loop는 0부터 external의 i까지 올라가며 비교하며 정렬하기 위함입니다.

 

차근차근 살펴봅시다.

 

external for loop의 i값은 6이며

internal for loop의 j값은 0부터 5까지 실행됩니다.

 

j가 0인 경우를 살펴봅시다.

arr[0]과 arr[1] 4와 1이니 인덱스 0이 더 크므로,

internal for loop 내부에 if문의 arr[j] > arr[j+1]조건이 성립합니다.

그렇게 arr의 0과 1인덱스를 swap 해줍니다.

 

j가 1인 경우는 arr[1]과 arr[2] 4와 5이므로 조건이 성립하지 않습니다.

 

j가 2인 경우는 arr[2]과 arr[3] 5와 3이니 인덱스 2가 더 크므로 조건이 성립합니다.

그렇게 arr의 2와 3 인덱스를 swap 해줍니다.

 

j가 3인 경우는 arr[3]과 arr[4] 5와 6이므로 조건이 성립하지 않습니다.

 

j가 4인 경우는 arr[4]과 arr[5] 6과 2이니 인덱스 4가 더 크므로 조건이 성립합니다.

그렇게 arr의 4와 5 인덱스를 swap 해줍니다.

 

j가 5인 경우는 arr[5]과 arr[6] 6와 7이므로 조건이 성립하지 않습니다.

두 번째 external for loop의 값은 5이며 

internal for loop의 j값은 0부터 4까지 실행됩니다.

 

j가 0인 경우를 살펴봅시다.

arr[0]과 arr[1] 1와 4이므로 조건이 성립하지 않습니다.

 

j가 1인 경우는 arr[1]과 arr[2] 4와 3이니 인덱스 1이 더 크므로 조건이 성립합니다.

그렇게 arr의 1과 2 인덱스를 swap 해줍니다.

 

j가 2인 경우는 arr[2]과 arr[3] 4와 5이므로 조건이 성립하지 않습니다.

 

j가 3인 경우는 arr[3]과 arr[4] 5와 2이니 인덱스 3이 더 크므로 조건이 성립합니다.

그렇게 arr의 3와 4 인덱스를 swap 해줍니다.

 

j가 4인 경우는 arr[4]과 arr[5] 5와 6이므로 조건이 성립하지 않습니다.

세 번째 external for loop의 값은 4이며 

internal for loop의 j값은 0부터 3까지 실행됩니다.

 

네 번째 external for loop의 값은 3이며 

internal for loop의 j값은 0부터 2까지 실행됩니다.

다섯 번째 external for loop의 값은 2이며 

internal for loop의 j값은 0부터 1까지 실행됩니다.

여섯 번째 external for loop의 값은 1이며 

internal for loop의 j값은 0만 실행됩니다.

위 이미지는 각 external for loop를 돌 때 array의 변화를 나타낸 것입니다.

옆에 있는 값과 비교해서 정렬하며 한 번의 반복이 끝났을 때 가장 큰 값이 맨뒤에 위치하는 게 보이시나요.

이것이 bubblesort의 핵심입니다.

 

간단한 정렬 알고리즘이지만, 시간 복잡도는 O(n^2)입니다.

계속해서 swap 하는 작업이 있기 때문에 다른 정렬들 중에서 가장 효율성이 떨어지는 알고리즘이라고 할 수 있습니다.

---

버블 정렬에 check 변수를 두어 swap이 일어나지 않으면 뒤에는 정렬되었다는 의미이므로,

불필요한 for loop를 또 돌릴 필요 없이 중간에 브레이크를 두어 탈출할 수 있습니다.