반응형
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
public class Main {
    public static void printArray(int[] a) {
        for(int i = 0; i < a.length; i++){
            System.out.println(a[i]);
        }
    }
    
    public static int divideArray(int[] a, int head, int tail) {
        int left, right, temp;
        left = head + 1;
        right = tail;
        
        while(true) {
            while(left < tail && a[head] > a[left]) {
                left++;
            }
            
            while(a[head] < a[right]) {
                right--;
            }
            
            if(left >= right) {
                break;
            }
            
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            
            left++;
            right--;
            
        }
        temp = a[head];
        a[head] = a[right];
        a[right] = temp;
        
        return right;
        
    }
    
    public static void sortArray(int[] a, int start, int end) {
        int pivot;
        
        if(start < end) {
            pivot = divideArray(a, start, end);
            
            sortArray(a, start, pivot - 1);
            
            sortArray(a, pivot + 1, end);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] a = new int[n];
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        //printArray(a);
        
        sortArray(a, 0, a.length - 1);
        
        printArray(a);
        
    }
}
cs

O(nlogn)의 속도가 평균적이고, 최악에는 O(n^2)의 시간복잡도가 나오기도 한다.

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm 이론' 카테고리의 다른 글

LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08
이진 탐색  (0) 2023.01.07

+ Recent posts

티스토리툴바