How to sort this array this way in python?

Question

You are given an array, for example:

arr = [['AB','KR','EH'],['EE','DD','PS'],['GH','LM','XK']]

array printed by rows

Then, through a function, you have to get this:

sorted array printed by rows

The array must be sorted ascending as a whole and not only by rows. You can not create new arrays for this. You have to do it in place.

I tried to find a way to do this with no new arrays but I could not. This is my code, it certainly sorts the array but creates a new array.

def sortArray(arr): #n : filas,columnas
    sorted_arr = []
    for j in arr:
        sorted_arr.extend(j)

    return sorted(sorted_arr)

In Python these are lists, not arrays. Arrays are in the `numpy` and `array` modules. — Barmar, Mar 28 '23 at 21:48
Never mind, I didn't see `KR` in the last row. I'm also confused. Shouldn't that be between `GH` and `LM`? — Barmar, Mar 28 '23 at 21:52
It is as you said before, Barmar. You have to order it lexicographically. — Eddie Esqui., Mar 28 '23 at 21:54
Are you ever going to explain the sort order, why KR shall be there? — Kelly Bundy, Mar 28 '23 at 22:08
@KellyBundy You have to order it lexicographically. KR should be between GH and LM. — Eddie Esqui., Mar 28 '23 at 22:09
How is KR supposed to be between GH and LM in that image? In what order shall I traverse the grid for that? And your own code doesn't even produce a 2D list. — Kelly Bundy, Mar 28 '23 at 22:11

score 1 · Answer 1 · answered Mar 28 '23 at 22:22

You can perform a selection sort, using indexes from 0 to N * N - 1 where N is the length of the array (since it's square). The corresponding element in the actual array for each index can be calculated by dividing and taking the remainder.

def sortArray(arr):
    n = len(arr)
    for i in range(n * n):
        m = i
        for j in range(i + 1, n * n):
            if arr[j // n][j % n] < arr[m // n][m % n]:
                m = j
        arr[i // n][i % n], arr[m // n][m % n] = arr[m // n][m % n], arr[i // n][i % n]

score 0 · Answer 2 · answered Mar 28 '23 at 21:57

0

Try:

from itertools import islice

arr = [["AB", "KR", "EH"], ["EE", "DD", "PS"], ["GH", "LM", "XK"]]

i = iter(sorted(v for l in arr for v in l))
for l in arr:
    l[:] = islice(i, 0, len(l))

print(arr)

Prints:

[
  ["AB", "DD", "EE"], 
  ["EH", "GH", "KR"], 
  ["LM", "PS", "XK"]
]

answered Mar 28 '23 at 21:57

Andrej Kesely

168,389
15
48
91

Not the expected result and creates a new list. – Kelly Bundy Mar 28 '23 at 21:58
@KellyBundy It doesn't create new list. And the result is correct based of comment *"...You have to order it lexicographically..."* – Andrej Kesely Mar 28 '23 at 21:59
`sorted` creates a new list and you know it. – Kelly Bundy Mar 28 '23 at 22:00
@KellyBundy It's just temporary variable. The result is stored in existing list `arr` – Andrej Kesely Mar 28 '23 at 22:00
Doesn't matter. – Kelly Bundy Mar 28 '23 at 22:01
You're interpreting it as "must not return a new list", but I think the whole point is that it's supposed to avoid any list allocation at all. – Barmar Mar 29 '23 at 14:00

B Remmelzwaal · Answer 3 · 2023-03-28T22:43:17.800

0

Well, if you can't create a new list and it has to be done in-place, you could always just do an exchange sort:

arr = [['AB','KR','EH'],['EE','DD','PS'],['GH','LM','XK']]

def sortedArray(arr):
    height = len(arr)
    width = len(arr[0])
    for left in range(height*width):
        for right in range(left+1, height*width):
            li, lj = left//height, left%width
            ri, rj = right//height, right%width
            if arr[li][lj] > arr[ri][rj]:
                arr[li][lj], arr[ri][rj] = arr[ri][rj], arr[li][lj]
    
    return arr

print(sortedArray(arr))

Output:

[
 ['AB', 'DD', 'EE'], 
 ['EH', 'GH', 'KR'], 
 ['LM', 'PS', 'XK']
]

Looks messy, feels dumb, but at least it does meet the requirements.

edited Mar 28 '23 at 22:43

answered Mar 28 '23 at 22:22

B Remmelzwaal

1,581
2
4
11

You can make it less messy if you use a translator like I did in my second solution now. – Kelly Bundy Mar 28 '23 at 23:15
While I do agree it's more elegant, I feel it's also getting into a grey area concerning the no allocations for new lists, since you are creating a whole class. Wonder if that would be allowed under the rules. – B Remmelzwaal Mar 28 '23 at 23:20
1

It's not storing anything, though. And takes O(1) space no matter how large the data is. Not much different than using a few variables and integer objects. – Kelly Bundy Mar 28 '23 at 23:24

Kelly Bundy · Answer 4 · 2023-03-28T23:29:56.330

(Result is based on their comments, i.e., not exactly as shown in the incorrect image. And using that they said it's always square.)

Solution 1: Odd insertion sort algorithm

a = [['AB','KR','EH'],['EE','DD','PS'],['GH','LM','XK']]

r = range(len(a))
for i in r:
  for j in r:
    for I in r:
      for J in r:
        if a[i][j] < a[I][J]:
          a[i][j], a[I][J] = a[I][J], a[i][j]

print(a)

Output (Attempt This Online!):

[['AB', 'DD', 'EE'], ['EH', 'GH', 'KR'], ['LM', 'PS', 'XK']]

Solution 2: Ordinary insertion sort

Really ordinary. Just one-dimensional insertion sort. But on an object that translates the indices and gets/sets the values in the two-dimensional original:

def insertionSort(A):
  for i, a in enumerate(A):
    while i and a < A[i-1]:
      A[i] = A[i-1]
      i -= 1
    A[i] = a

def sortArray(A):
  class B:
    def __getitem__(_, i):
      return A[i//n][i%n]
    def __setitem__(_, i, value):
      A[i//n][i%n] = value
  n = len(A)
  insertionSort(B())
  return A

arr = [['AB','KR','EH'],['EE','DD','PS'],['GH','LM','XK']]
print(sortArray(arr))

Try it online!

How to sort this array this way in python?

4 Answers4

Solution 1: Odd insertion sort algorithm

Solution 2: Ordinary insertion sort