BOJ_1517 버블소트 c++ 랑 머지소트로 풀기

https://www.acmicpc.net/problem/1517

1517번: 버블 소트

1초에 1억번 수행한다고 하는데 그럼 병렬 수행은 안될까요?

내 프로세서는 1초에 n억번의 계산을 수행하는 프로세서다!

//https://www.acmicpc.net/problem/1517
#include <iostream>
using namespace std;

int count= 0; //몇번발생했는지
int arr[505050] = {0,};
int sorted[505050] = {0,};

void merge(int left, int mid, int right){
    int i, j, k;
    i = k = left;
    //c언어 대입은 right-most. 오른쪽부터 불러와서 왼쪽에 복사.
    j = mid +1;
    while(i <= mid && j <= right){
        if(arr[i] <= arr[j]){ //같을때도 교환하지 않습니다.
            sorted[k++] = arr[i++];
        }
        else{
            sorted[k++] = arr[j++];
            count += mid - i + 1; // 남은만큼
        }
    }
    //while(i>mid && j<= right){ //compact하나 시간은 더 걸림
        //sorted[k++] = arr[j++];
    //}
    if(i > mid){
        while(j<= right){
            sorted[k++] = arr[j++];
        }
    }
    else{
        while(i<=mid){
            sorted[k++] = arr[i++];
        }
    }
    //sort_completed.

    for(int x = left; x <= right; x++){
        arr[x] = sorted[x];

    }
    return;
}


void mergesort(int left, int right){
    int mid;
    if(left < right){
        mid = ((left + right)/2);
        mergesort(left , mid);
        mergesort(mid+1, right);
        merge(left, mid, right);
    }
    return;
}
int main(){
    int n = 0;
    cin >> n;

    for(int i = 0; i < n ; i++){
        cin >> arr[i];
    }

    mergesort(0, n-1);

    cout << count;
    return 0;
}

 

#include <iostream>

using namespace std;

 

int count= 0; //몇번발생했는지 

int arr[505050] = {0,};

int sorted[505050] = {0,};

--> 전역변수로 작성해줍니다. 그리고 배열을 505050 이렇게 작성하는건 보기 좋아서 입니다.
사실 세개마다 반점하나만 찍으면 더 좋을거같은데
우리 컴퓨터는 멍청해서 그런거 못할거같음.

void merge(int left, int mid, int right){

    int i, j, k;

    i = k = left;

c언어 대입은 right-most. 오른쪽부터 불러와서 왼쪽에 복사.
i = d = k = left 라고 하면 left값이 k부터 차근차근 들어감.

    j = mid +1;

    while(i <= mid && j <= right){

        if(arr[i] <= arr[j]){ //같을때도 교환하지 않습니다.

            sorted[k++] = arr[i++];

        }

        else{

            sorted[k++] = arr[j++];

            count += mid - i + 1; // 남은만큼

        }

    }

    //while(i>mid && j<= right){ //compact하나 시간은 더 걸림

        //sorted[k++] = arr[j++];

    //}

    if(i > mid){

        while(j<= right){

            sorted[k++] = arr[j++];

        }

    }

    else{

        while(i<=mid){

            sorted[k++] = arr[i++];

        }

    }

    //sort_completed.

left right을 이용하여서 풀어도 괜찮으나
재귀를 시키기 위해
유동적으로 mid를 잡고
mid 기준으로 앞뒤로 움직이게 해도 풀린다.

 

    for(int x = left; x <= right; x++){

        arr[x] = sorted[x];

 

    }

    return;

}

void mergesort(int left, int right){

    int mid;

    if(left < right){

        mid = ((left + right)/2);

        mergesort(left , mid);

        mergesort(mid+1, right);

        merge(left, mid, right);

    }

    return;

}

int main(){

    int n = 0;

    cin >> n;

 

    for(int i = 0; i < n ; i++){

        cin >> arr[i];

    }

 

    mergesort(0, n-1);

 

    cout << count;

    return 0;

}