Sort/Sort.txt at main · hgfdsa4320/Sort · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
import java.util.*;

interface SortMethods{ //정렬 방법
    void bubbleSort(int[] x,int n);
    void selectionSort(int[] x,int n);
    void insertionSort(int[] x,int n);
    void shellSort(int[] x,int n);
}
interface SortDegree{ //정렬 정도
    void random(int[] x,int n); //랜덤
    void descendingSort(int[] x,int n); //내림차순 정렬
    void almostSort(int[] x,int n); //거의 정렬이 되어있는 상태
}
class Sort implements SortMethods,SortDegree {
    static void swap(int[] x, int a, int b) {
        int t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

    @Override
    public void bubbleSort(int[] x, int n) {
        for (int i = 1; i < n; i++)
            for (int j = 0; j < n - i; j++)
                if (x[j] > x[j + 1])
                    swap(x, j, j + 1);
    }

    @Override
    public void selectionSort(int[] x, int n) {
        int min;
        for (int i = 0; i < n - 1; i++) {
            min = x[i];
            int k=i;
            for (int j = i + 1; j < n; j++)
                if (x[j] < min)
                  k=j;
            swap(x,i,k);
        }
    }

    @Override
    public void insertionSort(int[] x, int n) {
        int k;
        int j;
        for(int i=1;i<n;i++){
            k=x[i];
            j=i-1;
            while(j>=0&&x[j]>k){
                x[j+1]=x[j];
                j=j-1;
            }
            x[j+1]=k;
        }
    }

    @Override
    public void shellSort(int[] x, int n) {
        int k,j;
        for(int h=n/2;h>0;h/=2) {
            for (int i=h;i<n;i++){
                k=x[i];
                j=i;
                while(j>=h&&x[j-h]>k){
                    x[j]=x[j-h];
                    j=j-h;
                }
                x[j]=k;
            }
        }
    }
    public void time(int[] x,int n,String s1,String s2){
        double beforeTime = System.currentTimeMillis();
        bubbleSort(x,n);
        double afterTime = System.currentTimeMillis();
        double secDiffTime = (afterTime - beforeTime) / 1000;
        System.out.println(s1+"정렬에서의 "+s2+"시간:"+secDiffTime);

    }

    @Override
    public void random(int[] x,int n) {
        Random r=new Random();
        for(int i=0;i<x.length;i++)
            x[i]=r.nextInt(100)+1;
        time(x,n,"랜덤","bubbleSort");
        time(x,n,"랜덤","selectionSort");
        time(x,n,"랜덤","insertionSort");
        time(x,n,"랜덤","shellSort");

    }


    @Override
    public void descendingSort(int[] x,int n) {
        Arrays.sort(x);
        int[] k=x.clone();
        for(int i=0;i<x.length;i++)
            x[i]=k[n-i-1];
        time(x,n,"내림차순","bubbleSort");
        time(x,n,"내림차순","selectionSort");
        time(x,n,"내림차순","insertionSort");
        time(x,n,"내림차순","shellSort");
    }

    @Override
    public void almostSort(int[] x,int n) {
        Arrays.sort(x);
        for(int i=0;i<x.length/50;i++)
            swap(x,i+20,x.length-i-1);
        time(x,n,"대부분","bubbleSort");
        time(x,n,"대부분","selectionSort");
        time(x,n,"대부분","insertionSort");
        time(x,n,"대부분","shellSort");
    }

}
public class SortAlgorithm{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);

        Sort s=new Sort();
        int n=sc.nextInt();
        int[] x=new int[n];
        s.random(x,n);
        s.descendingSort(x,n);
        s.almostSort(x,n);

    }
}