기수 정렬, 계수 정렬, 셸 정렬

□ 기수 정렬(Radix Sort)

- 낮은 자리 수(1의자리)부터 정렬하는 방식

- 각 원소 간의 비교 연산을 하지 않아 빠른지만, 기수 테이블(Queue)을 위한 메모리가 필요

- 알고리즘 복잡도 : O(dn)

public static void radixSort(int[] arr) {

        // 기수 테이블
        ArrayList<Queue<Integer>> list = new ArrayList<>();
        for(int i = 0; i< 10; i++) {
            list.add(new LinkedList<>());
        }

        int idx = 0;
        int div = 1;                    // 1의 자리
        int maxLen = getMaxLen(arr);    // 기수정렬을 몇번 시행할지 자릿수

        for(int i = 0; i< maxLen; i++) {            // 자릿수 만큼 시행
            for(int j = 0; j<arr.length; j++) {     // 1의자리부터 시작
                list.get((arr[j] / div) % 10).offer(arr[j]);    // index를 얻어 리스트에 넣어줌
            }

            // 순서대로 가져와서 배치
            for(int j = 0; j<10;j++) {
                Queue<Integer> queue = list.get(j);

                while(!queue.isEmpty()) {
                    arr[idx++] = queue.poll();
                }
            }
        }
        idx = 0;
        div *= 10;

    }

    // 최대 자릿수 구하기
    public static int getMaxLen(int[] arr) {
        int maxLen = 0;
        for(int i = 0; i<arr.length; i++) {
            int len = (int)Math.log10(arr[i])+1;    //자릿수 구하기
            if(maxLen < len) {
                maxLen = len;
            }
        }
        return maxLen;
    }

 

 

□ 계수 정렬(Counting Sort)

- 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식

- 제일 큰 값을 기준으로 카운팅 테이블(Array)크기를 설정하고 Index와 숫자가 똑같으면 +1

- 카운팅 테이블을 위한 메모리 필요

- 알고리즘 복잡도 : O(n+k) k : 정렬 대상 데이터 중 최대 값

 public static void countingSort(int[] arr) {
        // 카운팅 테이블 만들기
        int max = Arrays.stream(arr).max().getAsInt();
        int[] cnArr = new int[max+1];
        for(int i = 0; i< arr.length; i++) {
            cnArr[arr[i]]++;
        }

        int idx = 0;
        for(int i = 0; i< cnArr.length; i++) {
            while(cnArr[i] > 0) {
                arr[idx++] = i;
                cnArr[i] -= 1;
            }
        }

        // 위의 방법 말고도 쓸모없는 공간을 줄이기 위해 있는 것만 공간을 만듬
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int item: arr) {
            map.put(item, map.getOrDefault(item, 0)+1);
        }
        int idx2 = 0;
        ArrayList<Integer> list = new ArrayList<>(map.keySet());
        Collections.sort(list);

        for(int i = 0; i < list.size(); i++) {
            int cnt = map.get(list.get(i));
            while(cnt>0) {
                arr[idx2++] = list.get(i);
                cnt--;
            }
        }
    }

 

□ 셸 정렬

- 삽입 정렬의 약점을 보완한 정렬 방식

- 오름차순, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 모두 교환 필요

- 이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교

- 알고리즘 복잡도 : O(n^2) : 간격 설정에 따라 Worst case는 삽입 정렬과 동일

 

 

 

 ❖ nums 배열에서 흰색부터 빨강 순으로 인접하게 정렬시킨 후 출력하는 프로그램

    // 입력 : 2 0 2 1 1 0
    // 출력 : 0 0 1 1 2 2
    // 중복된 값이 있으므로 안정된 정렬 사용
   public static void solution(int[] arr) {
       if(arr == null || arr.length == 0) {
           return;
       }

       int[] cnArr = new int[3];
       for(int i = 0; i<arr.length;i++) {
           cnArr[arr[i]]++;
       }

       int idx = 0;
       for(int i = 0; i<cnArr.length;i++) {
           while(cnArr[i] > 0 ){
               arr[idx++] = i;
               cnArr[i]--;
           }
       }
       
   }

 

❖ 철자 순서를 바꾸었을 때 같아지는 문자 묶어서 출력

    // 철자 순서를 바꾸면 같아지는 문자를 anagram으로 묶어서 출력
    // anagram 그룹내에서 출력 순서는 상관없음
    // elvis <-> lives

    // 입력 : eat tea tan ate nat bat
    // 출력 : [[eat, tea, ate], [bat],[tan, nat]]

    // 정렬하면 같은 문자가 되는 것끼리 묶어서 출력
    public static ArrayList<ArrayList<String>> solution(String[] strs) {
        HashMap<String,ArrayList<String>> map = new HashMap<>();

        for(String s : strs) {
            char[] cArr = s.toCharArray();          // 정렬하기 위해 변환
            sort(cArr);                             // 정렬 aet
            String key = String.valueOf(cArr);      // 이게 키가 될것임
            
            if(!map.containsKey(key)) {             // map에 키가 없다면
                map.put(key, new ArrayList<>());    // 새로 만들어 넣어줌
            }
            map.get(key).add(s);                    // 키가 aet인 eat을 추가
        }

        return new ArrayList<>(map.values());
    }

    // 삽입 정렬
    public static void sort(char[] arr) {
        for(int i = 1; i<arr.length;i++) {
            char temp = arr[i];
            int j;
            for(j = i; j>0 && arr[j-1]> temp; j--) {
                arr[j] = arr[j-1];
            }
            arr[j] = temp;
        }
    }

 

❖ 오버랩 되는 구간을 합치는 프로그램

    // intervals라는 구간으로 이루어진 배열이 주어졌을 때
    // 오버랩 되는 구간을 합치는 프로그램을 작성
    // 합친 구간은 오름차순으로 정렬

    // 입력 : [2,6] [1,3] [15,18] [8,10]
    // 출력 : [1,6] [8,10] [15,18]
    public static ArrayList<int[]> solution(int[][] intervals) {
        sort(intervals);        // 첫번째 값 기준으로 정렬

        // 구간이 겹치는지 확인 
        ArrayList<int[]> result = new ArrayList<>();    // 구간이 합쳐서 정리된 리스트
        int[] curInterval = intervals[0];
        result.add(curInterval);

        for(int i = 1; i<intervals.length; i++) {
            if(curInterval[1] >= intervals[i][0]) {     // [1,3] [2,6] 3이 2보다 크므로 3을 6으로
                curInterval[1] = intervals[i][1];
            } else {
                curInterval = intervals[i];
                result.add(curInterval);
            }
        }




        return null;
    }

    public static void sort(int[][] intervals) {
        quickSort(intervals, 0, intervals.length-1);
    }
    
    public static void quickSort(int[][] arr, int left, int right) {
        if(left >= right) {
            return;
        }

        int pivot = patition(arr, left, right);
        quickSort(arr, left, pivot-1);
        quickSort(arr, pivot+1, right);
    }

    public static int patition(int[][] arr, int left, int right) {
        int pivot = arr[left][0];
        int pl = left;
        int pr = right;

        while(pl < pr) {
            while(arr[pr][0] > pivot && pl<pr) {
                pr--;
            }
            while(arr[pl][0] <= pivot && pl < pr) {
                pl++;
            }
            swap(arr, pl, pr);
        }
        swap(arr, pl, pr);
        return pl;
    }

    public static void swap(int[][] arr, int i, int j) {
        int[] temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

 

❖ 정렬이 필요한 구간 출력

// 정수 배열 nums가 주어졌을 때
    // 오름차순으로 정렬하기 위해 배열 내에서 정렬이 필요한 구간의 길이를 출력하는 프로그램

    // 입력 : 2 6 4 8 5 3 9 10
    // 출력 : 5

    // 좌측 시작지점은 가장 오른쪽에있는 작은 값(3)을 기준으로 
    // 왼쪽에 기준보다 큰 수들이 있는데 기준보다 작아지면 그 전부터 시작지점
    // 우측 끝나는지점은 시작지점은 가장 오른쪽에 있는 작은 값보다 시작지점 사이에서 가장 큰 값을 기준으로 기준보다 더 큼
    public static int solution(int[] nums) {
        int min = Integer.MAX_VALUE;
        int firstIdx = 0;

        for(int i = nums.length-1; i>=0;i--) {
            min = Math.min(min, nums[i]);
            if(nums[i] > min) {
                firstIdx = i;
            }
        }

        int max = Integer.MIN_VALUE;
        int lastIdx = 0;
        for(int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            if(nums[i] < max) {
                lastIdx = i;
            }
        }
        return lastIdx - firstIdx +1;
    }