문제
- 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) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
'알고리즘 > 인프런' 카테고리의 다른 글
섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 4. Least Recently Used (0) | 2022.11.01 |
---|---|
섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 3. 삽입정렬 (0) | 2022.10.31 |
섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 1. 선택정렬 (0) | 2022.10.30 |
섹션 5. Stack, Queue(자료구조) 8. 응급실 (0) | 2022.10.25 |
섹션 5. Stack, Queue(자료구조) 7. 교육과정 설계 (0) | 2022.10.24 |