Input sorting without arrays, pointers, or vectors

[nightcrew]

Assume you have a int variable n that has already been declared and initialized. Its value is the number of integers that need to be read in from standard input and printed out in sorted (ascending) order, each on a line by itself. Furthermore, there are no duplicates in the input and every number to be read is a non-negative value that is less than n's value.

In this exercise you may not use any array (or fancy STL collection such as a vector). You may declare a variable or two as needed. With these restrictions, read the n values and print them out as required onto standard output.

This is a direct quote from an exercise. Seems like a step backwards, but this is what my professor has assigned.

In fact, in the previous three questions I solved similar problems using arrays. He just wants it done without one now.

We are not required to write the entire program, just the piece that would solve the provided question.

Any guidance would be appreciated.

[nightcrew]

Below are the solutions I came up with for the previous two questions.

The first asked you to sort n random inputs that could range from 0 to 49 in order without displaying duplicates using a boolean array:

int counter, x;

for (counter = 0; counter < 50; counter++){
    wasReadIn[counter] = false;}
for (counter = n; counter > 0; counter--){
    cin >> x;
    if (x > -1 && x < 50)
        wasReadIn[x] = true;}
for (counter = 0; counter < 50; counter++){
    if (wasReadIn[counter] == true)
        cout << counter << " ";}

The second asked you do perform a similar task, except this time duplicates could be stored and output using an integer array:

int counter, duplicates, x;

for (counter = 0; counter < 50; counter++){
    wasReadIn[counter] = 0;}
for (counter = n; counter > 0; counter--){
    cin >> x;
    if (x > -1 && x < 50)
        wasReadIn[x] += 1;}
for (counter = 0; counter < 50; counter++){
    if (wasReadIn[counter] >= 1){
        for (duplicates = wasReadIn[counter]; duplicates > 0; duplicates--)
            cout << counter << " ";}}

Now this question is again asking for a very similar output, but I just don't even know where to begin without using an array. Thought posting the previous questions might shed some light on the original post.

[vijayan121]

An external merge sort using four files, perhaps?

http://en.wikipedia.org/wiki/Merge_sort#Use_with_tape_drives

[nightcrew]

The exercise is run through a server, so I don't think I can use files for I/O unless the program references a file name for me (which it normally does if files can be used).

[sfuo]

This sounds like a trick question to me because if n was 50 or something and I gave the input 20, 30, 21, 49, 1, 35, ... 0 how would you be able to sort that without having a variable for each input.

To "sort" a bunch of input in ascending order with n numbers and no duplicates can be done by using a for() loop

for( int i = 0; i < n; i++ )
	cout << i << endl;

[nightcrew]

how would you be able to sort that without having a variable for each input.

This is the very question that has been puzzling me since I first laid eyes on the problem.

Probably something simple I'm missing here that I'll kick myself for later.

[WaltP]

Output the numbers to the printer
Cut the numbers from the paper
Sort them on the table
Tape them together when sorted.
:icon_twisted:

[arkoenig]

If there's no upper bound on n, then you need a data structure that can grow without bound. If you can't use arrays or pointers, then you must find some other data structure that grows without bound. If you're not allowed to use any such data structure, then the only solution I can see is to use recursion to store the information you need on the call stack somehow. I don't immediately see how, but I also don't see any other way to do it.

Either that or there's some other aspect of the problem that you haven't told us.

[Caligulaminus]

I thought the same as sfuo wrote.

[nightcrew]

The original post is exactly, word for word, what the question states. I have not excluded any details. To hold back information would not be beneficial in my attempt to solve the problem.

[nightcrew]

I want to try the external merge sort with files.

Probably the only way. I'll update if it works (which it probably will).

[NathanOliver]

The only thing I can think of is that maybe you are to use a stream iterator and loop through it outputting what you need each iteration. This seams like a very nonsense question.

[arkoenig]

Oh, wait a minute, I got it. It is indeed a trick question. sfuo is right. Read the conditions carefully.

[nightcrew]

I took a crack at using a file for sorting.

I keep entering an infinite loop on the test object, and if I plug the code into Bloodshed and build my own main, it skips the while loop at line 26 no matter what numbers I enter.

So, this method may work... I'm obviously just going about it the wrong way if it does though. The class I am taking is an introduction to C++, so just keep that in mind when breaking down what I've used.

ofstream outputFile;
ifstream inputFile;
int counter, number, minimum;

minimum = n;
outputFile.open("Random_Numbers.txt");
for(counter = n; counter > 0; counter--)
{
    cin >> number;
    outputFile << number << endl;
}
outputFile.close();
number = 0;
do
{
    counter = 0;
    inputFile.open("Random_Numbers.txt");
    while (inputFile >> number)
    {
        if (number < minimum)
            minimum = number;
    }
    inputFile.close();
    inputFile.open("Random_Numbers.txt");
    outputFile.open("temp_File.txt");
    while (inputFile >> number)
    {
        if(number != minimum)
        {
            outputFile << number << endl;
            counter++;
        }
    }
    inputFile.close();
    outputFile.close();
    remove("Random_Numbers.txt");
    rename("temp_File.txt","Random_Numbers.txt");
    if (counter > 0)
        cout << minimum << endl;
}while (counter > 0);

[sfuo]

Yeah but if you think about it a file is pretty much a big array of characters so if he would let you do that then thats a joke.

[nightcrew]

Pretty much.

But, I might as well try it. I've got no other leads to follow, so if anyone can help me identify where I've gone wrong with my code, it would be much appreciated.

[kriviere]

OK, let me state this more explicitly. If I have n non-negative integers, each of which is less than n, then that defines the set of integers [0..n-1]. All the code needs to do is read in the n integers and write out the integers 0 to n-1. It doesn't matter what order they appeared in the input file.

[sfuo]

Since it says there are no duplicate inputs I'm guessing (and there is no way to check) there will be no need for checking if a duplicate number was entered. You can throw on a check to restrain input from [0,n).

This is what I came up with "1 day ago" according to this thread.

#include <iostream>
using namespace std;

int main()
{
	int n = 10, inpt;

	for( int i = 0; i < n; i++ )
		cin >> inpt;

	for( int i = 0; i < n; i++ )
		cout << i << endl;

	return 0;
}

[nightcrew]

I guess I was trying to be too serious about it...

I'll try some simple for loops when I get home tonight.

I do appreciate the input from everyone. If this is a trick question... Oh, so mad. ;)

[marnun]

i know it's been a while since you posted this question, but i am wondering if you were able to solve it (i am stuck with it in codelab now). thanks

[Nutster]

As stated in the earlier posts, n non-negative integer values less than n without duplicates would be all the integers from 0 to n-1. So read in all the numbers, and then run another loop to just print all the integers from 0 to n-1. No need to actually store any of the numbers.

I do like the idea of recursive function calls to sort the numbers, though.

[marnun]

thanks! talking about paying attention to details..
btw, just learned about recursion functions tonight :-)

[ralhamami]

I know this is old, but I've figured this out. There are two things to keep in mind here:
1. n is the numbers of inputs (No more, no less)
2. All inputs will be between 0 and n-1

That means, in ascending order, it will literally be 0 to n-1, so the correct solution would be a simple:

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

Hope that helps somebody! :)

[omgerg]

int j;
int i;
for( i = 0; i < n; ++i){
scanf("%d\n", j);
}
for( i = 0; i < n; ++i){
printf("%d\n" , i);
}