sorting array of structs

[markymark99]

struct Process{
    int pid;
    int burst;
    int arrival;
};

int main(int argc, char *argv[]){

    int numProcesses = 3;

    Process *arrayOfProcesses = new Process[numProcesses];

    arrayOfProcesses[0].pid = 0;
    arrayOfProcesses[0].burst = 8;
    arrayOfProcesses[0].arrival = 2;

    arrayOfProcesses[1].pid = 1;
    arrayOfProcesses[1].burst = 12;
    arrayOfProcesses[1].arrival = 3;

    arrayOfProcesses[2].pid = 2;
    arrayOfProcesses[2].burst = 4;
    arrayOfProcesses[2].arrival = 1;

with this code here i want to list this data in ascending order of the burst value, so itll print:

0,8,2
1,12,3
2,4,1

. I need to set a funtion to do it but i have no clue how to sort it

[mbozzi]

https://en.wikipedia.org/wiki/Bubble_sort

[gunnerfunner]

OP: you'd have to do a few more things since you're sorting custom data-types:
a. overload operator < for Process based on data-member burst
b. define assignment operator, bubble sort requires it
c. by rule of 3, also define copy ctor and dtor

#include <iostream>
using namespace std;

struct Process{
    int pid;
    int burst;
    int arrival;
    Process(){}
    Process (int p, int b, int a) : pid(p), burst(b), arrival (a) {}
    Process (const Process& rhs);
    Process& operator = (const Process& rhs);
    ~Process () {}

    bool operator < (const Process& rhs)const
    {
        return burst <= rhs.burst;
    }
};
ostream & operator << (ostream & os, const Process& rhs);

int main()
{
    int numProcesses = 3;
    Process arrayOfProcesses[numProcesses]  {Process(0, 8, 2), Process (1, 12, 3), Process (2, 4, 1)};
    //use intializer lists and overloaded ctor's to reduce typing

    Process tmp;

    for(size_t i = 0; i < numProcesses; i++)
    {
        for (size_t j = i+1; j < numProcesses; j++)
        {
            if(arrayOfProcesses[j] < arrayOfProcesses[i])
            {
                tmp = arrayOfProcesses[i];
                arrayOfProcesses[i] = arrayOfProcesses[j];
                arrayOfProcesses[j] = tmp;
            }
        }
    }
    for(size_t i = 0; i < numProcesses; i++)
    {
        cout << arrayOfProcesses[i];
    }
}
Process::Process (const Process& rhs)
{
    pid = rhs.pid;
    burst = rhs.burst;
    arrival = rhs.arrival;
}
Process& Process::operator = (const Process& rhs)
{
    if(this == &rhs)
    {
        return *this;
    }
    pid = rhs.pid;
    burst = rhs.burst;
    arrival = rhs.arrival;

    return *this;
}
ostream & operator << (ostream & os, const Process& rhs)
{
    os << "Pid: " << rhs.pid << " Burst: " << rhs.burst << " Arrival: " << rhs.arrival << '\n';

    return os;
}

[keskiverto]

OP: you'd have to do a few more things since you're sorting custom data-types:
a. overload operator < for Process based on data-member burst
b. define assignment operator, bubble sort requires it
c. by rule of 3, also define copy ctor and dtor

Not for a POD (plain-old-data) type. The Process contains mere integers in it and the compiler generated default operators are thus sufficient, except for the comparison.

The "rule of 3" is a necessity when the object has pointers as members and plain copies are not appropriate.


Overloading the operator< is possible, and it creates a default ordering. However, one could as well create a predicate function:
bool compBurst( const Process & lhs, const Process & rhs );

The compBurst should return true, if burst of lhs is less than burst of rhs. In all other cases return false.


(One can have multiple predicate functions, to sort same array in more than one way.)

When one has a predicate function, one can use it in a sorting algorithm. For example:
std::sort( arrayOfProcesses, arrayOfProcesses + numProcesses, compBurst );
See http://www.cplusplus.com/reference/algorithm/sort/
for that that does.

One is free to write the sort algorithm self, for educational purposes.

[gunnerfunner]

Very good point keskiverto. Using a lambda does indeed shrink the program, thanks

#include <iostream>
#include <algorithm>
using namespace std;

struct Process{
    int pid;
    int burst;
    int arrival;
    Process(){}
    Process (int p, int b, int a) : pid(p), burst(b), arrival (a) {}
 };
ostream & operator << (ostream & os, const Process& rhs);

int main()
{
    int numProcesses = 3;
    Process arrayOfProcesses[numProcesses]  {Process(0, 8, 2), Process (1, 12, 3), Process (2, 4, 1)};
    //use intializer lists and overloaded ctor's to reduce typing

    sort(arrayOfProcesses, arrayOfProcesses + numProcesses,
         [] (const Process& lhs, const Process& rhs) ->bool {return lhs.burst <= rhs.burst;});
    for(size_t i = 0; i < numProcesses; i++)
    {
        cout << arrayOfProcesses[i];
    }
}
ostream & operator << (ostream & os, const Process& rhs)
{
    os << "Pid: " << rhs.pid << " Burst: " << rhs.burst << " Arrival: " << rhs.arrival << '\n';

    return os;
}

[jlb]

Beware, the following uses a VLA which is not allowed in C++.

    int numProcesses = 3;
    Process arrayOfProcesses[numProcesses]  {Process(0, 8, 2), Process (1, 12, 3), Process (2, 4, 1)};

It would be better off as:

    Process arrayOfProcesses[]  {{0, 8, 2}, {1, 12, 3}, {2, 4, 1}};
    size_t numProcesses = sizeof(arrayOfProcesses) / sizeof(arrayOfProcesses[0]);

Or better yet use a std::vector!

    std::vector<Process> vectorOfProcesses = {{0, 8, 2}, {1, 12, 3}, {2, 4, 1}};
    sort(vectorOfProcesses.begin(), vectorOfProcesses.end(),
         [] (const Process& lhs, const Process& rhs)->bool
                    {return lhs.burst < rhs.burst;});

    for(auto& itr : vectorOfProcesses)
        cout << itr << endl;

Of course if this was truly hard coded data you could bypass the sort by initializing the vector/array in the proper order.

[gunnerfunner]

But C++ standard (till C++11) doesn’t support variable sized arrays. The C++11 standard mentions array size as a constant-expression See (See 8.3.4 on page 179 of N3337). So the above program may not be a valid C++ program. The program may work in GCC compiler, because GCC compiler provides an extension to support them.

As a side note, the latest C++14 (See 8.3.4 on page 184 of N3690) mentions array size as a simple expression (not constant-expression).

http://www.geeksforgeeks.org/variable-length-arrays-in-c-and-c/

[mbozzi]

I thought the claim that VLAs are legal was dubious, so I checked the standard myself. Perhaps that was a typo, or the proposed feature was dropped.

Quoting WG21 draft, N3797 [dcl.array]:

In a declaration T D where D has the form
D1 [ constant-expression_opt ] attribute-specifier-seq_opt
and the type of the identifier in the declaration T D1 is “derived-declarator-type-list T”, then the type of the identifier of D is an array type; if the type of the identifier of D contains the auto type-specifier, the program is ill-formed. T is called the array element type; this type shall not be a reference type, the (possibly cv-qualified) type void, a function type or an abstract class type. If the constant-expression (5.19) is present, it shall be a converted constant expression of type std::size_t and its value shall be greater than zero. The constant expression specifies the bound of (number of elements in) the array. If the value of the constant expression is N, the array has N elements numbered 0 to N-1, and the type of the identifier of D is “derived-declarator-type-list array of N T”....

If you want more evidence (perhaps more credible than a citation of yet another working draft), check http://en.cppreference.com/w/cpp/language/array .
Consistent with my citation, the array bound must be a converted constant expression.

[gunnerfunner]

Max: thanks for following this up, makes sense. If this was not the case we could have something like:

#include <iostream>

int main( )
{
    size_t x = 4;

    int arr[x] = {1, 2, 3, 4};

    x = 3;

    for(size_t i = 0; i < x; i++)
    {
       std::cout << arr[i] << " ";//Output: 1 2 3
    }
    std::cout << '\n';
    x = 5;
    for (size_t i = 0; i < x; i++)
   {
       std::cout << arr[i] << " ";//Output: 1 2 3 4 3
   }
}

Though my compiler (GCC 4.9.2) doesn't complain in the first instance, when x = 3, arr[4] is now 'lost' much like an object on the heap whose pointer has been deleted and in the second, when x = 5, a spurious number from memory is printed as arr[5]. Both, of course, are to be avoided.
I ran it on cpp.sh as well under C++14 where the program executed too with outputs {1, 2, 3} and {1, 2, 3, 4, 0} respectively. Once again just because it runs doesn't mean its accurate or advisable. Thanks again

[jlb]

Though my compiler (GCC 4.9.2) doesn't complain in the first instance,

Well if you have your compiler properly configured it would do more than just "warn" you it would fail to compile.

||=== Build: Debug in testcpp (compiler: gcc 6.1.0) ===|
main.cpp||In function ‘int main()’:|
main.cpp|7|error: ISO C++ forbids variable length array ‘arr’ [-Wvla]|
||=== Build failed: 1 error(s), 0 warning(s) (0 minute(s), 0 second(s)) ===|

From here on I will be using an array that has a size that is a compile time constant, therefore avoiding the nasty VLA issues.

when x = 3, arr[4] is now 'lost' much like an object on the heap whose pointer has been deleted

Again with a properly configured compiler, if x were 3 you would get a compile error, assuming you have more initializers than the size of the array.
||=== Build: Debug in testcpp (compiler: gcc 6.1.0) ===|
main.cpp||In function ‘int main()’:|
main.cpp|7|error: too many initializers for ‘int [3]’|
||=== Build failed: 1 error(s), 0 warning(s) (0 minute(s), 0 second(s)) ===|

when x = 5, a spurious number from memory is printed as arr[5]. Both, of course, are to be avoided.

I suppose you mean arr[4] since arr[5] is not a valid element of the array and trying to access an array of size 5 with arr[5] is an array out of bounds error, which produces undefined behavior.

But accessing arr[4] (the fifth element) doesn't print a spurious value. Since you have only partially initialized the array any element that you didn't supply a value was "default" initialized, so all the array elements are properly initialized, int this case arr[4] has a value of 0.