정렬 알고리즘 / 삽입 / 퀵 / 듀얼 피벗

 

 

시작은 

 

틀려서 시작한 포스팅이다.

 

 

 

 

테스트 케이스는 통과하는 데, 반례가 뭔지 모르겠다

 

하지만,

 

정답을 푼 사람들의 답은 아주 간결했다. 

   Arrays.sort(vv1, new Comparator<T>() {
                        @Override
                        public int compare(T o1, T o2) {
                            return 0;
                        }
                    });

이 부분이 포인트. 

 

Arrays.sort 는 기본적으로 오름차순이지만, 아니라면 

 

오버라이드를 통해 정렬 기준을 정해준다. 

 

시간초과가 뜬 실패한 코드와 달리, 장황하게 for문을 안돌려도 된다.

내부적으로 Arrays.sort 가 처리하고 있겠지라고 생각해서 들어가 봤다.

 

듀얼 피벗 퀵 소트를 공부해야 한다.

왜 이거 쓰는지 궁금한 사람이 또 있었다.

 

OKKY | 자바의 Arrays.sort는 왜 Dual-Pivot Quicksort를 사용하나요?

 

 

 

 

정렬의 종류는 참 많다. 

 

 

듀얼피벗퀵솟이 제일 빠르다.

 

 

삽입 정렬 + 퀵 정렬???

 

 

 

삽입 정렬은 단순하지만 비효율적인 방법이라고 한다. 

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog

 

 

 

레코드 수가 적을경우에 효과적인 정렬이다.

-> 레코드 수가 많고 크기가 클 경우에는 비교적 많은 레코드들의 이동이 있기 때문이다.

 

✍ array[1] 번 부터 끝까지 도는 반복문이 있고,

✍ 그 반복문 내부에서 선택한 순번을 앞선 순번 모두와 비교하는 반복문이 들어간다. 

 

 // 1 번 부터 시작.
 for (int i = 1; i < arrays.length; i++) {
    // 앞선 순번들의 숫자들과 비교.
    for (int j = i; j >= 0; j--) {
      // 앞선 숫자가 더 크다면,
      if (arrays[j + 1] < arrays[j]) {
      	// 순서를 바꿔준다.
        int temp = arrays[j+1];
      	arrays[j+1] = arrays[j];
        arrays[j] = temp;

 

 

 

퀵 정렬은 구현이 정말 다양하다고 한다. 

그렇지만 메커니즘은 크게 다음과 같다.

 

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트,

 

 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법이다.

 

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

//중간값을 구하는 것이 핵심.
int pivot = arr[(start+end)/2];
while(start <= end){
    while(arr[start] < pivot)
        start++;
    while(arr[end] > pivot)
        end--;
    if(start <= end){
        swap(arr, start, end);
        start++;
        end--;
    }
}


public static void quickSort(Integer[] arr, int left, int right) {
        int mid = (left + right) / 2;
        int pivot, i, j;
        threeSort(arr, left, right, mid);
        if (right - left + 1 > 3) {
            pivot = arr[mid];
            swap(arr, mid, right - 1);
            i = left;
            j = right - 1;
            //System.out.println("pivot = " + pivot);
            while (true) {
                while (arr[++i] < pivot);
                while (arr[--j] > pivot);
                if (i >= j) {
                    break;
                }
                swap(arr, i, j);
            }
            swap(arr, i, right - 1);
            //System.out.println("arr = " + Arrays.deepToString(arr) + ", left = " + left + ", right = " + right);
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }


    public static void threeSort(Integer[] arr, int left, int right, int mid) {
        if (arr[left] >= arr[mid]) swap(arr, left, mid);
        if (arr[left] >= arr[right]) swap(arr, left, right);
        if (arr[mid] >= arr[right]) swap(arr, mid, right);
    }

 

테스트하다 스택오버플로 에러 봤음.. 잘못된 재귀호출

피벗 잡고 기준으로 왼쪽은 작은거 오른쪽은 큰거 반복...

 

 

 

 

Dual-Pivot Quicksort   피벗 2개 선택해서 3개의 구역으로 나눈다 정도의 차이가 있다. 

 

 

효율은 차이가 크네