Блог

Я пишу программу, которая будет выполнять 5 различных функций сортировки и сравнивать время между ними. Я вывожу 1000-й элемент каждого массива, чтобы проверить, правильно ли он отсортирован, все мои другие сортировки, кроме сортировки слиянием, выдают правильное число. Сортировка слиянием близка, но отключена, она находится в пределах одного или двух элементов от получения правильного ответа (вывод 25011, а не 25034 для 1000-го элемента.) Вот код для моей сортировки слиянием:

 //Zach Heesaker. CS3. Project 4
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <stdio.h>
#include <ctime>
#include <cstdio>
#include <time.h>
#include <stdint.h>
#include<list>
#include<cmath>

using namespace std;

const int n = 10000;
int numswaps, numcompares;

void swap(intamp; a, intamp; b);
void print(int arr[], int n, ofstreamamp; outf, double time);
void read(int arr[], int size);
void mergepass(int arr[], int y[], intamp; n, intamp; L);
void mergeSort(int arr[], int n);
void merge(int arr[], int y[], int L, int m, int n);

int main()
{
    int numsorts = 5;
    string whichsort;
    ofstream outf("output.ot");
    int arr[n   1];
    clock_t start, end;
    double time;

    outf << "Sort Name: " << setw(5) << " " << "1000th Element: " << setw(1) << " " << "Number of Moves: " << setw(1) << " " << "Time taken: " << endl;
    read(arr, n);
    numcompares = 0;
    numswaps = 0;
    start = clock();
    mergeSort(arr, n);
    end = clock();
    time = double(end - start) / double(CLOCKS_PER_SEC);
}

void mergeSort(int arr[], int size)
{
    int L = 1;
    int y[n   1];
    while (L < n)
    {
        mergepass(arr, y, size, L);
        L = 2 * L;
        mergepass(y, arr, size, L);
        L = 2 * L;
    }
}

void merge(int arr[], int y[], int L, int m, int n)
{
    int i, j, k, t;
    i = L;
    k = L;
    j = m   1;
    while ((i <= m) amp;amp; (j <= n))
    {
        numcompares  ;
        if (arr[i] <= arr[j])
        {
            numswaps  ;
            y[k  ] = arr[i  ];
        }
        else
        {
            numswaps  ;
            y[k  ] = arr[j  ];
        }
    }
    if (i > m)
    {
        for (t = j; t <= n; t  )
        {
            numswaps  ;
            y[k   t - j] = arr[t];
        }
    }
    else
    {
        for (t = i; t <= m; t  )
        {
            numswaps  ;
            y[k   t - i] = arr[t];
        }
    }
}

void mergepass(int arr[], int y[], intamp; n, intamp; L)
{
    int i, t;
    i = 1;
    while (i <= n - 2 * L   1)
    {
        merge(arr, y, i, i   L - 1, i   2 * L - 1);
        i = i   2 * L;
    }
    if ((i   L - 1) < n)
    {
        merge(arr, y, i, i   L - 1, n);
    }
    else
    {
        for (t = i; t <= n; t  )
        {
            numswaps  ;
            y[t] = arr[t];
        }
    }
}

void swap(intamp; a, intamp; b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
    numswaps  = 3;
}

void print(int arr[], int n, ofstreamamp; outf, double time)
{
    outf << left  << setw(6) << " " << left  << arr[1000] << setw(12) << " " << left <<  numswaps << setw(10) << " " << left << "t" << time << endl;
}

void read(int arr[], int size)
{
    ifstream ifs("input.txt");
    int i = 0;
    while (!ifs.eof())
    {
        ifs >> arr[i];
        i  ;
    }
}

int merge(int arr[], int left, int right)
{
    int pivot = arr[right];
    int k = (left - 1);
    for (int j = left; j <= right - 1; j  )
    {
        numcompares  ;
        if (arr[j] < pivot)
        {
            k  ;
            swap(arr[k], arr[j]);
        }
    }
    swap(arr[k   1], arr[right]);
    return (k   1);
}
  

Есть идеи относительно того, что здесь происходит не так? Спасибо.