Day 11 - 정렬 (Sort) 하기

안녕하십니까 아재나라입니다. 

요즘 파이널판타지7 리메이크 플레이로 자바 업로드가 뜸해 졌습니다. 공부를 더 해야하는데 자꾸 이런 저런 핑계로 늦어지네요. 코로나로 연금 생활이 길어지면서 많은 사람들이 힘들어하고 있는데 이럴수록 건강관리 멘탈관리가 중요한것 같습니다. 

 

그럼 자바에서 정렬관련 사항은 어떤지 살펴 보겠습니다. 

---

배열이 나오게 되면 아무래도 함께 고민해야하는 부분이 정렬입니다. 크기 순으로 정렬해야하는 부분인데 가장 손쉬운 방법은 Arrays 클래스의 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개의 숫자의 정렬을 위해 필요한 최대 비교 수 

  {10, 30, 70, 90, 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)

• 세로 i=1,4 / 가로 j=1,4

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

---

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

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

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

• 우선 1열의 비교 

  k(1) : k(2) 간의 비교

  k(2) : k(3) 간의 비교 

  k(3) : k(4) 간의 비교

  k(4) : k(5) 간의 비교 

• 실제 행열에서의 번호 (1~5대신에 0~4로) 

  k(0) : k(1) 간의 비교

  k(1) : k(2) 간의 비교

  k(2) : k(3) 간의 비교

  k(3) : k(4) 간의 비교 

• 열은 j이면 j:j+1의 비교 

  k(j) : k(j+1) 간의 비교 

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

• if(arr[j]<arr[j+1]){

     int tmp=arr[j];

     arr[j]=arr[j+1];

     arr[j+1]=tmp;

  }

           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();

---

이렇게 정렬에 대한 내용을 살펴 보았다. 자바에서 제공하는 sort() 메소드를 이용하면 사실 쉽게 정렬이 가능한 부분이라 위와 같은 개념 정리가 불필요해 보일수도 있지만, 말 그대로 개념을 정리하는 부분이라 생각하면 될 것 같다. 

 

정렬과 더불어 검색 부분이 있는데 이부분은 다음 시간에 살펴 보도록 하겠다.