1,105,644 Community Members

Bubble sorting a 2D array

Member Avatar
gyuunyuu
Newbie Poster
13 posts since Feb 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

I understand the concept of bubble sort and have no trouble implementing it, but I can't grasp the concept of doing it for 2D array. I've googled for some resources but I was unable to understand those codes.

So let's say I have a 2D char array with words (maximum of 7 char) from reading a text file which I figured out so far.
# 0 1 2 3 4 5
0 h e l l o

1 a x e

2 h e l p

3 n i c e

4 c a m p e r

5 o c e a n
.
.

If I am to sort the first char of each word, at what point would I have to consider sorting of the 2nd char? Can you guys give me some hint or pseudo code to help me out? Thanks.

Member Avatar
WaltP
Posting Sage w/ dash of thyme
9,363 posts since May 2006
Reputation Points: 2,905 [?]
Q&As Helped to Solve: 1,151 [?]
Skill Endorsements: 45 [?]
Team Colleague
 
0
 

Create a second array which contains indecies into your array of strings. For example:
ArrayList= "0hello", "1axe", "2help", "3nice", "4camper", "5ocean"
ArrayPntr= 0,1,2,3,4,5

Now as you test ArrayList use ArrayPntr to get at the values:

for i=0 to 5
    if ArrayList[ArrayPntr[i]] .GT. ArrayList[ArrayPntr[i+1]]
        swap only  ArrayPntr[i] and ArrayPntr[i+1]
Member Avatar
gyuunyuu
Newbie Poster
13 posts since Feb 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Create a second array which contains indecies into your array of strings. For example:
ArrayList= "0hello", "1axe", "2help", "3nice", "4camper", "5ocean"
ArrayPntr= 0,1,2,3,4,5

Now as you test ArrayList use ArrayPntr to get at the values:

for i=0 to 5
    if ArrayList[ArrayPntr[i]] .GT. ArrayList[ArrayPntr[i+1]]
        swap only  ArrayPntr[i] and ArrayPntr[i+1]

Thanks for the fast response! That's a one way to do it but I was looking for something of the nature of traditional bubble sort. Comparing and swapping words next to each other and go through all the passes while there's a same character being compared, move on to the 2nd position of char and do sorting there. What I understand from the code you provided, it's comparing entire word to word, rather than individual characters of each positions-compare 1st char of words, if the char is the same, compare 2nd char and so on.

Member Avatar
gyuunyuu
Newbie Poster
13 posts since Feb 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Nevermind. I just got an email from my TA and he said I can just compare by words. So your method will be suit my needs. Thanks again!

I'll leave this post unsolved for more suggestion. I'd like to see what other clever ways it will be out there. Thanks again guys.

Member Avatar
WaltP
Posting Sage w/ dash of thyme
9,363 posts since May 2006
Reputation Points: 2,905 [?]
Q&As Helped to Solve: 1,151 [?]
Skill Endorsements: 45 [?]
Team Colleague
 
0
 

Thanks for the fast response! That's a one way to do it but I was looking for something of the nature of traditional bubble sort. Comparing and swapping words next to each other and go through all the passes while there's a same character being compared, move on to the 2nd position of char and do sorting there. What I understand from the code you provided, it's comparing entire word to word, rather than individual characters of each positions-compare 1st char of words, if the char is the same, compare 2nd char and so on.

So in the standard BSort form, you need a K loop to look at individual characters. No biggie.

for i=0...
    for j=i...
        for k=.... ;; Loop through each character.

But, my way shows you a new and useful concept rather than simply adding to the known sort algorithm.

Member Avatar
Adak
Posting Virtuoso
1,711 posts since Jun 2008
Reputation Points: 419 [?]
Q&As Helped to Solve: 207 [?]
Skill Endorsements: 10 [?]
 
0
 

You can use a modified bubble sort if you make two changes:

When you find a char that needs to be swapped, you move the entire row of char's (the whole word).

Instead of comparing one column's char with the column next to it, like the regular bubble sort, you need to compare char's in the same column, but in adjacent rows.

IOW's, you "tilt" the array, over by 90 degrees, onto it's face, and make your comparisons, that way.

The sort through an index logic that WaltP mentioned above, is a great trick for any programmer to have in their toolbox, btw. It allows you to do some amazing tricks, since it keeps the original order of the input, yet allows you to SHOW the input, as if it was sorted, perfectly well (fast, too!).

Indexing is a powerful tool, any time you have a bunch of data, and need to organize it.

Question Answered as of 3 Years Ago by WaltP and Adak
You
This question has already been solved: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article