으아아앜
1k
2019-06-21 04:47:18
3
419

퀵정렬....? 제가 원리를 잘못 이해한건가요??? (코드 살짝만봐주세요 ㅠ_ㅠ)



class Solution {
    
    public void swap(int[] array, int index1, int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
    
    public void quickSort(int[] array,int _low, int _high){
        int pivo = (_low+_high)/2;
        int low=_low;
        int high=_high;
        
        while(low<high){
            while(array[low]<array[pivo]){ 
                low++;
            }
            while(array[high]>array[pivo]){
                high--;
            }
            if(low<high){ 
                swap(array,low,high);    
                if(pivo==high){
                    pivo = low;
                }else if(pivo==low){
                    pivo =high;
                }
                
            }
        }
        for(int n=0; n<array.length; n++){
            System.out.print(array[n] + " ");
        }


        if(_low<=(pivo-1)){
            quickSort(array, _low, pivo-1);
        }
        if((pivo+1)<_high){
            quickSort(array, pivo+1, _high);         
        }
        
        
        
    }
    
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        int[] temp = {1,3,2,8,5,6,7,4,2,4,6,8,9,2,5,6,6};
        
        for(int n=0; n<temp.length; n++){
            System.out.print(temp[n] + " ");
        }
        System.out.println();
        quickSort(temp, 0, temp.length-1);
        
        return answer;
    }
}


프로그래머스에서 작성하던 코드를 그대로 복붙한점 양해바랍니다. ㅠ

일단 질문을 올리게 된 이유는, 제가 작성한 퀵정렬은 시간복잡도가 좋지 않은듯 합니다.

다른 블로그의 예제에서는 수행할 수 있던 20크기의 배열을 제 퀵정렬은 타임아웃되서 수행하지 못하더라구요......



제 나름대로 퀵정렬 원리를 이해하고, 거의 베끼지 않고 작성한 코드입니다.

제 코드의 어떤 부분이 퀵정렬을 망치고 있는지 보이시는 분 계신가요....? ㅠㅠㅠㅠㅠ


0
  • 답변 3

  • moonti
    3k
    2019-06-21 06:01:11

    퀵정렬인지 모르겟는걸요??

    더 더 단순한 로직인데요..

    수도코드 보시고 비교해보세요~

  • 쿵따리쿵쿵따
    270
    2019-06-21 06:23:37 작성 2019-06-21 06:25:06 수정됨

    퀵정렬 실행은 잘 되나요??? 정렬 자체가 안될거같은데

  • rezigrene
    1k
    2019-06-21 10:09:19

    {3,3,3} 을 정렬해보세요.

  • 로그인을 하시면 답변 을 등록할 수 있습니다.