[Java] 선택정렬 응용 문제- 오름차순/ 내림차순 / 알파벳

 

문제 1: 오름차순 선택 정렬

다음과 같은 배열이 주어졌다.

[10, 3, 8, 15, 6]

문제 : 배열을 오름차순으로 정렬하라.

출력 예시 :

[3, 6, 8, 10, 15]

 

<나의 답안>

import java.util.Arrays;

public static void selctionArrays (int[] arr){
   int n = arr.length;
   
   for(int i = o; i < n-1; i++) {
      int minIndex = i;
      for(int j = i+1; j < n; j++) {
         if(arr[j] < arr[minIndex]){
           minIndex = j
         }
      }
      int temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
   }
}

---

<채점>

문제점 1. 메서드 이름 잘못 사용

public static void selectionSort (int[] arr) {

메서드 이름이 selctionArrays 로 작성되다.

selectionSort처럼 철자를 올바르게 고쳐야 한다.

 

문제점 2. for 루프에서 소문자 o를 사용

for(int i = 0; i < n-1; i++) {

자바에서는 소문자 o와 숫자 0이 다르므로 에러가 발생한다.

 

문제점 3. minIndex = j뒤에 세미콜론 없음

minIndex = j;

 

모두 사소한 오타와 ;를 붙이지 않아서 틀렸다.

사소한 실수라도 기록하여 완벽한 코드를 구사해야지!

 

<덧붙일 테스트 코드>

public static void main(String[] args) {
   int[] arr = {10, 3, 8, 15, 6};
   selectionSort(arr);
   System.out.println(Arrays.toString(arr));

 

---

<정답 코드>

import java.util.Arrays;

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 3, 8, 15, 6};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

출력 배열:

[3, 6, 8, 10, 15]

---

문제 2: 내림차순 선택 정렬

다음과 같은 배열이 주어졌다.

[12, 4, 9, 16, 7]

 문제: 배열을 내림차순으로 정렬하라.

  출력 예시 : 

[16, 12, 9, 7, 4]

---

< 나의 답안 >

import java.util.Arrays;

public static void selectionSort(int[] arr) {
    int num = arr.length;
    for (int i = 0; i < n-1; i++) {
      int maxIndex = i;
      for (int j = i+1; j < n ; j++) {
         if (arr[j] > arr[maxIndex]) {
             maxIndex = j;
         }
      }
      int temp = arr[maxIndex];
      arr[maxIndex] = arr[j];
      arr[j] = arr[maxIndex]; 
      
    }
}

 

<채점>

문제점 1: 변수 이름 혼동 (num과 n)

int num = arr.length;
for (int i = 0; i < num-1; i++) {

- 배열의 길이를 저장한 변수 이름이 num인데, for 루프에서 n을 사용하고 있다.

- n은 선언되지 않은 변수이므로 컴파일 에러가 발생한다.

 

문제점 2: arr[j]와 arr[maxIndex] 교환 오류

int temp = arr[maxIndex];
arr[maxIndex] = arr[i];
arr[i] = temp;

---

<정답 코드>

import java.util.Arrays;

public class SelctionSort {
   public static void selectionSortDescending(int[] arr) {
        int num = arr.length; //배열 길이 저장 
        
        for (int i = 0; i < num-1; i++) {
           int maxIndex = i; // 현재 위치를 최대값 인덱스로 가정
           
             for (int j = i+1 ; j < num; j++){
                 if (arr[j] > arr[maxIndex]) {
                      maxIndex = j;
                 }
             }
             int temp = arr[maxIndex];
             arr[maxIndex] = arr[i];
             arr[i] = temp;
           
        }
   }
   public static void main(String[] args) {
      int[] arr = {12, 4, 9, 16, 7};
      selectionSortDescending(arr);
      System.out.println(Arrays.toString(arr));
   }
}

 

<출력 배열>

[16, 12, 9, 7, 4]

 

---

문제 3 : 문자열 배열 정렬

다음과 같은 문자열 배열이 주어졌다.

String[] arr = {"grape", "apple", "banana", "cherry", "fig"};

문제 : 문자열 배열을 알파벳 순서(오름차순)로 정렬하시오

<출력예시>

["apple", "banana", "cherry", "fig", "grape"]

 

문제 풀이 힌트

 문자열을 비교할 때는 compareTo 메서드를 사용한다.

   - a.compareTo(b):

         - a가 b보다 앞에 있으면 음수를 반환.

         - a가 b보다 뒤에 있으면 양수를 반환.

         - a와 b가 같으면 0을 반환.

 

 

import java.util.Arrays;

public class SelctionSortStrings {
    public static void selectionSort(String[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n-1; i++) {
            int minIndex = i; // 현재 위치를 최소값으로 가정
            
            for (int j = i+1; j < n; j++) {
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j; // 더 앞서는 문자열이면 최소값 갱신 
                 }
            }
            //최소값과 현재 위치 값 교환
            String temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    public static void main(String[] args) {
       String[] arr = {"grape", "apple", "banana", "cherry", "fig"};
       System.out.println("Before Sorting: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("After Sorting: " + Arrays.toString(arr));
    }

}

1. 배열의 첫 번째 문자열을 기준으로 잡는다.

2. 첫 번째 문자열 이후의 문자열들을 비교하여 가장 앞에 오는(알파벳 순서상 작은) 문자열을 찾는다.

3. 찾은 문자열과 기준 문자열을 교환한다.

4. 두 번째 문자열로 이동하여 동일한 과정을 반복한다. 

5. 배열의 끝까지 가면 모든 문자열이 알파벳 순서로 정렬된다. 

 

<출력>

Before Sorting: [grape, apple, banana, cherry, fig]
After Sorting: [apple, banana, cherry, fig, grape]