coding%20test/DivideAndConquer/

[utterances-bot]

[Coding Test] divide and conquer - 1FeS Notes

divide and conquer in cpp

https://wch18735.github.io/coding%20test/DivideAndConquer/

[wch18735]

#include<iostream>

using namespace std;

const int MAXNUM = 2000;
int N, Arr[MAXNUM];
void mergeSort(int*, int);
int main(int argc, char** argv) {
    freopen("sort_sample.txt", "r", stdin);

    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%d", &Arr[i]);

    mergeSort(Arr, N);

    return 0;
}

void printA() {
    for (int i = 0; i < N; i++)
        printf("%d ", Arr[i]);
    printf("\n");
}

void printPart(int *arr, int len) {
    for (int i = 0; i < len; i++) printf("%d ", arr[i]);
    printf("\n");
}

void mergeSort(int* arr, int len) {
    if (len == 1) return;

    int mid = len / 2;
    mergeSort(arr, mid);
    mergeSort(arr + mid, len - mid);

    int* tmp = new int[len];
    int leftSide = 0, cnt = 0, rightSide = mid;

    while (leftSide < mid && rightSide < len) {
        if (arr[leftSide] < arr[rightSide])
            tmp[cnt++] = arr[leftSide++];
        else
            tmp[cnt++] = arr[rightSide++];
    }

    while (leftSide < mid)
        tmp[cnt++] = arr[leftSide++];

    while (rightSide < len)
        tmp[cnt++] = arr[rightSide++];

    for (int i = 0; i < len; i++)
        arr[i] = tmp[i];

    delete[] tmp;
}

[wch18735]

zero base → one base

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

const int MAXNUM = 2000;
int N, Arr[MAXNUM], TmpArr[MAXNUM];
void mergeSort(int*, int, int);
int main(int argc, char** argv) {
    //freopen("sort_sample.txt", "r", stdin);

    scanf("%d", &N);
    for (int i = 1; i <= N; i++) scanf("%d", &Arr[i]);

    mergeSort(Arr, 1, N);

    return 0;
}

void printA() {
    for (int i = 1; i <= N; i++)
        printf("%d ", Arr[i]);
    printf("\n");
}

void mergeSort(int* arr, int s, int e) {
    if (s >= e) return;
    int mid = (s + e) / 2;

    mergeSort(arr, s, mid);
    mergeSort(arr, mid + 1, e);

    int leftside = s, rightside = mid + 1, cnt;
    for (cnt = leftside; cnt <= e;) {
        if (rightside > e) TmpArr[cnt++] = arr[leftside++];
        else if (leftside > mid) TmpArr[cnt++] = arr[rightside++];
        else if (arr[leftside] <= arr[rightside]) TmpArr[cnt++] = arr[leftside++];
        else TmpArr[cnt++] = arr[rightside++];
    }

    for (cnt = s; cnt <= e; cnt++) arr[cnt] = TmpArr[cnt];

    printA();
}