Win a copy of Programmers Guide to Apache Thrift this week in the Open Source forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Devaka Cooray
  • Knute Snortum
  • Paul Clapham
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Ron McLeod
  • Piet Souris
  • Frits Walraven
Bartenders:
  • Ganesh Patekar
  • Tim Holloway
  • salvin francis

Sorting a 2 dimensional array alphabethically  RSS feed

 
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Guys,

New to Java and having some difficulty with an assignment, so any help appreciated.

Basically, I have a 2 dimensional array, which is a simple char matrix. I now need to sort this alphabetically by the first row. In doing this, I need to transpose the columns also.

So for example, my 2 dimensional array ends up as follows

J  A  V  A
F  G V  X
X  A  D  F
G  V  X  G

which I want to arrange  like below,  with each column sorted alphabetically....

A  A  J  V
G  X  F V
A  F  X  D
V  G  G X
 
Marshal
Posts: 64471
225
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

Please work out how you would do that on paper. The process of getting a computer to do the rearrangement is exactly the same as you would do on paper.
Remind me: do you have an array containing four enclosed arrays, each representing a row?
I presume you have written yourself a utility class with this sort of method in:-There is a good reason why I wrote so much documentation comment; it is an important part of the class.

It is useful to know how sorting algorithms work, and you are here mirroring the sorting onto other objects (the other arrays), but at work nobody writes their own sort algorithms and nobody likes parallel arrays.
 
Michael Curley
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Campbell,

Thanks for your reply. I will try and follow your advice.
I'm a total novice, and don't believe I know about the standard swap technique either,
The 2D array is actually the result of arranging a string which has being input by the user. The string is converted to uppercase, and into a char array(one dimensional)....This is then arranged into a 2D char[][] matrix, where the rows and column sizes are determined by a codeword, and the length of the string which has being input.

The next step then, was what I am trying to achieve in my first post.....

Thank you for your advice thus far.
 
Bartender
Posts: 20721
124
Android Eclipse IDE Java Linux Redhat Tomcat Server
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The very first thing you need to do before designing an algorithm is to state it as concisely as you can.

I mis-read your mission about 3 times based on how it was described in messagee header and message body.

What you actually want to do is, given a matrix (2-dimensional array) of characters, take each column and arrange them by the ascending collating sequence of the character in the top row of that matrix.

The example, incidentally, was much appreciated.

To swap items there are certain tricks that can be done, including abusing certain machine-language instructions and sometimes being able to take advantage of someone else's previously-written (and debugged, we hope!) swap function. But in the end, the net effect is that given 3 items, A, B, and C, you can swap the values in A and B by C←A, A←B, then B←C. C is a temporary storage that can be re-used, so a single C can be used for all rows where columns are being swapped. Assuming, of course, that you don't have a parallel processor that can do every row at the same time. But since this is general Java, we'll take it as a given that you have to do things the hard way: linearly.
 
Michael Curley
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Tim,

Thank you for your reply.
Your interpretation was spot on. I understand that a big part of learning how to write good code is being able to describe concisely and accurately what you are trying to do, and I know I am a long way from being able to do that at the moment.
Some good advice, thank you.
 
Rancher
Posts: 427
6
Fedora IntelliJ IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A  A  J  V
G  X  F V
A  F  X  D
V  G  G X

Is only the first row sorted or what?  how is g x f v sorted?  you do the left column then a g a v isn't sorted either.   How are they supposed to be sorted?
 
Michael Curley
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Al,

Yeah as was already pointed out above, my statement wasn’t accurate or concise enough. I couldn’t put it better than this.......

“What you actually want to do is, given a matrix (2-dimensional array) of characters, take each column and arrange them by the ascending collating sequence of the character in the top row of that matrix”
 
Campbell Ritchie
Marshal
Posts: 64471
225
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rather different approach. Convert your 4×4 matrix from arrays representing the rows to arrays representing the columns. Sort the arrays by comparing their first elements only. Convert it back to rows.
Beware: Find out what it means for a sorting algorithm to be stable. If you have a stable algorithm, the column AGAV will always appear left of AXFG. If your algorithm isn't stable, it is possible for AXFG to appear left of AGAV. This method says it uses a stable algorithm.
 
Saloon Keeper
Posts: 3250
128
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Or, for something completely different: if your first row = "b a d c", and you sort it, then the original indices (0 1 2 3) will now be 1 0 3 2. What does that mean for the other rows?
 
Tim Holloway
Bartender
Posts: 20721
124
Android Eclipse IDE Java Linux Redhat Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:Or, for something completely different: if your first row = "b a d c", and you sort it, then the original indices (0 1 2 3) will now be 1 0 3 2. What does that mean for the other rows?

Michael Curley wrote:take each column...



Campbell Ritchie wrote:Rather different approach. Convert your 4×4 matrix from arrays representing the rows to arrays representing the columns. Sort the arrays by comparing their first elements only. Convert it back to rows.



That's rather like going from Leeds to Manchester via Hyderabad.

The whole thing can be sorted in-place using a single intermediate value. For a small array, simply bubble-sorting the columns would do and is a very simple algorithm.  For wider arrays, you could always extract the first row into a sorted vector of column indexes and then only have to exchange columns once.

There's no benefit to transforming the matrix as a whole.
 
Campbell Ritchie
Marshal
Posts: 64471
225
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:. . . That's rather like going from Leeds to Manchester via Hyderabad. . . . .

But our local travel website would send you via Lagos, too. Point taken.
 
Piet Souris
Saloon Keeper
Posts: 3250
128
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmmm...

if it were me, then I would produce a very simple int[] Comparator (that compares on the first elements), and do a sort on the transpose of the matrix.

But this is the Beginners Forum, and I don't think this exercise is easy at all. I would not use terms like 'very easy'. Let's wait for Michael to hear what he thinks.
 
Tim Holloway
Bartender
Posts: 20721
124
Android Eclipse IDE Java Linux Redhat Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have no idea why the idea of swapping the rows and columns just to sort the columns seems to be so popular.  
 
Campbell Ritchie
Marshal
Posts: 64471
225
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:I have no idea why the idea of swapping the rows and columns just to sort the columns seems to be so popular.  

It gets you out of parallel arrays, but I take your point that it is not a good solution.
 
Tim Holloway
Bartender
Posts: 20721
124
Android Eclipse IDE Java Linux Redhat Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Tim Holloway wrote:I have no idea why the idea of swapping the rows and columns just to sort the columns seems to be so popular.  

It gets you out of parallel arrays, but I take your point that it is not a good solution.


Actually, I never knew I was even in any parallel arrays.

Come to think of it, this would be a wonderful thing to do in the APL programming language, where the whole operation would probably take about 5 characters of what looked like gang grafitti.
 
Campbell Ritchie
Marshal
Posts: 64471
225
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:. . . . Actually, I never knew . . .

Maybe it's me in a parallel universe.
 
Michael Curley
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:Or, for something completely different: if your first row = "b a d c", and you sort it, then the original indices (0 1 2 3) will now be 1 0 3 2. What does that mean for the other rows?



This was my first approach. So I came up with a method that assigns numbers to letters in the "codeword" from A-Z, and as as you say it converts (0 1 2 3) to (1 0 3 2) in this example. The reason I went down this route is because the program takes in the "codeword" from the user, so the length of each row, although 4x in the example given in my first post, with JAVA as the codeword, could be much larger depending upon which "codeword" the user decides to use. So if, for example, the uses decides to use "Apples" as the codeword, the matrix size will be (6 x "X"), where X will be a function of some other Plaintext input....(and the method will convert(0 1 2  3 4  5) to (0 3 4 2 1 5). I understand that I now need to arrange each row based on these indicies, but I haven't quite figured that bit out yet.

I am also afraid the code I am writing may not be the most efficient, and I AM sure there are much easier approaches to the problem. Any Takers?
 
Michael Curley
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:Hmmm...

if it were me, then I would produce a very simple int[] Comparator (that compares on the first elements), and do a sort on the transpose of the matrix.

But this is the Beginners Forum, and I don't think this exercise is easy at all. I would not use terms like 'very easy'. Let's wait for Michael to hear what he thinks.



This sounds interesting, but I am unfamiliar with this approach. I need to find out more information as to how this works.......
 
Piet Souris
Saloon Keeper
Posts: 3250
128
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Michael Curley wrote: (...) This was my first approach.


hi Michael,

well, it takes just one line of code to get the indices, after sorting the letters of the code word, but that involves some methods that are probably unfamiliar to you at this moment.

So, if you have a codeword with length L, then create an array A of length L, and initialize it with 0, 1, 2, ..., L - 1.
Now, if you sort your codeword and you swap charAt(i) with charAt(j), then also swap A[i] and A[j]. When done, the A array contains the sorted indices. Now, for each int[] row of your 2D array, make sure that element[i] will be equal to element[A[i]]. Be careful not to overwrite elements, though.
 
Piet Souris
Saloon Keeper
Posts: 3250
128
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Hanolloway wrote:I have no idea why the idea of swapping the rows and columns just to sort the columns seems to be so popular.  


Well, first of all you need a method that retrieves the columns. Then you must sort these somehow, Lastly, you need to transform these sorted columns back into a [][]. Using rows is so much simpler. And if I misunderstood you, please elaborate how you would do it.

What I had in mind (but instead of an [][], I have a Matrix class with the suitable methods) is:

I fail to see why this is not a good method, since it does exactly what you describe (again, if I understood correctly).
But this is not exactly a Beginners way, and all methods proposed sofar are not easy.
 
Tim Holloway
Bartender
Posts: 20721
124
Android Eclipse IDE Java Linux Redhat Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Take the first row of the matrix, This is your sort key set. Thus, 'J', 'A', 'V', 'A' could result in the index sequence 1, 3, 0, 2, assuming that equal key indexes get assigned in left-to-right order.

Armed with this magic decoder card, you can then do column swaps: column 0 with column 2, column 3 with column 1. A column swap is just a simple loop function that given two column indexes and an in-place matrix to be organized enumerates the rows of the matrix and swaps the contents of the cells at those column locations. No need to copy the matrix out and in again and only a single intermediate storage element is required. Cases where both indexes are for the same column can be short-circuited, since they effectively do nothing.

I can see where maybe the matrix transform might be less lines of code, but it's trickery in that the means used isn't directly a consequence of the problem definition and thus, like the time-honored stunt of using XOR to exchange 2 values isn't as universal a solution. And could potentially have side-effects. Plus, I've got an evil suspicion that if you defined your sort callbacks and maybe exploited a lambda or 2, you could probably do the column sort in little code and no transpose.

But regardless, this is supposed to be a general problem, not an advanced one, so advanced solutions are probably going to simply annoy the instructor.
 
Michael Curley
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:

Michael Curley wrote: (...) This was my first approach.


hi Michael,

well, it takes just one line of code to get the indices, after sorting the letters of the code word, but that involves some methods that are probably unfamiliar to you at this moment.

So, if you have a codeword with length L, then create an array A of length L, and initialize it with 0, 1, 2, ..., L - 1.
Now, if you sort your codeword and you swap charAt(i) with charAt(j), then also swap A[i] and A[j]. When done, the A array contains the sorted indices. Now, for each int[] row of your 2D array, make sure that element[i] will be equal to element[A[i]]. Be careful not to overwrite elements, though.



Sorry, got sidetracked with other stuff last few days....

Thank you for all your help guys....
 
Piet Souris
Saloon Keeper
Posts: 3250
128
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Michael,

was on vacation without internet, just got back. Glad we could help.

This is the one-liner that I mentioned, but on second thought the line was way too long, so I split it over three lines. .
 
Michael Curley
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:hi Michael,

was on vacation without internet, just got back. Glad we could help.

This is the one-liner that I mentioned, but on second thought the line was way too long, so I split it over three lines. .

Thank you so much for all your help.......
 
Sheriff
Posts: 6738
466
BSD Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Michael, hi.

What the output supposed to be if the matrix were:
A  A  A  A
Z  Y  X  W
X  A  D  F
G  V  X  G

>?
 
Michael Curley
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:Michael, hi.

What the output supposed to be if the matrix were:
A  A  A  A
Z  Y  X  W
X  A  D  F
G  V  X  G

>?



Hi Liutauras,

In that case the matrix should not change. But I think I know what you are getting at, i.e. having a stable sort algorithm.
As the first row is a code-word, it is possible that what you have described could well happen. I have tested my program using "AAAA" as a codeword, and
am happy to report that nothing in the matrix changes.

On the other hand, I know my code could be more efficient, but I am a java newbie, and I am improving all the time, thanks in no small measure to excellent
websites like this.

Mike
 
The moustache of a titan! The ad of a flea:
ScroogeXHTML - small and flexible RTF to HTML converter library
https://coderanch.com/t/710903/ScroogeXHTML-RTF-HTML-XHTML-converter
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!