Efficient algorithm for sorting objects by key that are range from 0 to 100 for big input sizes

user_2730608 0
Viewed 126

I have the following class that represents students info:

struct Student
{
    std::string name;
    int id = 0;
    short rank = 0;
};

The field rating can be any number from 0 to 100. I need to implement the following function that sorts students in descending order:

void fast_sort(std::vector<Student>& students)
{
  // TODO:
}

Can I do the sort somehow in-place? What's the most efficient approach for big size inputs?

I have already tried to count the number of students for each rating:

std::map<short, int> counter;
for(size_t i = 0; i < students.size(); ++i)
{
    short rank = students[i].rank;
    ++counter[rank];
}

Now I am thinking about the way to put students on the right place without using additional std::vector.

sorting algorithm c++
3 Answers

The std::sort function might be useful for you since it allows using a user defined comparison function as in the following example :

// sort algorithm example
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include "Student.h" // your Student's class header

bool myfunction (const Student& x, const Student& y) { 
  return (x.getRating()<y.getRating()); 
}

int main () {
  
  std::vector<Student> myStudents;
  
  // fill your Students vector with your logic

  // using myfunction as comp
  std::sort (myStudents.begin(), myStudents.end(), myfunction);  

  return 0;
}

Its time complexity is in O(nlog(n)), no better than the best performing known general sorting algorithm.

user_47244580

Counting sort

  1. Count the number of students for each rank;
  2. Use the cumulative counts to find the index of the first student of every rank;
  3. Put the students at the first available index for their rank.

Each of these three steps has complexity O(n+k), where n is the number of students and k the number of ranks.

I'll show an example with 10 students, with ranks going from 0 to 2 instead of 0 to 100.

# define NBSTUDENTS 10
# define NBRANKS 3

struct Student students[NBSTUDENTS] =
  {("Alice", 0),  ("Bob", 2),     ("Charlie", 1), ("Daenerys", 1), ("Eleonore", 2),
   ("Farouk", 1), ("Gabriel", 0), ("Hector", 1),  ("Iris", 2),     ("Julien", 2)};
  1. Count the number of students for each rank
int count_per_rank[NBRANKS] = {2, 4, 4};
  1. Use the cumulative counts to find the index of the first student of every rank
int available_index[NBRANKS] = {0, 0+2, 0+2+4};

You can use std::partial_sum defined in header <numeric> to get the cumulative counts; see Surt's answer.

  1. Put the students at the first available index for their rank
struct Student sorted_students[NBSTUDENTS] = {}
for (auto student = students.begin(); student < students.end(); ++student)
{
    sorted_students[available_index[student->rank]] = *student;
    available_index[student->rank]++;
}

std::sort

The complexity of std::sort is O(n log(n)). The complexity of the counting sort above is O(n+k). These O( ) notation hide a constant; you can expect that constant to be much smaller for the well-optimised std::sort than for your custom implemented sort. When n tends towards infinity, log(n) also tends towards infinity. But log increases very slowly. How big is your big size input? I assume you have fewer than a million students. The binary logarithm of 1000000 is 20. If we assume n < 1000000, then n log(n) < 20 n. Are we really faster than std::sort with our custom counting sort?

user_30807230

You have nearly solved it yourself, a little change to the counting code

(totally untested code)

std::map<short, int> counter;
for(size_t i = 0; i < students.size(); ++i) {
    short rank = students[i].rank;
    ++counter[rank];
}

to

std::array<int, Values> counter;
for(size_t i = 0; i < students.size(); ++i) {
    short rank = students[i].rank;
    ++counter[rank];
}

Where values is the number of contiguous different values 0..Values-1

Then use counting sort (the foundation of radix sort)

std::array<int, Values> pos = {0};
std::partial_sum(counter.begin(), std::prev(counter.end()), std::next(pos.begin()));

Now you have the starting point of each rank.

std::vector<Student> studs;
for (int i = studs.size(); i < studs.end(); ++i) {
  int wanted = pos[studs[i].rank];
  while (wanted != i) {
    pos[studs[i].rank]++;
    swap(studs[i], studs[wanted]);
    wanted = pos[studs[i].rank];
  }
}
user_40132580
Related