Undefined offset when using bubble sort on associative array

Question

I have this function to bubblesort an associative array based on a key input with the option to order by descending or ascending:

function bubbleSort($input, $key, $order){
    while (true){
        $end = false;
        $swapped = false;
        $idx = 0;
        do {
            $x = $input[$idx];
            $y = $input[$idx + 1];
            $x_param = $x[$key];
            $y_param = $y[$key];
            if (is_null($y)) {
                $end = true;
                continue;
            }
            if ($order == "desc"){
                if ($x_param < $y_param){
                    $input[$idx] = $y;
                    $input[$idx + 1] = $x;
                    $swapped = true;
                }
            }
            else{
                if ($y_param < $x_param){
                    $input[$idx] = $y;
                    $input[$idx + 1] = $x;
                    $swapped = true;
                }
            }
            $idx++;
        }
        while ($end == false);
        if ($swapped == false) {break;}
    }
    return $input;
}

In this example I'll use it on this associative array:

$array = array(
    array("Student Number" => 001, "Student name" => "David", "Student age" => 21),
    array("Student Number" => 002, "Student name" => "Jonas", "Student age" => 15),
    array("Student Number" => 003, "Student name" => "Katy", "Student age" => 23));

If I print it with print_r like this it will successfully sort and print it:

print_r(bubbleSort($array, "Student age", "desc"));

The problem is I get Notice: Undefined offset: 3 for the line containing $y = $input[$idx + 1];

As well as Notice: Trying to access array offset on value of type null for the line containing $y_param = $y[$key];

It does print a properly sorted asc array, so the code works.

But is there a way to phrase my code to not get the notice ?

Screenshot of the full output I get (with a lot of notices).

you can turn off error reporting, but you'd be better to fix the code with some checks to see if elements exist before you try to do stuff with them — imposterSyndrome, Oct 31 '20 at 12:28
Is there another way to sort an associative array with a reusable function? @Progrock — Justice 雨, Oct 31 '20 at 13:46

Progrock · Answer 1 · 2020-10-31T17:30:48.697

You can write your own comparison function with usort.

<?php

$array = array(
    array("Student Number" => 001, "Student name" => "David", "Student age" => 21),
    array("Student Number" => 002, "Student name" => "Jonas", "Student age" => 15),
    array("Student Number" => 003, "Student name" => "Katy", "Student age" => 23)
);   

function sort_array_by_key(&$array, $key, $order = 'ASC') {
    usort(
        $array, 
        fn($a, $b) => $order == 'ASC'
            ? $a[$key] <=> $b[$key]
            : $b[$key] <=> $a[$key]
    );
}

sort_array_by_key($array, 'Student name', 'DESC');
var_export($array);

Output:

array (
  0 => 
  array (
    'Student Number' => 3,
    'Student name' => 'Katy',
    'Student age' => 23,
  ),
  1 => 
  array (
    'Student Number' => 2,
    'Student name' => 'Jonas',
    'Student age' => 15,
  ),
  2 => 
  array (
    'Student Number' => 1,
    'Student name' => 'David',
    'Student age' => 21,
  ),
)

Removing the ascending/descending part to make for easier reading:

function sort_array_by_key_asc(&$array, $key) {
    usort(
        $array, function($a, $b) use ($key) {
            return $a[$key] <=> $b[$key];
        }
    );
}

(Short arrow functions absorb surrounding scope, so can be less verbose to author.)

From the usort manpage:

Note: If two members compare as equal, their relative order in the sorted array is undefined.

Note: This function assigns new keys to the elements in array. It will remove any existing keys that may have been assigned, rather than just reordering the keys.

(This is probably still technically a bubble sort?) – Progrock Oct 31 '20 at 14:50 — Progrock, Oct 31 '20 at 14:50

Progrock · Accepted Answer · 2020-10-31T17:22:00.670

To address your undefined indexes. You'll need to check if they exist.

So instead of:

        $x = $input[$idx];
        $y = $input[$idx + 1];
        $x_param = $x[$key];
        $y_param = $y[$key];
        if (is_null($y)) {
            $end = true;
            continue;
        }

You'll want something more like:

        if(!array_key_exists($idx + 1, $input)) {
            $end = true;
            continue;
        }
        $y = $input[$idx + 1];
        $x_param = $x[$key];
        $y_param = $y[$key];

However, note that you are not checking the validity of the other keys. And are assuming you have a zero based numeric indexed array with sequential indexes. So you may want further checks, or to use another way to traverse your array.

array_multisort

An alternative to your bubblesort approach could be to use array_multisort and lean on that to do the heavy lifting.

Extract a column of values based on your chosen key. Then the sort of that column can be used to sort the parent array.

The underlying algorithm is a quicksort (I believe). This is using SORT_REGULAR (the default) as a comparison. You'll want to look up the sort flags.

<?php
$array = array(
    'foo' => array("Student Number" => 001, "Student name" => "David", "Student age" => 21),
    'bar' => array("Student Number" => 002, "Student name" => "Jonas", "Student age" => 15),
    'baz' => array("Student Number" => 003, "Student name" => "Katy", "Student age" => 23)
);

function sort_by_key(&$array, $key, $reverse = false) {
    $column = [];
    foreach($array as $v) {
        $column[] = $v[$key] ?? null;
    }
    $order_flag = $reverse ? SORT_DESC : SORT_ASC;
    array_multisort($column, $order_flag, $array);
}

sort_by_key($array, 'Student age');
var_export($array);

Output:

array (
  'bar' => 
  array (
    'Student Number' => 2,
    'Student name' => 'Jonas',
    'Student age' => 15,
  ),
  'foo' => 
  array (
    'Student Number' => 1,
    'Student name' => 'David',
    'Student age' => 21,
  ),
  'baz' => 
  array (
    'Student Number' => 3,
    'Student name' => 'Katy',
    'Student age' => 23,
  ),
)

Invariably you'll find that if you have like values, you'll probably then want to further sort on another column, and so on.

You can swap out the foreach above for an array_column() call, and use multiple columns in array_multisort.

How can I sort arrays and data in PHP?

Thank you! This helped :) I ended up using array_column($array, $key) as well to tidy it up. — Justice 雨, Nov 01 '20 at 06:54

Undefined offset when using bubble sort on associative array

2 Answers2

array_multisort