공부/알고리즘

정렬 - K번째 수 (프로그래머스) - 완료

오피스엑소더스 2019. 5. 15. 17:10

https://programmers.co.kr/learn/courses/30/lessons/42748


2019-05-15 성공! 포인트 5점 획득! :D




내 코드

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
package lvl_one;
 
public class KthInteger {
 
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int a = 0, b = 0, c = 0, i = 0, j = 0;
        int[] arr;
        for (i = 0; i < commands.length; i++) {
            a = commands[i][0];
            b = commands[i][1];
            c = commands[i][2];
            arr = new int[b - a + 1];
            for (j = 0; j < arr.length; j++) {
                arr[j] = array[(a++) - 1];
            }
            quickSort(arr, 0, arr.length - 1);
            answer[i] = arr[c - 1];
        }
        return answer;
    }
 
    public static int partition(int arr[], int left, int right) {
 
        int pivot = arr[(left + right) / 2];
 
        while (left < right) {
            while ((arr[left] < pivot) && (left < right))
                left++;
            while ((arr[right] > pivot) && (left < right))
                right--;
 
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
 
        return left;
    }
 
    public static void quickSort(int arr[], int left, int right) {
 
        if (left < right) {
            int pivotNewIndex = partition(arr, left, right);
 
            quickSort(arr, left, pivotNewIndex - 1);
            quickSort(arr, pivotNewIndex + 1, right);
        }
 
    }
}
cs


퀵정렬 코드 출처 : https://www.baeldung.com/java-quicksort


내림차순 퀵 정렬!

6번, 8번에 pivot 앞 부등호 방향만 바꿔주면 오름차순-내림차순 스왑

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
public static int partition(int arr[], int left, int right) {
         
    int pivot = arr[(left + right) / 2];
 
    while (left < right) {
        while ((arr[left] > pivot) && (left < right))//요기 arr[left] > pivot
            left++;
        while ((arr[right] < pivot) && (left < right))//요기 arr[right] < pivot] 
            right--;                                //두개 부등호만 바꿔주면 오름차-내림차
         if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
   return left;
}
 
public static void quickSort(int arr[], int left, int right) {
 
    if (left < right) {
        int pivotNewIndex = partition(arr, left, right);
 
        quickSort(arr, left, pivotNewIndex - 1);
        quickSort(arr, pivotNewIndex + 1, right);
    }
 
}
cs



#퀵소트 #퀵정렬 #QuickSort #quicksort



맨 위로