[백준] 2750_수 정렬하기.java

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

나의 풀이

• 정렬문제는 쉽게 Arrays.sort() 함수를 사용해서 쉽게 정렬을 할 수 있지만,
  그 동작 원리를 구현해보기 위해 선택정렬과 삽입정렬로 두가지의 풀이를 추가했다.
• 나동빈님의 '이것이 취업을 위한 코딩테스트다' 를 참고했습니다.

선택정렬이란?

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬알고리즘이다.

step1

전체 범위 중 가장 작은 숫자 0을 선택해 0번째 index 에 있는 7과 바꿔줍니다.

step2

교체한 0을 제외하고 처리되지 않은 데이터 중 가장 작은 1을 선택해 5와 바꿔줍니다.

step3

교체한 1을 제외하고 처리되지 않은 데이터 중 가장 작은 2를 선택해 9와 바꿔줍니다.

step4

교체한 2를 제외하고 처리되지 않은 데이터 중 가장 작은 숫자 3를 선택해 7와 바꿔줍니다.

step5

이 과정을 반복수행하다 보면 다음과 같이 오름차순으로 정렬되게 됩니다.

---

삽입정렬이란?

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다

step1

첫번째 데이터 7은 그 자체로 정렬이 되어 있다고 판단하고,두 번째 데이터인 5가 어떤 위치로 들어갈지 판단합니다. 7의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재합니다.

step2

이어서 9가 어떤 위치로 들어갈지 판단합니다.

step3

이어서 0이 어떤 위치로 들어갈지 판단합니다.

step4

이러한 과정을 반복하면 다음과 같이 정렬이 완료됩니다.

---

알고리즘을 실제 문제 백준_수 정렬하기.java 에 적용

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]);
}

}
}