섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 2. 버블정렬

문제

• N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
• 정렬하는 방법은 선택정렬입니다.

입력

• 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
• 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

출력

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

입출력 예제

---

풀이방식

이번 문제는 버블정렬을 사용하여 푸는 문제이다.

 

버블정렬이란 아래와 같이 이웃한 두 수를 비교하여 위치를 바꾸며 정렬하는 것을 말한다.

즉, 13과 5를 비교해서 더 작은 값인 5를 13과 위치를 바꾸는 것을 말한다.

아래 배열에서 버블정렬이 1회 수행되면 [5, 13, 11, 7, 23, 15] 가 나온다.

2회 수행되면 [5, 11, 13, 7, 23, 15]가 나온다.

---

설계과정

1. 이웃한 앞, 뒤 값을 비교하여 더 적은 값과 위치를 변경한다.

2. 이를 반복하여 정렬한다.

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. int[ ] 형으로 메소드를 작성한다.

 

3. 0부터 N - 1까지 도는 for문을 작성한다.

• 맨 마지막 원소는 그 앞에 과정을 통해 자동적으로 정렬되므로 한번 더 돌 필요는 없다.

4. 0부터 N - i - 1까지 도는 for문을 작성하여 더 적은 수를 앞으로 보낸다.

• 맨 마지막 원소는 그 뒤에 값이 없으므로 비교할 필요가 없다.
• 앞의 원소와 비교한 것으로 마지막 정렬이 끝나기 때문이다.
• 즉, j는 정렬이 될 수록 마지막-1 까지만 돌아도 된다.

5. j와 j+1의 값을 비교하여 j가 더 크면 두 값의 위치를 바꿔준다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.