재귀호출을 이용한 최소값 찾기, 총합 구하기, 선택 정렬

1. 최소값 찾기

import java.util.Arrays;
 
public class Minimum {
    public static void main(String[] args) {
        int len = 10;
        int[] arr = new int[len];
 
        for(int i = 1; i <= len; i++) 
            arr[i - 1] = ((int)((Math.random() * len) + 1));
        
        System.out.println(Arrays.toString(arr));
        System.out.println("Minimum: " + min(arr, len - 1));
    }
    
    public static int min(int[] arr, int n) {
        if(n == 1) {
            return (arr[0] < arr[1]) ? arr[0] : arr[1];
        } else {
            int m = min(arr, n - 1);
            return (arr[n] < m) ? arr[n] : m;
        }
    }
}

시간 복잡도: $O(n)$

 

 

2. 총합 구하기

import java.util.Arrays;
 
public class Summation {
    public static void main(String[] args) {
        int len = 10;
        int[] arr = new int[len];
        
        for(int i = 1; i <= len; i++) {
            arr[i - 1] = i;
        }
        
        int sum = sum(arr, len - 1);
        
        System.out.println(Arrays.toString(arr));
        System.out.println("Sum: " + sum);
    }
    
    public static int sum(int[] arr, int n) {
        if(n == 1) {
            return (arr[0] + arr[1]);
        } else {
            return (arr[n] + sum(arr, n - 1));
        }
    }
}

시간 복잡도: $O(n)$

 

 

3. 선택 정렬

import java.util.Arrays;
 
public class SelectionSort {
 
    public static void main(String[] args) {
        int len = 10;
        int[] arr = new int[len];
        
        for(int i = 1; i <= len; i++) {
            arr[i - 1] = ((int)((Math.random() * len) + 1));
        }
 
        System.out.println(Arrays.toString(arr));
        sort(arr, len - 1);
        System.out.println(Arrays.toString(arr));
    }
 
    public static void sort(int[] arr, int beginIdx) {
        if(beginIdx > 0) {
            sort(arr, beginIdx - 1);
        }
 
        int m = minIdx(arr, beginIdx);
        int temp = arr[beginIdx];
        arr[beginIdx] = arr[m];
        arr[m] = temp;
    }
 
    public static int minIdx(int[] arr, int beginIdx) {
        if(beginIdx == arr.length - 1) {
            return (arr.length - 1);
        } else {
            int m = minIdx(arr, beginIdx + 1);
            if(arr[beginIdx] < arr[m]) {
                return beginIdx;
            } else {
                return m;
            }
        }
    }
}

시간 복잡도: (여전히) $O(n^2)$

 

 

 

운이 좋았다. 예전에 재귀로 최소값 구하는 걸 구현해놨었는데(https://t0pli.tistory.com/171), 이번 과제는 여기서 응용하는 것 뿐이었다.

최소값 구하는 걸 해놓으니까 총합 구하는 건 거의 바로 구현했다.

선택 정렬이 좀 어렵긴 했지만 어차피 중요한 건 최소값의 인덱스를 찾는 거고, 결국 최소값 구하기의 응용일 뿐이라 생각보다는 빨리 끝냈다.