신규 블로그를 만들었습니다!

2020년 이후부터는 아래 블로그에서 활동합니다.

댓글로 질문 주셔도 확인하기 어려울 수 있습니다.

>> https://bluemiv.tistory.com/

퀵 소트 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++ 구현)

퀵 정렬 (Quick sort) 특정한 값(Pivot)을 기준으로 큰 숫자와 작은 숫자를 구분하자 '분할 정복' 알고리즘으로 평균속도가 O(N * logN) 이다. 퀵정렬에는 기준이 되는 값이 존재한다. 이때, 기준값을 피봇(pivot)..

hongku.tistory.com

 

  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기