Sort Array by First Item in Subarray C++

sort array by first item in subarray c++

One way to sort the array is to not sort the array itself.

Instead, sort an array of indices that point inside of the array, and then use the sorted index to access the elements. It is much easier to do that than to manipulate a 2d array in a sorting function.

In general, if you have the memory for the array of indices (we will need additional storage for the index array), sorting objects that have

1. a large payload per item, or
2. the original order of the array needs to be kept around, or
3. sorting is just clumsy¹ or impossible to manipulate easily in a sorting algorithm,

can use this technique that will be described here.

Here is an example:

#include <algorithm>
#include <iostream>

int main()
{
    int index[3] = {0,1,2};
    int timeTable[3][2] = {{4, 204}, {10, 39}, {1, 500}};
    std::sort(index, index + 3, [&](int n1, int n2){ return timeTable[n1][0] < timeTable[n2][0]; });
    for (int i = 0; i < 3; ++i)
       std::cout << "The index is " << index[i] << ".  The data at this index is  [" << 
                 timeTable[index[i]][0] << " " << timeTable[index[i]][1] << "]\n";
}

Live Example

So basically we create an initial index array numbered from 0 to n-1 where n are the number of items to sort. Then we call std::sort on the index, and in the sorting criteria, we compare the items in the actual array using the indices passed to the sorting predicate. The result will be the index array having its elements swapped around during the sort instead of the original array's elements being swapped.

Note that the sorting predicate is very simple -- we state exactly what we want the indices to represent in the sort by using the indices being passed on the timeTable array. There is no tricky, error-prone, or code that does not scale well if one of the items is out of order (for example, the parallel array scenario -- imagine 20 arrays and having to swap 20 items just because one item is out of order).

After sorting the indices, when it comes time to use the timeTable array, we use the index array to point to the items (note how we specify the index by using timeTable[index[i]][0] instead of timeTable[i][0]).

---

¹ Included in the "clumsy" category are those "parallel
array sort" questions that show up on StackOverflow, where the poster is asked to sort multiple arrays "in parallel" based on data in one of those arrays.

Sort 2d C++ array by first element in subarray

Use a std::vector of std::vector as your container and the sort becomes much easier to do with. Not only is std::vector the preferred container for C++ but using STL functions on it is way simpler and direct , without any substantiable overhead.

Define your data as

std::vector<std::vector<int>> umbrellas{
    {5, 6},
    {2, 7},
    {9, 20}
};

Now you can use a custom comparator lambda that takes in two vector element references and returns True when the first element of the above vector is smaller than that of the one below.

std::sort(umbrellas.begin(),
          umbrellas.end(),
          [](const std::vector<int> &above, const std::vector<int> &below)
          {
              return (above[0] < below[0]);
          });

And the output :

for (auto &&row : umbrellas) {
    for (auto element : row) {
        std::cout<< element<< " ";
    }
    std::cout<< "\n";
}

2 7 
5 6 
9 20

---

Taking this to C++20 it's even easier:

std::ranges::sort(umbrellas, std::less(),
     [](const auto &v) { return v[0];});

Sort subarrays according to their first element

Assuming Grid implements Comparable<Grid>, sort each array and add to 2d-array. Then sort that array of arrays of grids using Arrays.sort(Grid[][], GridArrayComparator), where GridArrayComparator looks for example like:

class GridArrayComparator implements Comparator<Grid[]> {
   public int compare(Grid[] grids1, Grid[] grids2) {
       if (grids1.length > 0 && grids1.length > 0) {
           return grids1[0].compareTo(grids2[0]);
       } else if (grids1.length > 0) {
           return 1;
       } else if (grids2.length > 0) {
           return -1;
       } else {
           return 0;
       }
   }
}

Then copy 2-d array to 1-d array.

Alphabetically sort array by sub-array's first element

<?php 

$array = array(
     0 => array('a', '1', '2', '3', '4', 'test'),
     1 => array('c', '1', '2', '3', '5', 'test'),
     2 => array('b', '1', '3', '4', '5', 'test'),
);

array_multisort(array_column($array, 1), SORT_ASC, $array);

print_r($array);

Output:

Array
(
    [0] => Array
        (
            [0] => a
            [1] => 1
            [2] => 2
            [3] => 3
            [4] => 4
            [5] => test
        )

    [1] => Array
        (
            [0] => b
            [1] => 1
            [2] => 3
            [3] => 4
            [4] => 5
            [5] => test
        )

    [2] => Array
        (
            [0] => c
            [1] => 1
            [2] => 2
            [3] => 3
            [4] => 5
            [5] => test
        )

)

https://eval.in/633355

Sorting Subarrays in C Sorts Entire Array Instead?

I compiled your sort_cards() function (after providing the missing }), with GCC 7.2.0 on a Mac and the command line:

gcc -O3 -g -std=c11 -Wall -Wextra -Werror -Wmissing-prototypes \
    -Wstrict-prototypes -c cards53.c

With these options (the critical one is -Wextra), it warns immediately:

cards53.c:31:34: error: comparison of unsigned expression >= 0 is always true [-Werror=type-limits]
         for (size_t j = i - 1; j >= 0; j--)

That indicates a serious problem. Especially as on the first iteration of the outer loop, i is 0, so i - 1 is a very big number. Frankly, your claim that the function will sort an entire array successfully is bogus. It won't. And I don't run code that won't compile with the command line shown.

If you fix that function, your code is then OK. I used:

#include <stdio.h>

#define n_H 10
#define n_C 104

static inline void card_swap(char *deck, int i1, int i2)
{
    char t = deck[i1];
    deck[i1] = deck[i2];
    deck[i2] = t;
}

static void sort_cards(char *cards, size_t n)
{
    for (size_t i = 1; i < n; i++)
    {
        for (size_t j = i; j-- > 0; )
        {
            if (cards[j] > cards[j + 1])
                card_swap(cards, j, j + 1);
            else
                break;
        }
    }
}

static void sort_hands(char *deck, size_t n_P)
{
    for (size_t i_P = 0; i_P < n_P; i_P++)
        sort_cards(deck + i_P * n_H, n_H);
}

static void dump_hands(const char *tag, const char *deck, size_t n_P)
{
    printf("%s:\n", tag);
    for (size_t p = 0; p < n_P; p++)
    {
        printf("Player %zu:", p + 1);
        const char *hand = deck + p * n_H;
        for (int i = 0; i < n_H; i++)
            printf(" %3d", hand[i]);
        putchar('\n');
    }
}

int main(void)
{
    char deck[n_C] =
    {
        74,  31,  53,  46,  42,  75,  72,  77,  70,  49,
        76,  86,  99,  78,  11,  94,  61,  14,  41,  87,
        40,  26,  92,   5,   9,   3,  66,  63, 101,  98,
    };
    int n_P = 3;
    dump_hands("Before", deck, n_P);
    sort_hands(deck, n_P);
    dump_hands("After", deck, n_P);
    return 0;
}

The array is initialized with the sample data you gave; the residue is all zeros, but that doesn't matter for this exercise.

Sample output:

Before:
Player 1:  74  31  53  46  42  75  72  77  70  49
Player 2:  76  86  99  78  11  94  61  14  41  87
Player 3:  40  26  92   5   9   3  66  63 101  98
After:
Player 1:  31  42  46  49  53  70  72  74  75  77
Player 2:  11  14  41  61  76  78  86  87  94  99
Player 3:   3   5   9  26  40  63  66  92  98 101

Inspection shows that the each sub-array is correctly sorted.

Sorting an array using subscripts without moving array elements

Ok. lets start with a simple example, a list of 4 elements to sort, lets go through the process of what your function needs to do and how it does it in terms of linked lists:

#->[3]->[1]->[4]->[2]->$

Ok, so here # is your pointer to the first element, in this case [3], which has a pointer to the second, and so on. I shall use ->$ as a null pointer (not pointing to anything) and ->* as a 'I don't care' pointer (where a pointer may exist, but want to show a conceptional break in the list)

We now perform multiple passes to merge these into one sorted list.

This is the first pass, so we treat it as if we have multiple lists of length 1:

#->* [3]->* [1]->* [4]->* [2]->*

In reality, these remain linked for now, but this is the conceptional model.

so what to we need 'know' at this time?

1. the end of the list before list #1
2. reference to beginning of list #1
3. reference to beginning of list #2
4. reference to item after list #2

Then we merge the two sublists (2) and (3) onto the end of (1), by taking the minimum of the heads of the lists, detaching that, and ammending it to (1), moving onto the next value in that list if it exists

conceptional

//sublists length 1. we'll work on the first pair
#->* [3]->* [1]->* [4]->* [2]->*  

//smallest element from sublists added to new sublist
#->* [3]->*        [4]->* [2]->*  //
     [1]->*

//above repeated until sublists are both exhausted
#->*               [4]->* [2]->*
     [1]->[3]->*

//we now have a sorted sublist
#->* [1]->[3]->*   [4]->* [2]->*

actual

//(1-4) are pointers to the list as per description above
#->[3]->[1]->[4]->[2]->$
|   |    |    |
1   2    3    4

//set the end of the lists (2) and (3) to point to null, so 
//when we reach this we know we have reached the end of the 
//sublist (integrity remains because of pointers (1-4)
#->* [3]->$ [1]->$ [4]->[2]->$
|     |      |      |
1     2      3      4

//the smallest (not null) of (2) and (3) is referenced by (1), 
//update both pointers (1) and (2) or (3) to point to the next
//item
#->[1]->* [3]->$ $ [4]->[2]->$
    |       |    |  |
    1       2    3  4

//repeat until both (2) and (3) point to null   
#->[1]->[3]->* $ $ [4]->[2]->$
         |     | |  |
         1     2 3  4

We now have a linked list with the first sublist in it. Now, we keep track of (1), and move on to the second pair of sublists, starting with (4), repeating the process.

Once (2),(3) and (4) are all null, we have completed the pass. We now have sorted sublists, and a single linked list again:

#->[1]->[3]->[2]->[4]->$ $ $ $
                   |     | | |
                   1     2 3 4

Now we do the same, only with sublists twice the length. (and repeat)

The list is sorted when sublist length >= length of linked list.

At no point during this have we actually moved any data around, only modified the links between the items in the linked list.

This should give you a solid idea of what you need to do from here.

I've extended this to some actual code:

See it here

I wrote it in python, so it satisfies your desire for pseudocode, as it isn't code for the language that you are writing in.

pertinent function with additional comments:

def mergesort(unsorted):
  #dummy start node, python doesn't have pointers, but we can use the reference in here in the same way
    start = llist(None)
    start.append(unsorted)
    list_length = unsorted.length()
    sublist_length = 1
    #when there are no sublists left, we are sorted
    while sublist_length < list_length:
        last  = start
        sub_a = start.next
        #while there are unsorted sublists left to merge
        while sub_a:
            #these cuts produce our sublists (sub_a and sub_b) of the correct length
            #end is the unsorted content
            sub_b = sub_a.cut(sublist_length)
            end   = sub_b.cut(sublist_length) if sub_b else None
            #I've written this so is there are any values to merge, there will be at least one in sub_a
            #This means I only need to check sub_a
            while sub_a:
                #sort the sublists based on the value of their first item
                sub_a, sub_b = sub_a.order(sub_b)
                #cut off the smallest value to add to the 'sorted' linked list
                node = sub_a
                sub_a = sub_a.cut(1)
                last = last.append(node)
                #because we cut the first item out of sub_a, it might be empty, so swap the references if so
                #this ensures that sub_a is populated if we want to continue
                if not sub_a:
                  sub_a, sub_b = sub_b, None
            #set up the next iteration, pointing at the unsorted sublists remaining
            sub_a = end
        #double the siblist size for the next pass
        sublist_length *=2
    return start.next

How to store the original indices of array after sorting the array in ascending ordering

The issue is that you are sorting the original array_dist when you shouldn't be sorting this at all.

You should only sort the index_array based on the comparison of the array_dist values :

// Compare values at `array_dist`, using the index array 
if (array_dist[index_array[i]] > array_dist[index_array[j]])
{
   // the indices need to be swapped
   x = index_arr[i];
   index_arr[i] = index_arr[j];
   index_arr[j] = x;
}         

Once you have this, then to print out the array_dist in sorted order:

for (int i = 0; i < 4344; ++i)
{
   cout << index_arr[i] << " : "
       << array_dist[index_arr[i]] << endl;
}

You use the index_array as a subscript within the original array.

---

Related Topics