백준 2750번 Quick Sort(퀵 정렬) 자바로 구현하기

알고리즘 도감 앱으로 플로우 익히고 막히는 곳만 대충 찾아가면서 구현했다.

‎알고리즘 도감

‎보면서 이해하고 실행해서 즐거운 알고리즘 도감입니다. 다양한 분야의 알고리즘을 애니메이션으로 친절하게 설명. 여러 가지 시도를 할 수 있는 '실험 모드'로 깊이 있는 이해가 가능합니다. 암호화, 보안 등 실용적인 알고리즘도 다루고 있습니다. ==== 카테고리와 게재 항목 ==== [ 정렬 ] 버블 정렬, 선택 정렬, 삽입 정렬, 힙(heap) 정렬, 병합 정렬, 퀵 정렬 [ 클러스터링 ] k-means법 [ 리스트 탐색 ] 선형 탐색, 이분 탐색 [ 그래프 탐색 ] 너비 우선 탐색, 깊이 우선 탐색, 벨만-…

itunes.apple.com

 

중복도 되는지 테스트해보려다가 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 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

public class No2750_QuickSort {          public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int N = Integer.parseInt(br.readLine());         int[] numArr = new int[N];                  for (int i = 0; i < N; i++) {             numArr[i] = Integer.parseInt(br.readLine());         }           findSorting(numArr, 0, N - 1);                  IntStream stream = Arrays.stream(numArr);         stream.forEach(System.out::println);     }       public static void findSorting(int numArr[], int left, int right) {         if (left < right) {             int p = sort(numArr, left, right);             findSorting(numArr, left, p - 1);             findSorting(numArr, p + 1, right);         }     }       public static int sort(int numArr[], int left, int right) {           int pivot = (left + right) / 2; // 랜덤 값 pivot에 대입                  // left 탐색         while (left < right && numArr[pivot] > numArr[left]) {             left++;         }           // right 탐색         while (left < right && numArr[pivot] <= numArr[right]) {             right--;         }           // arr[left] > arr[pivot] && arr[right] < arr[pivot] && left != right         if (left < right && numArr[left] > numArr[right]) {                          swap(numArr, left, right);             if (left == pivot) { // pivot이 옮겨질 경우, 처음부터 재탐색                 sort(numArr, 0, numArr.length - 1);             } else {                 sort(numArr, left, right);             }         }           if (left == right) {             swap(numArr, left, pivot);         }           return left;       }       public static void swap(int numArr[], int a, int b) {         int swap = numArr[a];         numArr[a] = numArr[b];         numArr[b] = swap;     } } Colored by Color Scripter

cs