Bubble Sort, 버블 정렬, 거품정렬

• 자바의 기본 정렬 중 하나인 거품 정렬을 알아보자.
• 물속에서 공기 방울이 가장 큰 거품이 맨위로 올라오는 것과 같은 이치.
  ※(아직 내 실력은 거품이다ㅠㅠ 거품이 생기기 조차 못함 ㅠ)  
• 정렬 대상인 n번째 인덱스와 n+1 인덱스의 값을 비교해서 더 큰 수를 뒤로 보내는 정렬 방법이다.

1.

3

1

2

4

6

5

 

int[] nums = {3, 1, 2, 4, 6, 5};

• 위와 같은 배열이 선언되었다.
• 첫 번째 인덱스에 있는 3은 이제 자기 자리를 찾기 위한 여정을 떠난다.
• 3과 1을 비교하면 3 이 1보다 크다. 3을 옆으로 보내자

1

3

2

4

6

5

• 3은 이제 2를 만났다. 3은 2보다 크니깐 2는 알아서 자리를 비켜준다.

1

2

3

4

6

5

• 3은 자기보다 작은 1과 2를 지나쳐 4를 만났다. 인생은 실전이다. 약육강식의 법칙이 적용된다.
• 3은 4보다 작다. 4를 지나갈 수 없어서 현 위치를 지키기로 했다.
• 위와 같은 상황을 아래와 같이 코드로 표현해보자

for(int i = 0; i < nums.length - 1; i++) {
  if(nums[i] > nums[i + 1]) {
     int temp = nums[i];
     nums[i] = nums[i + 1];
     nums[i + 1] = temp;
  }
}

• 이렇게 끝! 이면 좋겠지만 6 과 5 가 남았다. 첫 번째 인덱스에 있는 숫자인 3을 자기 자리를 찾기 위한 여행을 보냈으니 나머지 2, 3, 4, 5, 번째 인덱스에 있는 숫자들을 여행 보내야 한다. 마지막 인덱스 에 있는 숫자는 여행을 갈 필요가 없다. 이미 정렬이 끝나있을테니
• 이 과정을 배열길이 만큼 다시 반복 하면 숫자들을 제자리를 찾아갈 것이다.

class Main {
  public static void main(String[] args) {
   int[] nums = {3, 1, 2, 4, 6, 5};

   for(int j = nums.length - 1; j > 0; j-- )
     for(int i = 0; i < j; i++) {
       if(nums[i] > nums[i + 1]) {
         int temp = nums[i];
         nums[i] = nums[i + 1];
         nums[i + 1] = temp;
      }
    }
  }
}

※ 실행 해보도록 하자!

 

 

• https://www.youtube.com/watch?v=lyZQPjUT5B4

※ 원리를 이해하기 좋은 영상이다. 시간이 오래 걸리니 제발 2배속으로 보기를 추천한다.