quick sort를 짜봤는데 중복 문제 해결에 대해 궁금한점이 있습니다.

  • wardn
    wardn

    quick sort를 알고리즘만 보고 C언어로 구현해봤는데

    중복된 수가 있을때 첫 while문에서 무한 루프를 돌더라구요

    그래서 첫 while 문에서 조건을 걸어주니까 제 기능을 못하고..

    여러 방법을 써봤는데 시원스레 해결이 안나서 질문 올립니다.

    제가 짠 코드에서 로직상 문제나 비효율적인 점은 없는지..

    그리고 중복 문제 해결을 위해서 어떤걸 수정하면 좋을지

    알려주시면 감사하겠습니다!

    void quicksort(int array[], int left, int right, int len)
    {
        int key_left = left;
        int key_right = right;
        int pivot = array[left];
        int i, j;
    
        ++count;
        //printf("퀵소트 %d번째 : ", count);
    
        while (left < right)
        {
            while (array[left] < pivot)
                left++;
    
            while (array[right] > pivot)
                right--;
    
            if (left < right)
                swap(&array[left], &array[right]);
            else
                swap(&array[right], &pivot);
        }
        /*
        for (i = 0; i < len; i++)
            printf("%d ", array[i]);
        printf("\n");
        */
        pivot = right;
        left = key_left;
        right = key_right;
    
        if (left < pivot - 1)
            quicksort(array, left, pivot - 1, len);
        if (right > pivot + 1)
            quicksort(array, pivot + 1, right, len);
    }
    

    8년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.