sorting array of strings in lexicographic order

• (2 Pages)
• 1
• 2

22 Replies - 30650 Views - Last Post: 23 July 2010 - 09:16 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=182719&amp;s=6ad8ee32b3ddc64b19eaca27b111001a&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 j1_osu2002

Reputation: 2
• Posts: 57
• Joined: 09-February 09

sorting array of strings in lexicographic order

Posted 22 July 2010 - 09:18 AM

I'm having a hard time figuring out what I am doing wrong here. What I am trying to do is create a bubble sort algorithm that sorts an array of strings in lexicographic order. Here is what I have coded:

```public static void main(String[] args)
{
String[] array = new String[] {"Jenny", "Rob", "Dereck", "Mike", "Kristin"};
for (int i = left; i < right - 1; i++)
{
for (int j = left; j < right - 1; j++)
{

if (array[j].compareTo(array[j+1]) > 0)
{
String temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
System.out.println(array[i]);
}
}

```

Any help is greatly appreciated!

Is This A Good Question/Topic? 0

Replies To: sorting array of strings in lexicographic order

#2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,170
• Joined: 27-December 08

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 09:43 AM

It doesn't look like you've declared the variables left and right. Are you getting any other errors or problems? If so, please specifically describe them.

#3 cfoley

• Cabbage

Reputation: 2244
• Posts: 4,722
• Joined: 11-December 07

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 09:45 AM

You need to declare left and right.

```int left = 0;
int right = array.length
```

You can also make an improbement. After the first pass, the last element is guaranteed to be in the right position. After the second pass, the last two are in the right position.

for (int j = left; j < right - 1 - i; j++)

This post has been edited by cfoley: 22 July 2010 - 09:47 AM

#4 m-e-g-a-z

• Winning

Reputation: 497
• Posts: 1,453
• Joined: 19-October 09

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 09:50 AM

This line here String[] array = new String[] {"Jenny", "Rob", "Dereck", "Mike", "Kristin"}; should be String[] array = {"Jenny", "Rob", "Dereck", "Mike", "Kristin"};. Where have you initialised variables left and right? You have got alot of syntax errors. Have a look at the famous bubble sort algorithm as your current code is initally going to do n swaps across 1 iteration which will give you wrong results. You will need to create a boolean and set it to false having a while loop while(..false) and then set the boolean to true inside the while loop at the first line. Once there is a swap if (array[j].compareTo(array[j+1]) > 0) .., set the boolean to false. Im on my phone at the moment so sorry I could not have provided a much detailed explination with proper pseudo code. Edit - while loop solution having a single for loop like this for(int i = 0;i < array.length -1; i++) and then comparing array[i] with array[i+1]

This post has been edited by m-e-g-a-z: 22 July 2010 - 09:54 AM

#5 cfoley

• Cabbage

Reputation: 2244
• Posts: 4,722
• Joined: 11-December 07

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 09:58 AM

Megaz, his sorting code is absolutely fine, as is his array declaration. The new String[] part isn't necessary when doing an initial assignment, but it's not wrong either.

There IS another bug but that is to do with displayijng the results.

To fix it, delete your println. Them, after your double loop, you need another loop to go through the array and print out each line.

#6 m-e-g-a-z

• Winning

Reputation: 497
• Posts: 1,453
• Joined: 19-October 09

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 10:11 AM

Your right, damn these blackberrys are difficult when reading code, I thought the array declaration had a fixed array size. I've always liked the while loop solution for some reason - personal preference.

#7 j1_osu2002

Reputation: 2
• Posts: 57
• Joined: 09-February 09

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 10:29 AM

m-e-g-a-z, on 22 July 2010 - 03:50 PM, said:

This line here String[] array = new String[] {"Jenny", "Rob", "Dereck", "Mike", "Kristin"}; should be String[] array = {"Jenny", "Rob", "Dereck", "Mike", "Kristin"};. Where have you initialised variables left and right? You have got alot of syntax errors. Have a look at the famous bubble sort algorithm as your current code is initally going to do n swaps across 1 iteration which will give you wrong results. You will need to create a boolean and set it to false having a while loop while(..false) and then set the boolean to true inside the while loop at the first line. Once there is a swap if (array[j].compareTo(array[j+1]) > 0) .., set the boolean to false. Im on my phone at the moment so sorry I could not have provided a much detailed explination with proper pseudo code. Edit - while loop solution having a single for loop like this for(int i = 0;i < array.length -1; i++) and then comparing array[i] with array[i+1]

This is what I ended up doing. However when I compile I get an error that says "cannot find symbol - variable i". I'm not sure why it says that when clearly it's defined in the for loop.

```public static void main(String[] args)
{
String[] array = {"Jenny", "Rob", "Dereck", "Mike", "Kristin"};
boolean didSwap = true;
int right = 0;
int left = 0;
int last = right - 1;
while (didSwap)
{
didSwap = false;

for (int i = left; i < last - 1; i++)
{
if (array[i].compareTo(array[i+1]) > 0)
{
didSwap = true;
String temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
System.out.println(array[i]);
}
}

```

#8 NoobKnight

Reputation: 49
• Posts: 238
• Joined: 14-July 09

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 10:35 AM

```for(int i=0 {  // <-- declared
// can only use it in this scope
}
```

You can't access i outside your forloop, it was declared in the forloop and and can only be used there.

#9 Handler

Reputation: 15
• Posts: 199
• Joined: 01-April 10

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 10:40 AM

Make a new for loop and loop through the array printing each one

```for(int temp = 0; temp<array.length(); temp++)
{
System.out.println(array[temp]);
}

```

#10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,170
• Joined: 27-December 08

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 11:01 AM

As you initialize right = 0, but int last = right - 1;. So your inner loop will never execute b/c left = 0 is never less than last-1 = -2.

#11 j1_osu2002

Reputation: 2
• Posts: 57
• Joined: 09-February 09

Re: sorting array of strings in lexicographic order

Posted 23 July 2010 - 08:11 AM

macosxnerd101, on 22 July 2010 - 05:01 PM, said:

As you initialize right = 0, but int last = right - 1;. So your inner loop will never execute b/c left = 0 is never less than last-1 = -2.

Maybe you can help me out. How do I correct this?

#12 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,170
• Joined: 27-December 08

Re: sorting array of strings in lexicographic order

Posted 23 July 2010 - 09:13 AM

Let's analyze this. If we need to access arr[i] and arr[i+1], what would cause this to go out of bounds for arr[i+1]? A value of arr.length, right. So if i can hold the value arr.length-1, you will get an IndexOutOfBoundsException. You will want to go from i = 0 to arr.length-2, that way the largest value arr[i+1] can take on is arr.length-1.

#13 j1_osu2002

Reputation: 2
• Posts: 57
• Joined: 09-February 09

Re: sorting array of strings in lexicographic order

Posted 23 July 2010 - 01:00 PM

macosxnerd101, on 23 July 2010 - 03:13 PM, said:

Let's analyze this. If we need to access arr[i] and arr[i+1], what would cause this to go out of bounds for arr[i+1]? A value of arr.length, right. So if i can hold the value arr.length-1, you will get an IndexOutOfBoundsException. You will want to go from i = 0 to arr.length-2, that way the largest value arr[i+1] can take on is arr.length-1.

Ok I went ahead and made some changes. However, the loop won't stop executing and it's not putting the string in lexicographic order. Here is what I did:

```public static void main(String[] args)
{
String[] array = {"Jenny", "Rob", "Dereck", "Mike", "Kristin"};
boolean didSwap = true;
int last = array.length;

while (didSwap)
{
didSwap = true;

for (int i = 0; i < array.length - 2; i++)
{
if (array[i].compareTo(array[i+1]) > 0)
{
didSwap = true;
String temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
System.out.println(array[i]);
}
--last;
}
}

```

#14 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,170
• Joined: 27-December 08

Re: sorting array of strings in lexicographic order

Posted 23 July 2010 - 01:06 PM

You never set your boolean variable to false within the loop. Bubblesort assumes the array is sorted, unless told otherwise (you make a swap). Once it iterates without making a swap (and thus setting the boolean from false to true), it terminates.

#15 j1_osu2002

Reputation: 2
• Posts: 57
• Joined: 09-February 09

Re: sorting array of strings in lexicographic order

Posted 23 July 2010 - 01:36 PM

macosxnerd101, on 23 July 2010 - 07:06 PM, said:

You never set your boolean variable to false within the loop. Bubblesort assumes the array is sorted, unless told otherwise (you make a swap). Once it iterates without making a swap (and thus setting the boolean from false to true), it terminates.

I changed it to false. When I run the program it prints out:

Jenny
Dereck
Mike
Dereck
Jenny
Mike
Dereck
Jenny
Mike

I'm not understanding why it's not doing it in alphabetical order. Am I missing something?