Cod sursa(job #2901346)

Utilizator N.B.Lnabil. N.B.L Data 13 mai 2022 16:56:04
Problema Sortare prin comparare Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb

#include <iostream>
#include <fstream>

using namespace std;
ifstream in("algsort.in");
ofstream out("algsort.out");

using namespace std;


const int N = 1e6;

int arr[N];

int mergeSort(int st, int ed);
//
//int main() {
//    int n;
//    cin >> n;
//    for (int i = 0; i < n; ++i)
//        cin >> arr[i];
//
//    mergeSort(0, n );
//    for (int i = 0; i < n; ++i)
//        cout << arr[i] << " ";
//    return 0;
//}

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

    mergeSort(0, n);
    for (int i = 0; i < n; ++i)
        out << arr[i] << " ";
    return 0;
}

//    3 2 12 22
//    3 2 - 12 22
//    3 - 2 - 12 - 22

//    0 - 1 - 2  - 3

//    2 - 3
//    12 - 22

//    4
//    22 12 3 2


int mergeSort(int st, int ed) {
    if (st == ed)
        return st;
    int mid = (st + ed) / 2;
    mergeSort(st, mid);
    mergeSort(mid + 1, ed);
    int i = 0, j = mid + 1, k = 0;
    while (i < mid && j < ed) {
        if (arr[i] > arr[j])
            swap(arr[i], arr[j]), i++;
        else
            j++;
        k++;
    }
    while (i < mid)
        swap(arr[i], arr[k]), i++, k++;
    while (j < ed)
        swap(arr[j], arr[k]), j++, k++;
//    for (int i = st; i < mid - 1; ++i) {
//        for (int j = i + 1; j < ed; ++j)
//            if (arr[i] > arr[j])
//                swap(arr[i], arr[j]);
//    }
    return st;

}