sort.java

/**
 * Created by xynophon on 15.1.17.
 */
import java.util.Random;
import java.util.Scanner;

public class sort {
    public int[] swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        return arr;
    }

    // average time complex O(N^2)
    public void selection_sort(int[] arr){
        for(int i = 0; i < arr.length; i++){
            int min_item = i;
            for(int j = min_item+1; j < arr.length; j++){
                if(arr[min_item] > arr[j])
                    min_item = j;
            }
            swap(arr, min_item, i);
        }
    }

    // best time complexity O(N)
    // average time complexity O(N^2),
    // the fastest O(N^2) sort
    // insertion sort is faster than selection sort
    public void insertion_sort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            int key = arr[i];
            int index;
            for(index = i-1; index >= 0 && key < arr[index]; index--){
                arr[index+1] = arr[index];
            }
            arr[index+1] = key;
        }
    }
    
    // average time complexity O(N^2)
    // worst time complexity O(N^2)
    public void bubble_sort(int[] arr){
        for(int i = arr.length; i > 0; i--){
            for(int j = 0; j < arr.length-1; j++){
                if(arr[j] > arr[j+1])
                    swap(arr, j, j+1);
            }
        }
    }


    // worst time complexity O(N^2)
    // average time complexity O(NlogN)
    // 普段は早い。
    // 最悪の場合はmerge sortyより遅い。
    // 分割する時、複雑
    public void quick_sort(int[] arr, int left, int right){
        if(right <= left)return;
        int pivot = arr[right];
        int l = left-1;
        int r = right;
        while(true){
            while(arr[++l] < pivot);
            while(arr[--r] > pivot && left < r);

            if(l >= r)break;
            swap(arr, l, r);
        }
        swap(arr, l, right);
        quick_sort(arr, left, l-1);
        quick_sort(arr, l, right);
    }

    // mergesort
    // worst time complexity O(N^2)
    // average time complexity O(NlogN)
    // 最悪の場合はquicksortより早い。
    // mergeする時、複雑
    public void mergesort(int[] arr){
        int n = arr.length;
        if(n > 1){
            int l = n/2;
            int r = n-l;
            int[] l_arr = new int[l];
            int[] r_arr = new int[r];
 
            for(int i = 0; i < l; i++){
                l_arr[i] = arr[i];
            }
            for(int i = 0; i < r; i++){
                r_arr[i] = arr[l+i];
            }
 
            mergesort(l_arr);
            mergesort(r_arr);
            merge(l_arr, r_arr, arr);
        }
    }
 
    public void merge(int[] l_arr, int[] r_arr, int[]arr){
        int l = l_arr.length;
        int r = r_arr.length;
        int i = 0, j = 0;
        while(i < l && j < r){
            if(l_arr[i] < r_arr[j]){
                arr[i+j] = l_arr[i++];
            }else{
                arr[i+j] = r_arr[j++];
            }
        }
        if(i >= l){
            for(; j < r; j++){
                arr[i+j] = r_arr[j];
            }
        }else{
            for(; i < l; i++){
                arr[i+j] = l_arr[i];
            }
        }
    }

    public static void main(String args[]){
        Random rn = new Random();
        int[] arr = new int[10];
        for(int i = 0; i < 10; i++) {
            arr[i] = rn.nextInt(30);
            System.out.print(arr[i]+" ");
        }
        System.out.println();

        sort s = new sort();

        System.out.println("1 : insertion_sort");
        System.out.println("2 : selection_sort");
        System.out.println("3 : quick_sort");
        System.out.println("4 : bubble_sort");
        Scanner sc = new Scanner(System.in);
        int select = sc.nextInt();
        switch(select){
            case 1:
                s.insertion_sort(arr);
                System.out.println("insertion_sort");
                break;
            case 2:
                s.selection_sort(arr);
                System.out.println("selection_sort");
                break;
            case 3:
                s.quick_sort(arr, 0, arr.length-1);
                System.out.println("quick_sort");
                break;
            case 4:
                s.bubble_sort(arr);
                System.out.println("bubble_sort");
                break;
        }
        for(int value : arr){
            System.out.print(value+" ");
        }
    }
}