자료구조 :: JAVA를 이용한 퀵 정렬, Quick Sort, 퀵 소트 (JAVA 구현)

퀵 소트 Quick sort

 

이론적인 내용이 궁금하면 아래 글을 참고 할 것

2018/04/28 - [Algorithm] - 자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)

 

JAVA를 이용하여 퀵소트를 구현해보자

 

Pivot을 데이터의 맨 처음 값으로 한 경우

public class Quick {

    private static int number = 11;
    private static int[] data;
    private static int cnt = 0; // quick_sort 호출 횟수

    public static void quick_sort(int[] data, int x, int y) {
        cnt++; 
        
        if (x >= y) {
            // 원소가 1개인 경우
            return;
        }
        
        int pivot = x;
        int left = pivot + 1;
        int right = y;
        int temp;

        while (left < right) {
            while (left <= y && data[left] < data[pivot]) {
                left++;
            }
            while (right >= pivot && data[pivot] < data[right]) {
                right--;
            }

            if (left < right) {
                temp = data[left];
                data[left] = data[right];
                data[right] = temp;
            } else {
                temp = data[pivot];
                data[pivot] = data[right];
                data[right] = temp;
            }

            quick_sort(data, x, right - 1);
            quick_sort(data, right + 1, y);

        }
    }

    public static void printData(int[] data, int number) {
        for (int i = 0; i < number; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {

        // 1~100 랜덤한 값 출력
        data = new int[number];
        for (int i = 0; i < number; i++) {
            data[i] = (int) (Math.random() * 100);
        }

        // 정렬 전
        printData(data, number);

        // 정렬 시작
        quick_sort(data, 0, number - 1);

        // 정렬 후
        printData(data, number);
        
        // 연산 횟수
        System.out.println("N : " + number + " / cnt : " + cnt);
    }
}​

 

결과 확인

 

관련 글

2018/04/28 - [Algorithm] - 자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)

자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)