[LeetCode] 75. Sort Colors - 삽입정렬(Insertion Sort) + 합병정렬(Merge Sort) + 퀵정렬(Quick Sort) JAVA

https://leetcode.com/problems/sort-colors/

코드설명

삽입정렬(Insertion Sort) + 합병정렬(Merge Sort) + 퀵정렬(Quick Sort) 을 활용합니다.

 

사실, 여기서 위의 3가지 정렬방식중 2가지만 In-Place 정렬입니다.

삽입정렬(Insertion Sort)과 퀵정렬(Quick Sort)입니다.

>>

합병정렬(Merge Sort)는 In-Place 정렬이 아닌, 별도의 메모리를 활용합니다.

 

위의 3가지 방식을 활용하여 구현해보겠습니다.

코드

1. 선택정렬(Selection Sort) 시간복잡도 O(N^2) 공간복잡도 O(1)

가장 앞에서부터 처리하며, 나머지 범위 중 가장 작은 값을 "선택Selection"을 하여 가장 작은 숫자씩 하나씩 선택한다는 의미에서 선택정렬입니다.

class Solution {
    public void sortColors(int[] nums) {
        int N = nums.length;
        for(int i=0; i<N; i++){
            int minIdx = i;
            for(int j=i+1; j<N; j++){
                if(nums[minIdx] > nums[j]){
                    minIdx = j;
                }
            }
            swap(nums, minIdx, i);
        }   
    }
    void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

2. 삽입정렬(Insertion Sort) 시간복잡도 빅오 O(N^2)  빅오메가 O(N), 공간복잡도 O(1)  In-Place이기에 공간복잡도는 O(1)입니다.

앞에서부터 한개의 공간씩 값을 확정시킵니다. 만약, i-1이 < i 인 상황이라면, [0..i-1]번에서는 반드시 정렬되어 있음이 보장됩니다.

class Solution {
    public void sortColors(int[] nums) {
        int N = nums.length;
        for(int i=0; i<N; i++){
            int j = i;
            while(j > 0 && nums[j-1] > nums[j]){
                swap(nums, j-1, j);
                j -= 1;
            }
        }
    }
    void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

 

3. 합병정렬(merge sort)를 활용한 경우입니다. 공간복잡도 O(n)+O(logn)= O(N), 시간복잡도 O(n log n) 

문제에서 nums[]값이 In-Place Sort가 아니기에 값이 바뀌어서 이 문제를 통과하지 못합니다.

class Solution {
    public void sortColors(int[] nums) {
        nums = mergeSort(nums, 0, nums.length - 1);            
    }
    
    int[] mergeSort(int[] nums, int left, int right){
        if(left == right){
            return new int[]{nums[left]};
        }
        int mid = (left + right) / 2;
        int[] l = mergeSort(nums, left, mid);
        int[] r = mergeSort(nums, mid + 1, right);
        int[] sorted = merge(l, r);
        return sorted;
    }

    int[] merge(int[] l, int[] r){
        int[] arr = new int[l.length + r.length];
        int left = 0, right = 0;
        int idx = 0;
        while(left < l.length && right < r.length){
            if(l[left] < r[right] ){
                arr[idx++] = l[left++];
            }
            else if(l[left] >= r[right] ){
                arr[idx++] = r[right++];
            }
        }

        while(left < l.length){
            arr[idx++] = l[left++];
        }

        while(right < r.length){
            arr[idx++] = r[right++];
        }
        return arr;
    }
}

 

4. 퀵정렬(QuickSort) 사용한경우. 시간복잡도 O(n log n) 공간복잡도 O(1) -> 재귀 메모리스택은 제외하고 생각.

class Solution {
    public void sortColors(int[] nums) {
        int N = nums.length;
        quickSort(nums, 0, N - 1);
    }

    void quickSort(int[] A, int start, int end){
        if(start >= end) return ;
        int partitionIdx = partition(A, start, end);
        quickSort(A, start, partitionIdx - 1);
        quickSort(A, partitionIdx + 1, end);
    }

    int partition(int[] A, int start, int end){
        int pivot = A[start];
        int left = start + 1;
        int right = end;
        while(left <= right){
            while(left <= end && pivot >= A[left]){
                left ++;
            }
            while(right >= start && pivot < A[right]){
                right--;
            }
            if(left < right){
                swap(A, left, right);
            }
        }
        swap(A, start, right);
        return right;
    }
    void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

}

 

4. HashMap을 활용한경우입니다.

class Solution {
    public void sortColors(int[] nums) {
        HashMap<Integer, Integer> hashmap = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            hashmap.put(nums[i], hashmap.getOrDefault(nums[i], 0) + 1);
        }
        int idx = 0;
        for(int i=0; i<3; i++){
            if(hashmap.containsKey(i)){
                int frequency = hashmap.get(i);
                for(int j=0; j<frequency; j++){
                    nums[idx++] = i;
                }
            }
        }
    }

}