글 읽기 - 퀵소트 질문있습니다.

dlwodls10 2년 전 0

다른 질문글들을 읽어보니 시간초과가 나는건 퀵소트 특성상 어쩔 수 없다는건 알겠는데 저는 왜 그냥 틀렸다고 나오는지 모르겠습니다.

퀵소트 코드가 이상한걸까요? 저 혼자서는 문제를 못찾겠습니다.

그리고 가능하다면 재귀함수는 디버깅을 어떻게 해야하는지까지 알려주시면 감사하겠습니다.

퀵소트 개념은 이미 진작에 이해했음에도 불구하고 재귀함수 부분때문에 구글링해서 베껴온 이 코드가 제대로 돌아가는 코드인지는 파악이 잘 안됩니다. 재귀함수 문제 자체도 풀다가 때려친게 많고요.

어떻게 봐야 하는건가요?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void quick_sort(vector<int>&, int, int);

int main(int argc, const char * argv[]) {
  
    int n;
    cin >> n;
    vector<int> input;
    input.reserve(n);
    
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        input.push_back(temp);
    }
    
    quick_sort(input, 0, n - 1);
    
    for_each(input.begin(), input.end(), [](int i)->void{ cout << i << '\n'; });
    
    return 0;
}


void quick_sort(vector<int>& input, int first_index, int last_index) {
    
    if (first_index >= last_index) return;      //인덱스 두개가 같거나 순서가 바뀌었다는건 더이상 정렬할 원소가 없다는 뜻이므로 종료한다.
    
    int pivot_index = (last_index + first_index) / 2;
    int low_index = first_index;
    int high_index = last_index;
    
    while (low_index <= high_index) {   //로우인덱스가 하이인덱스를 따라잡거나 같아질때까지 반복한다.
        
        //피봇값보다 큰 로우값이 나올때까지 로우인덱스를 뒤로 넘긴다.
        while (input[pivot_index] > input[low_index]) low_index++;
        
        //피봇값보다 작은 하이값이 나올때까지 하이인덱스를 앞으로 넘긴다.
        while (input[pivot_index] < input[high_index]) high_index--;
        
        //로우값과 하이값을 바꾼다.
        if (low_index <= high_index) {
            int temp = input[low_index];
            input[low_index] = input[high_index];
            input[high_index] = temp;
            
            high_index--;
            low_index++;
        }
    }
    quick_sort(input,  first_index, high_index);
    quick_sort(input, low_index, last_index);
}

zigui 2년 전 1

제 생각에는 41, 44번째 줄에서 값을 비교할 때 매번 배열 값을 참조하는 대신, 34번째 줄에서 배열의 값을 저장하여 그 값으로 비교를 하는 것이 올바른 것 같습니다.

배열값을 조작하는 과정에서 배열의 값이 바껴 코드가 원하는 대로 동작하지 않을 수 있습니다.

dlwodls10 2년 전 0

@zigui 셔플만 앞에 덧붙이고 말해주신대로 했더니 바로 통과되네요! 감사합니다!

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <random>

using namespace std;

void quick_sort(vector<int>&, int, int);

int main(int argc, const char * argv[]) {
  
    vector<int> input;
    int n;
    cin >> n;
    input.reserve(n);
    
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        input.push_back(temp);
    }
    
    mt19937 seed;       //난수생성용 시드.
    
    shuffle(input.begin(), input.end(), seed);
    
    quick_sort(input, 0, n - 1);
    
    for_each(input.begin(), input.end(), [](int i)->void{ cout << i << '\n'; });
    
    return 0;
}



//10
//10 1 11 100 2 5 7 19 10000 113


void quick_sort(vector<int>& input, int first_index, int last_index) {
    
    if (first_index >= last_index) return;      //인덱스 두개가 같거나 순서가 바뀌었다는건 더이상 정렬할 원소가 없다는 뜻이므로 종료한다.
    
    int pivot_value = input[(last_index + first_index) / 2];
    int low_index = first_index;
    int high_index = last_index;
    
    while (low_index <= high_index) {   //로우인덱스가 하이인덱스를 따라잡거나 같아질때까지 반복한다.
        
        //피봇값보다 큰 로우값이 나올때까지 로우인덱스를 뒤로 넘긴다.
        while (pivot_value > input[low_index]) low_index++;
        
        //피봇값보다 작은 하이값이 나올때까지 하이인덱스를 앞으로 넘긴다.
        while (pivot_value < input[high_index]) high_index--;
        
        //로우값과 하이값을 바꾼다.
        if (low_index <= high_index) {
            int temp = input[low_index];
            input[low_index] = input[high_index];
            input[high_index] = temp;
            
            high_index--;
            low_index++;
        }
    }
    quick_sort(input,  first_index, high_index);
    quick_sort(input, low_index, last_index);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

퀵소트 질문있습니다.

dlwodls10 2년 전 0

zigui 2년 전 1

dlwodls10 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말