버블정렬(Bubble Sort) 알고리즘

안녕하세요, 알고리즘 공부하는 컴공 3학년입니다..ㅎ

개강을 시작함과 동시에 이번에 알고리즘 과목을 수강하는데, 수업 전에 미리 공부한 다음 이해한 내용을 토대로 글을 작성해봅니다.

---

알고리즘을 공부하면서 수많은 정렬을 배우게 될거에요, 뭐 버블정렬, 선택정렬, 삽입정렬, 병합정렬, 퀵정렬, 힙정렬 등등(또 있나요?) 이렇게 배우게 될건데.

정렬이 뭔지 아시나요?
한국인한테 너무 쉬운걸 물어봤죠? 

정렬은 알고리즘에 맞게 설명하면, 난잡한... 정리되지 않은 데이터들을 옳바르게 정렬하는거에요. 1, 5, 2, 0, 3.. 이런거 보면 쪼금 불편하지 않나요?

우리가 나중에 데이터를 처리하려면 데이터를 가져와야겠죠.. 근데 위처럼 가져오려는 데이터가 지저분~~ 하면 쪼금 거시기 하잖아요? 그래서 정렬 하는겁니다.

---

버블정렬

버블버블 Bubble.. 물 속에 있는 기포가 표면으로 뾰롱! 하고 올라오는 것처럼, 배열의 각 요소가 각 반복에서 끝으로 이동하는 정렬을 버블정렬이라고 부릅니다.

 

버블정렬 작업

이 데이터의 정렬을, 오름차순으로 정렬해봅시다.

1. 첫 번째 인덱스의 요소와 두 번째 인덱스의 요소를 비교합니다.

2. 첫 번째 인덱스의 요소가 두 번째 인덱스의 요소보다 크다면 서로 Switch합니다.

3. 이제 두 번째 요소와 세 번째 요소를 비교 후, 순서가 맞지 않으면 Switch합니다.

4. 이 Process를 마지막 요소까지 반복합니다.

 

가장 큰 요소를 오른쪽에 놓는다.

나머지 반복에 대해서도 동일한 Process가 적용됩니다.

각 반복 후에는 정렬되지 않은 요소 중 가장 큰 요소가 끝에 배치됩니다,

 

각 process가 끝나면, 맨 앞에서부터 같은 process를 반복하며 모든 요소를 거칩니다,

---

버블 정렬 알고리즘

bubbleSort(array)
  for i <- 1 to sizeOfArray - 1
    for j <- 1 to sizeOfArray - 1 - i
      if leftElement > rightElement
        swap leftElement and rightElement
end bubbleSort

버블 정렬의 알고리즘은 반복문을 계속 돌리는겁니다.

if leftElement > rightElement
        swap leftElement and rightElement

만약에 왼쪽의 요소가 오른쪽 요소보다 크면 switch하는겁니다. 오름차순 정렬이니까요.

근데 이거를 언제까지 반복하냐?

for i <- 1 to sizeOfArray - 1
    for j <- 1 to sizeOfArray - 1 - i

i는 전체 배열의 수에서 1을 뺸 값만큼 반복한다는 의미입니다. 코드에서 인덱스의 순서는 1이 아닌 0부터 시작하므로 8의 크기를 가진 배열의 마지막 인덱스는 7이잖아요?

j는 모든 요소 중에서, 한 번 버블정렬이 발생할때마다 가장 큰 요소가 오른쪽에 배치되잖아요? 그러면 한 번은 덜 반복해도 되므로 i에서 1을 또 뺴는겁니다.

따라서 전체 배열에 버블정렬을 하는데, 한 번할때마다 가장 우측에 큰 값이 정렬되므로, 1씩 줄여가면서 해나가는 겁니다.

---

근데 이런 버블정렬은 시간이 오래걸리겠죠?

모든 요소를 일일이 다 반복하니까요. 이를 해결하기 위해 교환이 발생하면 true, 발생하지 않으면 false, 로 지정해서 개선할 수 있습니다. 우린 이런 과정을 최적화라고 해요.

bubbleSort(array)
  for i <- 1 to sizeOfArray - 1
    swapped <- false
    for j <- 1 to sizeOfArray - 1 - i
      if leftElement > rightElement
        swap leftElement and rightElement
        swapped <- true
    if swapped == false
      break
end bubbleSort

 

swapped <- false
...
if swapped == false
  break

만약 교환이 발생하지 않았다? 라는것은 이미 정렬되어있다는 의미이므로 반복문을 바로 break시킵니다.

그게 아니라면 for문을 실행시키죠.

 for j <- 1 to sizeOfArray - 1 - i
      if leftElement > rightElement
        swap leftElement and rightElement
        swapped <- true

이거는 위에서 봤던 코드입니다.

이렇게 swapped에 false값을 주는 것만으로 알고리즘의 시간을 훨씬 짧게 최적화 시킬 수 있습니다.