자바 퀵 정렬 질문입니다!

본문 바로가기

자바 퀵 정렬 질문입니다!

작성일 2020.01.08댓글 1건
    게시물 수정 , 삭제는 로그인 필요

public class QuickSort {
    static int partition(int[] list, int left, int right){

        int pivot, temp, low, high;
        low = left;
        high = right + 1;
        pivot = list[left];

       do{
           do{
               low++;   //인덱스 범위를 넘어가는 에러 
               System.out.println(low);
           }while(pivot > list[low]);

           do{
               high--;
           }while(pivot < list[high]);

           if(low < high){
               temp = list[low];
               list[low] = list[high];
               list[high] = temp;
           }
       }while(low < high);

       temp = list[left];
       list[left] = list[high];
       list[high] = temp;

       return high;
    }

    static void quick_sort(int[] list, int left, int right){
        if(left < right){
            int q = partition(list, left, right);
            quick_sort(list, left,q - 1);
            quick_sort(list,q + 1, right);
        }
    }

    public static void main(String[] args){
        int[] list = {5,3,8,4,9,1,6,2,7};
        quick_sort(list,0,list.length-1);

        for(int i=0; i<list.length; i++){
            System.out.print(list[i] + " ");
        }

    }
}

퀵 정렬 질문입니다! 
C언어로 구현된 것을 보고 자바로 똑같이 구현을 해보았습니다. 근데 partition 메소드 안에 low++ 부분에서 배열의 크기는 0~8인데 low가 9가 되버려서 에러가 발생하는데 C에서는 돌아가는 코드인데 자바에서는 안되는데 어떤 걸 제가 잘 모르고 있는지 모르겠어서 질문드립니다 ㅜㅜ 

자바와 C언어의 어떤 차이가 있어서 똑같이 하면 안되는 걸까요?? 


#자바 퀵정렬 #자바 퀵소트 라이브러리 #자바 퀵정렬 오름차순

profile_image 익명 작성일 -

partition 메소드에서 마지막에 swap하는 부분에 변수가 잘못되었습니다.

​

수정전

temp = list[left]; // left -> low list[left] = list[high]; // left -> low list[high] = temp;

수정후

temp = list[low]; list[low] = list[high]; list[high] = temp;

이렇게 수정하면 에러는 발생하지 않지만 정렬 또한 정확하게 되진 않네요.

​

정확하게 동작하는 소스도 같이 첨부드립니다.

​

import java.util.Arrays; class QuickSort { public static void main(String[] args) { int[] list = {5, 3, 8, 4, 9, 1, 6, 2, 7}; quickSort(list); System.out.println(Arrays.toString(list)); } public static void quickSort(int[] arr) { sort(arr, 0, arr.length - 1); } private static void sort(int[] arr, int low, int high) { if (low >= high) return; int mid = partition(arr, low, high); sort(arr, low, mid - 1); sort(arr, mid, high); } private static int partition(int[] arr, int low, int high) { int pivot = arr[(low + high) / 2]; while (low <= high) { while (arr[low] < pivot) low++; while (arr[high] > pivot) high--; if (low <= high) { swap(arr, low, high); low++; high--; } } return low; } private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }

​

연관된 질문 답변 리스트

자바 퀵 정렬 질문입니다!

... i++){ System.out.print(list[i] + " "); } } } 퀵 정렬 질문입니다! C언어로 구현된 것을 보고 자바로 똑같이 구현을 해보았습니다. 근데...

자바 퀵정렬 구현 질문입니다!

... out.print(list[i] + " ") ; } } } 위처럼 자바로 퀵정렬을 구현했습니다 ㅠㅠ 근데 아래와 같은 에러가 발생하는데 도저히 이유를...

자바 정렬알고리즘 질문

... 자바문법, 자료구조등을 다 배웠으면 그 다음으로 무엇을 배워야 하나요? 1. 퀵 알고리즘이 제일 시간복잡도가 빠른데 업무 시 배열, 클래스 정렬이 필요하면 퀵정렬소스를...

자바 프로그래밍 정렬기능 질문

자바에서 arrays.sort 기능을 이용해 배열을 정렬할 때 어떤 알고리즘을 이용해 수행되나요? Arrays.sort 의 소스를 아래 링크 가면 확인 할수...