알고리즘) Shell/Radix Sort (셸/기수 정렬)

Shell Sort (셸 정렬)

https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html

일정간격으로 부분집합을 구성하고, 각 부분집합에 대해 삽입정렬을 수행.
간격을 줄여가며 반복.

• 부분집합을 만드는 기준이 되는 간격 값에 따라 성능 좌우
• 일반적으로 시간 복잡도는 O(n1.25~1.5)로 측정
• 삽입정렬보다는 개선된 방법

import java.lang.Math;
        import java.util.Scanner;;

public class Test {

    public static void printArray(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.printf("%2d ", arr[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        System.out.print("before Sort: ");
        printArray(arr);

        shellSort(arr, n);

        System.out.print("after Sort: ");
        printArray(arr);
    }

    public static void shellSort(int arr[], int size) {
        int interval = size/2;
        while (interval>=1) {
            for(int i=0; i<interval; i++) {
                interval_insertionSort(arr, i, size-1, interval);
            }
            interval /= 2;
        }
    }

    public static void interval_insertionSort(int[] arr, int left, int right, int interval) {
        int i, k, data;
        for(i=left+interval ; i<=right ; i+=interval) {
            data = arr[i];
            for(k=i-interval ; k>=left && data<arr[k] ; k-=interval) {
                arr[k+interval] = arr[k];
            }
            arr[k+interval] = data;
            printArray(arr);
        }
    }


}

---

Radix Sort (기수 정렬)

http://lktprogrammer.tistory.com/48

원소의 키를 표현하는 값의 기수(radix, 10진수의 경우 0~9까지 10개)개의 Bucket(큐, 배열 ..)을 준비한 뒤,
각 버킷에 원소를 분배했다가 버킷 순서대로 원소를 다시 꺼내는 과정을
키값의 자리수만큼(최대 십의자리라면 2번) 반복한다.

• 시간 복잡도 : O(dn) (d : 가장 큰 데이터의 자리수)

import java.lang.Math;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;;

public class Test {

    public static void printArray(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.printf("%2d ", arr[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        System.out.print("before Sort: ");
        printArray(arr);

        radixSort(arr);

        System.out.print("after Sort: ");
        printArray(arr);
    }

    public static void radixSort(int arr[]) {
        int maxSize = getMaxSize(arr); // 가장 큰 자리수
        ArrayList<Queue> bucket = new ArrayList<>();
        int powed = 1;

        for(int i=0; i<10; i++) { // bucket 생성
            bucket.add(new LinkedList());
        }

        for(int i=0; i<maxSize; i++) { // max자리수 만큼 전체 반복문 반복
            for(int k=0; k<arr.length; k++) { // 각 자리수에 맞는 index의 bucket에 넣는다
                bucket.get((arr[k]/powed)%10).offer(arr[k]);
            }
            for(int m=0, bucketNum=0; m<arr.length; ) { // 다시 bucket에서 빼온다
                while(!bucket.get(bucketNum).isEmpty()) {
                    arr[m++] = (int)bucket.get(bucketNum).poll();
                }
                bucketNum++;
            }
            powed *= 10;
            printArray(arr);
        }
    }

    public static int getMaxSize(int[] arr) {
        int maxSize = 0;
        for(int i=0; i<arr.length; i++) {
            int tmp = (int) Math.log10(arr[i]) + 1;
            if(tmp > maxSize)
                maxSize = tmp;
        }
        return maxSize;
    }

}