정렬 알고리즘 정리 - 3

황제연·2024년 7월 6일

자바 정렬 정렬알고리즘 퀵정렬

알고리즘

목록 보기

50/169

정렬 알고리즘 정리

백준 사다리 문제에서 다뤘던 삽입정렬과 버블 정렬을 제외하고
나머지 정렬 알고리즘에 대해 정리하고 직접 구현해보려고 한다

퀵정렬

퀵 정렬은 벗을 하나 두고 두개의 부분리스트로 나누어서 정렬하는 방식이다
피벗의 왼쪽에는 피벗보다 작은 값들이 있고 오른쪽은 피벗보다 큰 값들이 존재한다
이 방식으로 재귀적으로 수행하여 정렬하는 것이 퀵 정렬이다

퀵 정렬 피벗 위치

퀵정렬은 피벗을 왼쪽, 가운데, 오른쪽 중 하나에 두고 정렬을 할 수 있다
각 방식에 따라 방식이 조금씩 달라진다.

public class QuickSort{
        private static void leftPivotQuickSort(int[] arr, int low, int high){
            if(low >= high){
                return;
            }

            int pivot = leftPartitioning(arr, low, high);

            leftPivotQuickSort(arr, low, pivot-1);
            leftPivotQuickSort(arr, pivot+1, high);
        }


        private static void rightPivotQuickSort(int[] arr, int low, int high){
            if(low >= high){
                return;
            }
            int pivot = rightPartitioning(arr, low, high);
            rightPivotQuickSort(arr, low, pivot -1);
            rightPivotQuickSort(arr, pivot+1, high);
        }

        private static void centerPivotQuickSort(int[] arr, int low, int high){
            if(low >= high){
                return;
            }

            int pivot = centerPartitioning(arr, low, high);
            centerPivotQuickSort(arr, low, pivot);
            centerPivotQuickSort(arr, pivot+1, high);
        }
        private static int centerPartitioning(int[] arr, int left, int right){
            int low = left -1;
            int high = right + 1;
            int pivot = arr[(left + right) / 2];

            while(true){

                do{
                    low++;
                }while(arr[low] < pivot);


                do{
                    high--;
                }while(arr[high] > pivot && low <= high);

                if(low >= high){
                    return high;
                }

                swap(arr, low, high);
            }


        }


        private static int leftPartitioning(int[] arr, int left, int right){
            int low = left;
            int high = right;
            int pivot = arr[left];

            while(low < high){
                while(arr[high] > pivot && low < high){
                    high--;
                }

                while(arr[low] <= pivot && low < high){
                    low++;
                }

                swap(arr, low, high);
            }
            swap(arr, left, low);
            return low;
        }

        private static int rightPartitioning(int[] arr, int left, int right){
            int low = left;
            int high = right;
            int pivot = arr[right];

            while(low < high){
                while(arr[low] < pivot && low < high){
                    low++;
                }

                while(arr[high] >= pivot && low < high){
                    high--;
                }

                swap(arr, low, high);
            }
            swap(arr, right, high);
            return high;
        }




        private static void swap(int[] arr, int i, int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

    }

위 코드는 피벗을 왼쪽, 오른쪽, 가운데에 넣고 정렬하는 코드이다

왼쪽/오른쪽 기준의 경우

왼쪽과 오른쪽은 비슷하다
1 . 피벗을 하나 선택하고, low에는 왼쪽, high에는 오른쪽 위치를 넣어준다
2 . 공통적으로 low가 high보다 작아야하고 (엇갈리거나 만나지 않아야하고),
pivot보다 low 위치에 있는 값이 작다면 low를 증가시킨다
3 . 이어서 pivot보다 high 위치에 있는 값이 크거나 같다면 high를 감소시킨다
4 . 위 과정이 끝나면 low와 high를 바꿔준다.
5 . 이것을 low가 high보다 작은동안 반복하며,
모두 끝난 뒤에는 left와 low 또는 right와 high를 swap하고 각각 low와 high를 pivot으로 리턴한다
6 . pivot을 기준으로 다시 분할하여 왼쪽과 오른쪽에 대해 재귀적으로 다시 정렬한다