글 읽기 - 선생님들 이거 왜 틀렸나요??

ypd04208 1년 전 1

왜 1%에서 틀리는지 모르겠네요.

피봇을 활용한 퀵정렬입니다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    static void quickSort(int [] arr,int left,int right){
        int low = left;
        int high = right;
        int m = sortelem3(arr, low, (low+high)/2, high);
        int x = arr[m];

        swap(arr, m,right-1);
        low++;
        high-=2;

        while(low<=high){
            if(arr[low]<x){
                low++;
            }
            if(arr[high]>x){
                high--;
            }
            if(low<=high){
                swap(arr, low++, high--);
            }
        }

        if(left<high){
            quickSort(arr, left, high);
        }
        if(low<right){
            quickSort(arr, low, right);
        }

    }


    static int sortelem3(int [] arr, int a, int b, int c){
        if(arr[b]<arr[a]){
            swap(arr, b, a);
        }
        if(arr[b]>arr[c]){
            swap(arr, b, c);
        }
        if(arr[b]<arr[a]){
            swap(arr, b, a);
        }

        return b;
    }

    static void swap(int [] arr, int front, int rear){
        int tmp = arr[front];
        arr[front] = arr[rear];
        arr[rear] = tmp;
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int [] arr = new int [N];

        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        quickSort(arr, 0, arr.length-1);

        for(int i=0;i<N;i++){
            if(i==N-1){
                bw.write(arr[i]+"");
                break;
            }
            bw.write(arr[i]+"\n");
        }
        bw.flush();

    }
}

wjm7721 1년 전 1

https://www.acmicpc.net/blog/v...

직접 구현한 QuickSort는

피벗을 랜덤으로 잡지 않은 경우

O(N^2)라고 합니다.

ypd04208 1년 전 0

앗 답변 감사합니다!!

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

문제

문제

출처

ICPC

선생님들 이거 왜 틀렸나요??

ypd04208 1년 전 1

wjm7721 1년 전 1

ypd04208 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말