随机数外部排序 [英] Random numbers external sort

问题描述

我需要编写一个生成N个随机数并将其按降序写入二进制文件的程序.应该在不使用任何使用主内存的排序算法的情况下完成此操作.到目前为止，这是我所做的:

I need to write a program that generates N random numbers and write them to binary file in descending order. It should be done without using any of sorting algorithms that use main memory. This is what I've done so far:

#include <iostream>
#include <fstream> 
#include <ctime>
#include <cstdlib>

using namespace std;
int main () {
  srand(time(0));
  rand();
  int N;
  do{
    cout << "Unesite N: ";
    cin >> N;
    } while(N<=0);

  ofstream br("broj.dat", ios::binary | ios::trunc);

  for(int i = 0; i<N; i++){
    int a = rand();
    br.write((char *)&a, sizeof(a));
  }
  br.close();

  return 0;
}

因此，我生成了随机数并将其写入二进制文件，但是我不知道如何对其进行排序.

So, I've generated random numbers and wrote them to binary file but I don't know how to sort it.

推荐答案

您可以在线性时间内按排序顺序生成数字.描述如何执行此操作的论文是:通过Bentley& amp; amp; amp; amp;生成随机数排序列表.萨克斯

You can generate your numbers in sorted order in linear time. The paper describing how to do this is: Generating Sorted Lists of Random Numbers by Bentley & Saxe

https://pdfs.semanticscholar.org/2dbc/4e3f10b88832fcd5fb88d34b8fb0b<2000年./p>

https://pdfs.semanticscholar.org/2dbc/4e3f10b88832fcd5fb88d34b8fb0b0102000.pdf

/**
 * Generate an sorted list of random numbers sorted from 1 to 0, given the size
 * of the list being requested.
 * 
 * This is an implementation of an algorithm developed by Bentley and Sax, and
 * published in in ACM Transactions on Mathematical Software (v6, iss3, 1980) on
 * 'Generating Sorted Lists of Random Numbers'.
 */
public class SortedRandomDoubleGenerator {
    private long       valsFound;
    private double     curMax;
    private final long numVals;

    /**
     * Instantiate a generator of sorted random doubles.
     * 
     * @param numVals the size of the list of sorted random doubles to be
     *        generated
     */
    public SortedRandomDoubleGenerator(long numVals) {
        curMax = 1.0;
        valsFound = 0;
        this.numVals = numVals;
    }

    /**
     * @return the next random number, in descending order.
     */
    public double getNext() {
        curMax = curMax
                * Math.pow(Math.E, Math.log(RandomNumbers.nextDouble())
                        / (numVals - valsFound));
        valsFound++;
        return curMax;
    }
}

这篇关于随机数外部排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！