It sounds like you will have to read a file of integers like:
23
34
12
1
and covert them strings to int and put them in a sorted array.
I doubt that your prof wants you to learn how to call list::sort() although he/she may want you to learn about STL container classes.
To do this lab without any STL list, deques, vectors, hash or anything like that you will need a dynamic int array and then you can use an insertion sort. The dynamic array is made with a
int * int_array = new int[ARRAY_SIZE] (then deleted with delete [] int_array when finished)
Here is a class that I wrote that will handle dyamic int array sizing using new and a smallest to largest integer insertion sorting. At the end of the code is a small tester.
However, it was written in VC++ but as a standard console app, so there is no MFC MS specific stuff. The includes like stdio.h are also part of the Unix C headers. You probably won't have to change a single include. You may have to change the newlines to Unix style. TextPad will do it. It should at least get you started on the right path.
Code:
///////////////////////////////////////////////////////////////////////
// SortedIntArray.h:
//
//////////////////////////////////////////////////////////////////////
#ifndef __SORTEDINTARRAY_H
#define __SORTEDINTARRAY_H
#include <memory.h>
#include <stdio.h>
#define DEFAULT_ARRAY_SIZE 10 // Sizes for testing, change to larger number
#define DEFAULT_GROW_AMOUNT 5 // (eg 100 and 25)
class SortedIntArray
{
public:
SortedIntArray();
virtual ~SortedIntArray();
void insert_int(int newval);
void PrintArray();
int GetArraySize();
protected:
int * i_arr;
int ArraySize;
int NextOpenIndex;
void grow_array();
int find_insert_index(int newval);
void insert_new_val(int index, int newval);
};
#endif
///////////////////////////////////////////////////////////////////////
// SortedIntArray.cpp
//
//////////////////////////////////////////////////////////////////////
#include "SortedIntArray.h"
SortedIntArray::SortedIntArray()
{
printf("Constructing SortedIntArray: (%d)\n", DEFAULT_ARRAY_SIZE);
i_arr = new int[DEFAULT_ARRAY_SIZE]; // array of ints created when you create object
ArraySize = DEFAULT_ARRAY_SIZE;
NextOpenIndex = 0;
memset( (void *)i_arr, 0, ArraySize * sizeof( int ) ); // fill with 0's
}
SortedIntArray::~SortedIntArray()
{
printf("Destructor, deleting i_arr[] (%d)\n", ArraySize);
delete [] i_arr; // Cleanup when object falls out of scope
}
int SortedIntArray::GetArraySize()
{ return ArraySize;}
void SortedIntArray::insert_int(int newval)
{
int insert_index = 0;
if( NextOpenIndex == 0 )
{
i_arr[0] = newval;
printf("inserting %d at 0\n", newval);
NextOpenIndex++;
return; // nothing left to do, bail out
}
if ( NextOpenIndex > (ArraySize - 1) ) // Nowhere to put new number
grow_array();
//
// An insert sort is when you check all the elements for the correct position
// of (in this case) a number. It means that all your elements are sorted as they
// go into the array. This process gets increasingly slower are your array grows
// in size. You can, after 3 or more elements, begin to use a binary sort, which is
// many times faster.... but you have to implement it.
//
insert_index = find_insert_index(newval);
printf("inserting %d at %d\n", newval, insert_index);
insert_new_val(insert_index, newval);
}
void SortedIntArray::PrintArray()
{
printf("\nPrinting used part of array\n----------------------------------\n");
for( int i = 0; i < NextOpenIndex; i++)
{
printf("%d ", i_arr[i]);
//printf("%d:\t%d\n", i, i_arr[i]);
}
printf("\n----------------------------------\n\n");
}
int SortedIntArray::find_insert_index(int newval)
{
int ret = 0;
bool found_index = false;
for (int i = NextOpenIndex - 1; i >= 0; i--) // backwards loop
{
if( newval > i_arr[i] )
return (i + 1);
}
if( !found_index ) // number is less than entire list, it goes first
ret = 0;
return ret;
}
void SortedIntArray::insert_new_val(int index, int newval)
{
if( index == NextOpenIndex )
{
i_arr[index] = newval;
NextOpenIndex++;
return; // leave
}
// OR
// move all of the elements from the insert index up one
for( int i = NextOpenIndex; i >= index; i--) // backwards
{
if ( i > 0 )
i_arr[i] = i_arr[i - 1];
}
// Insert new value;
i_arr[index] = newval;
NextOpenIndex++; // move position
}
//-----------------------------------------
// Grow Array while preserving data.
//-----------------------------------------
void SortedIntArray::grow_array()
{
int * temp, * new_arr;
int new_size = 0;
temp = i_arr; // point temp a original array for later deletion
new_size = ArraySize + DEFAULT_GROW_AMOUNT;
printf("Growing array form %d to %d...\n", ArraySize, new_size);
new_arr = new int[new_size]; // make new array.
memset( (void *)new_arr, 0, new_size * sizeof( int ) ); // fill with zeros
memcpy( (void*)new_arr, (void *)i_arr, ArraySize * sizeof( int ) ); // copy data
/*
// Afraid of memcpy and what it is doing? Then use this:
for( int i = 0; i < ArraySize; i++ )
new_arr[i] = i_arr[i];
*/
i_arr = new_arr; // i_arr is now pointing at new_arr
ArraySize = new_size;
delete []temp; // release original array's resources
}
//////////////////////////////////////////////////
// Tester - main.cpp
//////////////////////////////////////////////////
#include "SortedIntArray.h"
int main()
{
SortedIntArray si_arr;
si_arr.insert_int(10);
si_arr.insert_int(34);
si_arr.insert_int(12);
si_arr.insert_int(6);
si_arr.insert_int(11);
si_arr.insert_int(10);
si_arr.insert_int(15);
si_arr.insert_int(9);
si_arr.insert_int(7);
si_arr.insert_int(10);
si_arr.insert_int(81);
si_arr.insert_int(8);
si_arr.insert_int(10); // 10 is our repeating number
si_arr.insert_int(2);
si_arr.insert_int(1);
si_arr.insert_int(5);
si_arr.insert_int(4);
si_arr.insert_int(3);
si_arr.insert_int(10);
si_arr.PrintArray();
return 0;
}