글 읽기 - 1517번 버블 소트 질문

lyradortiz913 3년 전 0

주먹구구식 계산을 통해서 버블소트가 제한 시간 내에 해결이 불가능함을 알았고,

병합 정렬을 이용해서 코드를 작성해보았는데, 어디가 문제인지 모르겠습니다.ㅠ 도와주세요..

#include <iostream>
#include <vector>

using namespace std;
int n;
long long numOfSwap = 0;

vector<int> seq;
vector<int> seq2;

void merge(int left, int right){
    int mid = (left+right) / 2;

    int i = left;
    int j = mid + 1;
    int k = left;
    while(i <= mid && j <= right){
        if(seq[i] <= seq[j]){
            seq2[k++] = seq[i++];
        } else {
            seq2[k++] = seq[j++];
            numOfSwap += (long long) (mid + 1 - left);
        }
    }

    int temp;
    if(i < mid) temp = i;
    else temp = j;

    while(k <= right) seq2[k++] = seq[temp++];

    for(int i = left; i <= right; ++i) seq[i] = seq2[i];
}

void mergeSort(int left, int right){
    int mid = (left+right)/2;
    if(left < right){
        mergeSort(left,mid);
        mergeSort(mid+1, right);
        merge(left,right);
    }
}

/*
void bubSort(){
    for(int i = n - 1; i > 0; --i){
        for(int j = 0; j < i; ++j){
            if(seq[j] > seq[j+1]){
                int temp = seq[j];
                seq[j] = seq[j+1];
                seq[j+1] = temp;
                ++numOfSwap;
            }
        }
    }
}*/

int main(void){
    cin >> n;
    seq.reserve(n);
    seq2.reserve(n);
    for(int i = 0; i < n; ++i){
        cin >> seq[i];
    }
    mergeSort(0, n-1);

    cout << numOfSwap;
}

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

문제

문제

출처

ICPC

1517번 버블 소트 질문

lyradortiz913 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말