퀵정렬(미완성)

BEHE_LIT·2020년 7월 22일
0

자료구조

목록 보기
12/14

필수개념

분할정복(divide-and-conquer), logN, 재귀

퀵정렬의 기본 재료

pivot
startIndex
endIndex
array

퀵정렬의 컨트롤 로직

swap : startIndex와 endIndex의 위치 맞바꾸기
partition : pivot값 설정 / 조건 만족시 swap함수 호출

의문점

  • pivot값의 위치에 따른 성능?
  • 재귀함수 메커니즘

public class QuickSort {

    void quickSort(int[] arr) {
        //시작위치와 끝나는 위치를 정한 재귀함수 호출
        quickSort(arr, 0, arr.length-1);
    }

    void quickSort(int[] arr, int start, int end) {


        int part2 = partition(arr, start, end);
        //나눈 파티션의 오른쪽과
        if(start < part2 - 1) {
            quickSort(arr, start, part2 -1);
            if(part2 < end) {
                quickSort(arr, part2, end);
            }
        }
    }

    int partition(int[] arr, int start, int end) {
        int pivot = arr[(start + end) / 2]; //배열의 중앙값을 피벗으로 설정
        while (start <= end) { //시작 인덱스(왼쪽 포인터)가 끝 인덱스(오른쪽 포인터)를 초과하는 순간 종료
            while (arr[start] < pivot) start++; //start 포인터가 피봇보다 큰값이 나오면 멈추고, 작은값이면 인덱스가 증가한다.
            while (arr[end] > pivot) end--; // end 포인터가 피봇보다 작은값이 나오면 멈추고, 큰값이면 인덱스가 감소한다.
            if (start<=end) {
                swap (arr, start, end);
                start++;
                end--;
            }
        }
        return start;
    }

    static void swap(int[] arr, int start, int end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }

    static void printArray(int[] arr) {
        for (int data : arr) {
            System.out.print(data + ", ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {1,2,7,4,3,9,8};

        QuickSort q = new QuickSort();
        printArray(arr);
        q.quickSort(arr);
        printArray(arr);

    }

}
profile
방랑자의 현장에 오신걸 환영합니다.

0개의 댓글