글 읽기 - Quick sort 관련 질문입니다

jkpxt14 1년 전 0

첨부한 소스코드로도 통과가 되지 않네요 ㅠ 조언 부탁드립니다..

#include <iostream>

using namespace std;

void swapF(int *a, int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

void quickSort(int arr[], int left_0, int right_0)
{
    if(right_0-left_0==1){
        if(arr[left_0]>arr[right_0]){
            swapF(&arr[left_0], &arr[right_0]);
        }
        return;
    }
    int pivot=arr[(left_0+right_0)/2];
    int left=left_0;
    int right=right_0;
    do{
        while(arr[left]<pivot)
            left++;
        while(arr[right]>pivot)
            right--;
        if(left<right){
            swapF(&arr[left], &arr[right]);
            left++;
            right--;
        }
    } while(left<right);
    if(left_0<right){
        quickSort(arr, left_0, right);
    }
    if(left<right_0){
        quickSort(arr, left, right_0);
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N, arr[1000000];
    cin>>N;
    for(int i=0; i<N; i++){
        cin>>arr[i];
    }
    quickSort(arr, 0, N-1);
    for(int i=0; i<N; i++){
        cout<<arr[i]<<"\n";
    }
}

amsminn 1년 전 0

quick sort는 O(n^2)입니다

fblood53 1년 전 0

퀵소트는 평균 O(NlogN)이고 컴퓨터 연산 특성상 속도가 가장 빠르다지만 최악은 O(N^2) 입니다.

피벗 선택이 잘못되면 망하기 때문이죵 어디서 들었는데 피벗 선택을 대충 하면 최악이 되도록 백준에서 테스트 케이스를 생성한다고 들은것 같습니다.

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

문제

문제

출처

ICPC

Quick sort 관련 질문입니다

jkpxt14 1년 전 0

amsminn 1년 전 0

fblood53 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말