sorting array of strings in lexicographic order

  • (2 Pages)
  • +
  • 1
  • 2

22 Replies - 17670 Views - Last Post: 23 July 2010 - 09:16 PM Rate Topic: -----

#1 j1_osu2002  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • 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  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,585
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1906
  • View blog
  • Posts: 3,952
  • 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

Was This Post Helpful? 0
  • +
  • -

#4 m-e-g-a-z  Icon User is offline

  • Winning
  • member icon


Reputation: 496
  • View blog
  • 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

Was This Post Helpful? 1
  • +
  • -

#5 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1906
  • View blog
  • Posts: 3,952
  • 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.
Was This Post Helpful? 1
  • +
  • -

#6 m-e-g-a-z  Icon User is offline

  • Winning
  • member icon


Reputation: 496
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#7 j1_osu2002  Icon User is offline

  • D.I.C Head

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

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 10:29 AM

View Postm-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]);
        }
    }


Was This Post Helpful? 0
  • +
  • -

#8 NoobKnight  Icon User is offline

  • D.I.C Head

Reputation: 51
  • View blog
  • Posts: 238
  • Joined: 14-July 09

Re: sorting array of strings in lexicographic order

Posted 22 July 2010 - 10:35 AM

Your i variable is outside your scope.
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.
Was This Post Helpful? 0
  • +
  • -

#9 Handler  Icon User is offline

  • D.I.C Head

Reputation: 15
  • View blog
  • 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]);
}


Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,585
  • 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.
Was This Post Helpful? 0
  • +
  • -

#11 j1_osu2002  Icon User is offline

  • D.I.C Head

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

Re: sorting array of strings in lexicographic order

Posted 23 July 2010 - 08:11 AM

View Postmacosxnerd101, 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?
Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,585
  • 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.
Was This Post Helpful? 0
  • +
  • -

#13 j1_osu2002  Icon User is offline

  • D.I.C Head

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

Re: sorting array of strings in lexicographic order

Posted 23 July 2010 - 01:00 PM

View Postmacosxnerd101, 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;
        }
    }


Was This Post Helpful? 0
  • +
  • -

#14 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,585
  • 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.
Was This Post Helpful? 0
  • +
  • -

#15 j1_osu2002  Icon User is offline

  • D.I.C Head

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

Re: sorting array of strings in lexicographic order

Posted 23 July 2010 - 01:36 PM

View Postmacosxnerd101, 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?
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2