Java Day 11: 정렬 알고리즘과 Bubble Sort 완벽 이해하기

안녕하세요, NerbCodeX입니다! 😊
코로나로 인해 생활 패턴이 많이 달라지고 힘든 시간을 보내고 계실 텐데요, 이럴 때일수록 멘탈 관리와 꾸준한 학습이 중요합니다. 오늘도 자바 학습으로 한 걸음 나아가봅시다.

오늘은 자바 배열에서 정렬(Sorting)에 대해 배워보겠습니다. 배열을 사용할 때 꼭 필요한 작업 중 하나가 데이터 정렬인데요, 자바는 기본적으로 Arrays.sort() 메소드를 제공하여 손쉽게 정렬할 수 있습니다. 하지만 정렬 알고리즘의 개념과 동작 원리를 이해하면 더 효율적인 코드를 작성할 수 있습니다.

특히, Bubble Sort(버블 정렬)는 정렬 알고리즘 중 가장 기본적이고 이해하기 쉬운 방법으로, 학습의 첫 단계로 적합합니다. 이번 글에서는 Bubble Sort의 원리와 구현 방법을 살펴보고, 정렬 효율을 높이는 방법도 함께 알아보겠습니다.

그럼, 정렬 알고리즘의 세계로 함께 가보시죠! 😊

---

정렬의 개요

정렬의 필요 조건

• Key
• 차순

정렬의 종류 

• bubble, selection, radix, quick ... 

위에도 언급한 정렬 sort() 메소드는 정렬의 종류 중에 quicksort 알고리즘을 사용합니다. 다양한 종류의 정렬 알고리즘 중에 어떤 정렬을 사용하는지에 따라 그 효율성에 차이가 생깁니다. 

 

우선 이중에서 가장 기본이 되는 Bubble Sort에 대해서 알아보도록 하겠습니다. 

---

Bubble Sort 

예제) {10, 30, 70, 90, 5}를 큰수부터 작은수로 정렬하라 

해당 배열을 위와 같다고 생각하면 앞에부터 순차 비교를 진행한다. 

• 1차 비교 

위와 같은 1차 비교로 다음과 같은 결과를 얻게 된다. 

• 2차 비교

맨 뒤의 5는 가장 작은 수라 이제 그 앞의 4개의 수를 비교 정렬하게 된다. 위의 2차 비교로 아래의 결과를 얻게 된다. 

• 3차 비교

3차 비교까지 진행하고 나면 결과가 나온듯하다. 

이로써 우리가 원하는 5개의 숫자에 대한 정렬을 3번의 비교를 통해 얻게 되었다. 이를 배열로 정리해 보면 다음과 같은 2차원 배열이 필요하다. 

• 5개의 숫자의 정렬을 위해 필요한 최대 비교 수 (1,2)(2,3)(3,4)(4,5)(1,2)(2,3)(3,4)(4,5)
• (1,2)(2,3)(3,4)(4,5)
• (1,2)(2,3)(3,4)(4,5)
• {10, 30, 70, 90, 5)
• 세로 i=1,4 / 가로 j=1,4

그럼 Bubble Sort정렬을 위한 배열 공식을 알아보자 . 

---

Bubble Sort 정렬을 위한 배열 공식 - 방법1

예제) 5개의 배열의 수의 크기를 비교하는 공식 

 int[] k= {10,30,24,78,9}; //정렬한 배열

• 우선 1열의 비교 k(2) : k(3) 간의 비교 k(4) : k(5) 간의 비교 
• k(3) : k(4) 간의 비교
• k(1) : k(2) 간의 비교
• 실제 행열에서의 번호 (1~5대신에 0~4로) k(1) : k(2) 간의 비교k(3) : k(4) 간의 비교 
• k(2) : k(3) 간의 비교
• k(0) : k(1) 간의 비교
• 열은 j이면 j:j+1의 비교 
• k(j) : k(j+1) 간의 비교 

• 배열 공식 코드 (비교 공식 if)

           for (int i = 0; i < 4; i++) { //행 비교를 위해 4번을  비교  
                for (int j = 0; j < 4; j++) { // 열 비교를 위해  4번을 비교
                     if(k[j]<k[j+1]) { //앞에가 크거나 작으면  안바꾸나, 뒤가 크면 자리를 바꾼다.
                           int tmp=k[j]; //swap하기 위해 변수 tmp  생성
                           k[j]=k[j+1];
                           k[j+1]=tmp;
                     }// if end
                }// for j end, if 비교를 4번(열)
           }//for i end, if 비교를 4*4번(행)

• 출력 결과 

---

이를 비교할 숫자의 길이를 변경할 수 있게 바꾼다. 

즉 for문의 비교 숫자를 i<4가 아닌 i<k.length-1로 해도 된다. 

           for (int i = 0; i < k.length-1; i++) {
                for (int j = 0; j < k.length-1; j++) {

위와 같이 적용하면 배열의 숫자 길이와 무관하게 적용된다. 

           int[] k= {10,30,24,78,9,33,21,34}; //정렬한 배열
           
           for (int i = 0; i < k.length-1; i++) { //행 비교를  위해 4번을 비교 , i<k.length-1
                for (int j = 0; j < k.length-1; j++) { // 열  비교를 위해 4번을 비교 , j<k.length-1
                     if(k[j]<k[j+1]) { //앞에가 크거나 작으면  안바꾸나, 뒤가 크면 자리를 바꾼다.
                           int tmp=k[j]; //swap하기 위해 변수 tmp  생성
                           k[j]=k[j+1];
                           k[j+1]=tmp;
                     }// if end
                }// for j end, if 비교를 4번(열)
           }//for i end, if 비교를 4*4번(행)

• 출력 결과

---

Bubble 비교의 개선안 - 방법2

위의 1번째 방법의 문제점은 이미 비교한 뒷 부분을 중복 비교한다는 부분이다. 

뒷부분에 불필요한 비교를 제외하는 방법을 사용한다. 

  {10, 30, 70, 90, 5)
  (1,2)(2,3)(3,4)(4,5) : 4번
  (1,2)(2,3)(3,4)(4,5) : 3번
  (1,2)(2,3)(3,4)(4,5) : 2번
  (1,2)(2,3)(3,4)(4,5) : 1번

           for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4-i; j++) {//열에서 행으로 갈때 마다 하나씩 빼준다.
                     if(k[j]<k[j+1]) {
                           int tmp=k[j];
                           k[j]=k[j+1];
                           k[j+1]=tmp;
                     }// if end
                }// for j end
           }//for i end

위 방법으로  for (int j = 0; j < 4; j++) --> for (int j = 0; j < 4-i; j++)  16번 반복을 10번 반복으로 줄일 수 있다. 
마찬가지로 4, 4-i대신에 k.length를 써도 된다. 

        for (int i = 0; i < k.length-1; i++) {
            for (int j = 0; j < k.length-1-i; j++) {//열에서  행으로 갈때 마다 하나씩 빼준다.
                 if(k[j]<k[j+1]) {
                       int tmp=k[j];
                       k[j]=k[j+1];
                       k[j+1]=tmp;
                 }// if end
            }// for j end
       }//for i end

---

Bubble 비교의 개선안 - 방법3(스위치 기법)

다른 개선 방법으로는 중간에 정렬이 완료되었을 때 이후에 검사를 중단하고 마무리 한다.     
중간에 검사를 하는 코드가 추가되어 검사 회수는 줄지만 빠르다고 장담할 수는 없다. 
  {30,70,90,10,5)
  (1,2)(2,3)(3,4)(4,5) : 
  (1,2)(2,3)(3,4)(4,5) : // 이미 정렬이 끝나 뒤쪽이 필요 없게 된다. 
  (1,2)(2,3)(3,4)(4,5) : 
  (1,2)(2,3)(3,4)(4,5) :

• 문제) 10개의 배열 index안에 학생들의 키가 있다. 이를 키 오름차순으로 sort하고 출력하시오, 단 자바의 sort api를 사용하지 마시오 

     public static void main(String[] args) {
           int[] ki= {175, 180, 174, 185, 165, 160, 174, 181,  179, 169};
           
           //원본 데이터 출력
           for (int i = 0; i < ki.length; i++) {
                System.out.print(ki[i]+"\t");   
           }
           System.out.println();
           
            // 정렬
           for (int i = 0; i < ki.length-1; i++) {
                for (int j = 0; j < ki.length-1-i; j++) {
                     if(ki[j]>ki[j+1]) { // 오름차순으로 부호 바꿈
                           int tmp=ki[j];
                           ki[j]=ki[j+1];
                           ki[j+1]=tmp;
                     }//if end
                }// for j end
           }// for i end
           System.out.println();
           
           //정렬 데이터 출력
           for (int i = 0; i < ki.length; i++) {
                System.out.print(ki[i]+"\t");   
           }
           System.out.println();
           
     }// main end

• 출력 결과

---

자바에서 제공하는 sort 메소드

import java.util.Arrays;
...
int[] bae= {10,90,100,60,70};
        Arrays.sort(bae); //

            import java.util.Arrays;
...
            int[] bae= {10,90,100,60,70};
            Arrays.sort(bae);

           for (int i = 0; i < bae.length; i++) {
                System.out.print(bae[i]+"\t");
           }
           System.out.println();

• 출력 결과 (기본 오름차순 정렬) 

• 내림차순 출력할때 코드 

           for (int i = bae.length-1; i>=0 ; i--) {
                System.out.print(bae[i]+"\t");
           }
           System.out.println();

---

 

오늘은 자바에서 Bubble Sort를 활용한 정렬 알고리즘과 이를 최적화하는 다양한 방법을 배워보았습니다. 또한, 자바에서 제공하는 Arrays.sort() 메소드를 사용하여 더욱 간편하게 정렬할 수 있는 방법도 살펴보았죠.

정렬은 데이터의 효율적인 처리를 위해 매우 중요한 부분입니다. Bubble Sort처럼 단순한 정렬부터 시작해, 점점 더 복잡한 정렬 알고리즘(Quick Sort, Merge Sort 등)을 학습하면 프로그래밍의 기본기를 탄탄히 다질 수 있습니다.

다음 시간에는 정렬의 연장선으로 검색(Search)에 대해 다룰 예정입니다. 정렬된 데이터를 기반으로 데이터를 효율적으로 검색하는 다양한 방법과 알고리즘을 배워볼 예정이니 많은 기대 부탁드립니다.

학습은 작은 한 걸음부터 시작됩니다. 오늘 배운 내용을 반복 연습하며 코딩 실력을 키워보세요! 😊
그럼 다음 시간에 또 뵙겠습니다. 감사합니다!

 

 

Java Day 10: 2차원 배열 기초와 실습 예제 총정리

 

 

Java Day 9: 배열의 기본 개념과 실습 - 1차원 배열 쉽게 배우기