[백준] 소트인사이트(선택 정렬 사용)

---

백준 온라인 저지 1427번 - 소트인사이드

내림차순 수 정렬문제를 선택 정렬 알고리즘을 통해 해결해보았다.

정렬 해야하는 데이터의 크기가 작아서 선택 정렬로도 2초라는 시간 내에 충분하게 정렬할 수 있었다.

지켜야 할 키 포인트는 아래와 같다!

1. loop내에서 현재 인덱스의 데이터와 최대 또는 최소값 간의 swap 연산

SelectionSort.java

package com.example.Etc;

/**
 * 백준 온라인 저지 1427 - 소트인사이드
 */
public class SelectionSort {
    public int[] sortDesc(int[] target) {
        // int to int[]
        int[] arr = target;

        for(int i = 0; i < arr.length; i++) {
            int maxIdx = i;
            // 내부 반복문을 통해 가장 큰 값이 있는 Index 찾기
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[j] > arr[maxIdx]) {
                    maxIdx = j;
                }
            }
            // 비교할 첫번째 값과 찾은 가장 큰 값을 비교했을 때 찾은 가장 큰 값이 더 클 경우 swap
            if(arr[i] < arr[maxIdx]) {
                int temp = arr[i];
                arr[i] = arr[maxIdx];
                arr[maxIdx] = temp;
            }
        }
        return arr;
    }
}

SelectionSortTest.java

package com.example.Etc;

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public class SelectionSortTest {
    @Test
    public void selectionSortTest() {

        SelectionSort sort = new SelectionSort();

        int[] target1 = {2, 1, 4, 3};
        int[] result1 = sort.sortDesc(target1);

        int[] target2 = {9, 9, 9, 9, 9, 8, 9, 9, 9};
        int[] result2 = sort.sortDesc(target2);

        int[] expected1 = {4, 3, 2, 1};
        int[] expected2 = {9, 9, 9, 9, 9, 9, 9, 9, 8};

        assertArrayEquals(expected1, result1);
        assertArrayEquals(expected2, result2);
    }
}