Numpyic way to sort an ndarray clockwise?

Question

I am trying to sort a numpy ndarray clockwise (in ascending order). You can understand it as taking all the values in the array, sort them, then lay them out in a clockwise spiral to a new array with the same shape. The directions of the clockwise spiral are shown below:

For example, say I have an array of

import numpy as np
a1 = np.array(([2, 4, 6],
               [1, 5, 3],
               [7, 9, 8]))

The expected output is

np.array([[1, 2, 3],
          [8, 9, 4],
          [7, 6, 5]])

If I have an array of

a2 = np.array(([2, 4, 6],
               [1, 5, 3],
               [7, 9, 8],
               [12, 11, 10]))

The expected output is

np.array([[1, 2, 3],
          [10, 11, 4],
          [9, 12, 5],
          [8, 7, 6]])

What I have tried so far

My idea is to track the row index x and the column index y of the moving iterator and the current index cur of the sorted flattened list sa. The number of rows to go through (lenr) and the number of columns to go through (lenc) are subtracted by 1 once the moving iterator passes lenr rows horizontally and lenc columns vertically. Here is the function that I managed to write:

def clockwise_sorted(a, key=None, reverse=False):
    nr, nc = a.shape
    res = a.tolist()
    sa = a.ravel().tolist()
    if key is None:
        sa.sort(reverse=reverse)
    else:
        sa.sort(key=key, reverse=reverse)
    res[0] = sa[:nc]
    cur, lenr, lenc = nc, nr - 1, nc - 1
    x, y = 0, nc - 1
    while (lenc > 0 and lenr > 0):
        # go down, then go left
        for _ in range(lenr):
            x += 1
            res[x][y] = sa[cur]
            cur += 1
        for _ in range(lenc):
            y -= 1
            res[x][y] = sa[cur]
            cur += 1      
        lenr -= 1
        lenc -= 1
        
        # go up, then go right
        for _ in range(lenr):
            x -= 1
            res[x][y] = sa[cur]
            cur += 1
        for _ in range(lenc):
            y += 1 
            res[x][y] = sa[cur]
            cur += 1
        lenr -= 1
        lenc -= 1
    return np.array(res)

For square matrices, my code works fine:

print(clockwise_sorted(a1))
#[[1 2 3]
# [8 9 4]
# [7 6 5]]
#%timeit 5.98 µs ± 413 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

But it doesn't work for non-square matrices:

print(clockwise_sorted(a2))
#[[ 1  2  3]
# [10 11  4]
# [ 9  9  5]
# [ 8  7  6]]

Clearly, it misses the 12 at [2,1].

Please note that I don't expect you to understand and fix my code. I don't like my code so much because I feel like there should be more numpyic ways to do this. Therefore, I want to see some numpyic solutions. However, it would be nice if someone can comment on what is wrong with my code.

Answer 1

You can use numpy.rot90 with recursion to rotate clockwise over the array. Sort the values of the array after changing to 1d and edit the values in the array by it

def rotate(matrix, arr):
    if not len(matrix):
        return
    matrix[0] = arr[:len(matrix[0])]
    rotate(np.rot90(matrix[1:]), arr[len(matrix[0]):])

a1 = np.array(([2, 4, 6],
                [1, 5, 3],
                [7, 9, 8]))

sorted_arr = sorted(a1.ravel())
rotate(a1, sorted_arr)
print(a1)

Output

[[1 2 3]
 [8 9 4]
 [7 6 5]]

Answer 2

This is likely hardly the numpyiest solution, but I think it's a neat Pythonic solution, being a generator function that yields spiral coordinates in clockwise order that's then used to index the numpy array (which has to be transposed twice to get the coordinates right, but that's peanuts...).

import numpy as np


def spiral_coords(w, h):
    maxx = w - 1
    maxy = h - 1
    minx = miny = 0

    while (minx, miny) != (maxx, maxy):
        for x in range(minx, maxx):  # right
            yield (x, miny)
        yield (maxx, miny)  # upper-right corner
        for y in range(miny + 1, maxy):  # down
            yield (maxx, y)
        yield (maxx, maxy)  # lower-right corner
        for x in range(maxx - 1, minx, -1):  # left
            yield (x, maxy)
        yield (minx, maxy)  # lower-left corner
        for y in range(maxy - 1, miny, -1):  # up
            yield (minx, y)
        minx += 1
        miny += 1
        maxx -= 1
        maxy -= 1
    yield (minx, miny)  # final point


def clockwise_sorted(a):
    a = a.T
    nr, nc = a.shape
    sa = a.ravel()
    sa.sort()
    res = np.zeros_like(a)
    for (x, y), v in zip(spiral_coords(nr, nc), sa):
        res[x, y] = v
    return res.T


a2 = np.array(
    [
        [2, 4, 6],
        [1, 5, 3],
        [7, 9, 8],
        [12, 11, 10],
    ]
)

print(a2)
print(clockwise_sorted(a2))

This outputs

[[ 2  4  6]
 [ 1  5  3]
 [ 7  9  8]
 [12 11 10]]
[[ 1  2  3]
 [10 11  4]
 [ 9 12  5]
 [ 8  7  6]]

If you don't necessarily need Numpy, you can also use the same generator to spiralize anything into e.g. a mapping of coordinates to letters:

coords = {(x, y): c for (x, y), c in zip(spiral_coords(6, 5), "Hello World! This is a spiral!")}

for y in range(5):
    print("".join(coords.get((x, y), " ") for x in range(6)))

outputs

Hello 
 is aW
sal! o
iripsr
hT !dl