N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
- 정렬문제는 쉽게 Arrays.sort() 함수를 사용해서 쉽게 정렬을 할 수 있지만,
그 동작 원리를 구현해보기 위해 선택정렬과 삽입정렬로 두가지의 풀이를 추가했다.- 나동빈님의 '이것이 취업을 위한 코딩테스트다' 를 참고했습니다.
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬알고리즘이다.
전체 범위 중 가장 작은 숫자 0을 선택해 0번째 index 에 있는 7과 바꿔줍니다.
교체한 0을 제외하고 처리되지 않은 데이터 중 가장 작은 1을 선택해 5와 바꿔줍니다.
교체한 1을 제외하고 처리되지 않은 데이터 중 가장 작은 2를 선택해 9와 바꿔줍니다.
교체한 2를 제외하고 처리되지 않은 데이터 중 가장 작은 숫자 3를 선택해 7와 바꿔줍니다.
이 과정을 반복수행하다 보면 다음과 같이 오름차순으로 정렬되게 됩니다.
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다
첫번째 데이터 7은 그 자체로 정렬이 되어 있다고 판단하고,두 번째 데이터인 5가 어떤 위치로 들어갈지 판단합니다. 7의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재합니다.
이어서 9가 어떤 위치로 들어갈지 판단합니다.
이어서 0이 어떤 위치로 들어갈지 판단합니다.
이러한 과정을 반복하면 다음과 같이 정렬이 완료됩니다.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //길이
int []arr = new int[n];
for(int i = 0;i<n;i++){
arr[i] = sc.nextInt();
}
//Arrays.sort(arr);
// 1.선택정렬
// for(int i = 0;i<n;i++){
// int min_index = i;
// for(int j = i+1;j<n;j++){
// if(arr[min_index] > arr[j]){
// min_index = j;
// }
// }
// int temp = arr[i];
// arr[i] = arr[min_index];
// arr[min_index] = temp;
// }
//2.삽입정렬
for(int i = 1;i<n;i++){
for(int j = i-1;j >= 0;j--){
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}else{
break;
}
}
}
for(int i = 0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
}