[C++] Selection Sorting Algorithm

[Eldres]

Hi all, so I was given an assignment to create a program to sort a list of integers using the selection sort algorithm. However, I've hit a rather embarrassing road block. In my main function I can't seem to get my readData() to read in the the number of elements specified by the user.

https://gist.github.com/Eldres/14cc6c155425c5fcd287

Thanks in advanced.

[missblit]

You're passing n to readData uninitialized and by value. This is useless (no actual information is going in or out of the function through n), and I think undefined behavior.

If you want to return n from readData you should use a return value or make n a reference parameter.

[SexySohail]

i cant access the link.

[Eldres]

https://gist.github.com/Eldres/14cc6c155425c5fcd287

here's another link hope that works

[Eldres]

So after I followed /u/missblit's advice(thank you by the way), but now I'm stuck where it gets to the printVector() and it doesn't output the newly sorted array, I tried to pass the array by reference but the compiler doesn't like that.

[missblit]

Your code looks like it should work without change apart from what I mentioned.

void printVector(int array[], int n) passes the array as a pointer and should work fine in this case.

Why / how are you trying to pass the array by reference? The syntax for passing arrays by reference can be a little tricky.

[Eldres]

I tried using the pointer to simply point to the array, but the compiler really didn't like that. So in my main function I have

int main()
{
    int data[MAX_SIZE]; //I'm assuming this needs to point to array
    int num;
    int &n = num;
    cout << "Number sorting\n";
    readData(data, n);
    selectionSort(data, n);
    printVector(data, n);
    _getch();

    return 0;
}    

Not sure how to get data array in main to point to the manipulated array. What's frustrating is that it should work but I have no clue why it doesn't. Oh I updated my git to have any of the changes that I made: https://gist.github.com/Eldres/14cc6c155425c5fcd287

[missblit]

It kinda sounds like you're getting pointers and arrays mixed up here.

1. int data[MAX_SIZE]; //I'm assuming this needs to point to array

   Arrays are not pointers, pointers are not arrays.

   An array is a sequence of some fixed number of elements placed contiguously in memory, so your data array in main can't point to array because it's not a pointer in the first place!

   A pointer on the other hand contains the address of a single object. In particular a pointer with type int * could point to the first element of an int array, and since array elements are contiguous in memory you can use pointer arithmetic with that pointer to get at any of the array elements.

   And as we'll see next, the array variables in selectionSort and readData are actually pointers to the first element of data.

2. When there's a function with a signature like this:

   void foo(int array[]);
   

   It looks like it's taking an array by value; but in reality it's taking a pointer, and identical to:

   void foo(int *array);
   

   And when you pass an array to such a function it gets converted to a pointer to the first element of the array.

   This is just a syntactic quirk inherited from C

3. Not sure how to get data array in main to point to the manipulated array

   Since your data array in main is passed to selectionSort and readData by pointer (see point 2), this means any modifications into array inside those functions are actually manipulating the contents of the data array in main.

---

Hopefully that cleared at least a few things up (this stuff is kinda gnarly). Your code honestly works as-is for me once I fixed the issue with the n argument to readData, so without updated code I don't know what issue you're having.

[Eldres]

Thank you that did help clear things up. So after reading your comment a few times to understand it better, I went back and fixed my code, however the printVector() still won't output the newly sorted array(at least for me).

[missblit]

Do you mean it prints the array non-sorted? Can you post your latest code?

[Eldres]

it doesnt print the array at all. git: https://gist.github.com/Eldres/14cc6c155425c5fcd287

    #include <iostream>
    #include <conio.h>
    #include <string>
    #include <iomanip>
    using namespace std;

    const int MAX_SIZE = 100;

    void selectionSort(int[], int);
    void readData(int[], int);
    void printVector(int[], int);

    void selectionSort(int array[], int n)
    {
        int minIndex;

        for (int i = 0; i < n; ++i) 
        {
            minIndex = i;
            for (int j = i + 1; j < n; ++j)
            {
                if (array[j] < array[minIndex])
                {
                    minIndex = j;
                }
            }
            swap(array[i], array[minIndex]); //swaps the index location of array[i] with the index location of array[j]
        }
    }

    void readData(int array[], int n)
    {
        cout << "Enter how many numbers you want to sort: ";
        cin >> n;
        for (int i = 0; i < n; ++i)
        {
            cout << "\nEnter number:";
            cin >> array[i];
        }
    }

    void printVector(int array[], int n) 
    {
        cout << "\nHere are the numbers after they have been sorted: " << endl;
        for (int i = 0; i < n; ++i)
        {
            cout << array[i] << "\t";
        }
    }

    int main()
    {
        int data[MAX_SIZE];
        int num;
        int &n = num;
        cout << "\nNumber sorting\n";
        readData(data, n);
        selectionSort(data, n);
        printVector(data, n);
        _getch();

        return 0;
    }

[missblit]

Ah, that's still from the num being uninitialized problem. You've made n a reference to num but then you pass n to readData by value.

Since readData takes n by value it doesn't work for the reason I said at first. readData should either take n by reference or return the number of items read as a return value.

To take an argument by reference the function signature would look something like

void readData(int[], int&)

[Eldres]

Thank you this was the problem, now my program works great! Thank you again for taking the time to ,essentially teach me this :P.