자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 버블 정렬

 

https://hyejin.tistory.com/1240

자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 선택 정

-> 이전 문제 풀이 

 

 

 

2. 버블 정렬 

설명

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

정렬하는 방법은 버블정렬입니다.

 

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

 

출력

오름차순으로 정렬된 수열을 출력합니다.

 

예시 입력 1 

6
13 5 11 7 23 15

 

예시 출력 1

5 7 11 13 15 23

 

 

문제 풀이 1

public int[] solution(int n, int[] arr)
{
   int idx = n;
   while ( idx != 0)
   {
      idx--;
      for (int i = 0; i < n - 1; i++)
      {
         if (arr[i] > arr[i + 1]) {
            int tmp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = tmp;
         }
      }
   }
   
   return arr;
}

 

👩‍💻 : 버블 정렬은 배열에서 바로 옆 (오른쪽) 값과 비교해서 오른쪽 값이 더 작으면 현재 값과 비교하면서 옆으로 나아가며 정렬하는 방법이다. 

 

idx 인덱스 값을 n 으로 설정하고 while 반복문을 도는데 이때 조건이 0이 되지 않을 때 까지 하는 것이다. 

(즉, n 번 반복하는 것!) 

 

한번  반복할 때 마다, idx 값이 1씩 줄어들게 하고, 그 다음 for문을 도는데 이때에는 i가 n-1 전까지 돌면서 

arr[i]와 arr[i + 1] 을 비교해서 arr[i+1]이 더 작으면 arr[i]과 값을 바꾸면서 오름차순으로 정렬하고 arr를 리턴해줬다. 

 

 

 

문제 풀이 2

public int[] solution2(int n, int[] arr)
{
   for (int i = 0; i < n - 1; i++) // i : 턴의 횟수
   {
      for (int j = 0; j < n - i - 1; j++)
      {
         if (arr[j] > arr[j + 1]) {
            int tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
         }
      }
   }
   return arr;
}

👾 : 강사님은 while문이 아니라 이중 for문을 통해서 문제를 풀었다. 

우선 i는 턴하는 횟수를 나타내는데, 즉 몇번 반복하느냐 이다 ! 

n - 1 번 턴해도 되는 이유는 두개를 비교하면 n까지 i가 갈 필요 없기 때문이다.

 

그리고 j는 n - i - 1 번 하면 되는데 j 랑 j + 1 값을 비교하기 때문에 마지막값은 마지막 값의 j -1 에서 비교되기 때문이다. 

arr[j]랑 arr[j+1] 비교해서 arr[j+1]이 더 작으면 arr[j]과 arr[j+1] 값을 비교해서 교환해주면 된다. 

 

그러면 오름 차순으로 정렬되고 arr를 리턴하면 된다 !