Recursive method to sort string lexographically

Page 1 of 1

7 Replies - 1612 Views - Last Post: 06 October 2012 - 06:18 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=294397&amp;s=3e4b046b903dda50ae7033a739c4f8de&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 bcsmith8

Reputation: 0
• Posts: 18
• Joined: 20-August 12

Recursive method to sort string lexographically

Posted 05 October 2012 - 07:49 AM

Hello all,

I have an assignment where I need to create a recursive method to sort a string lexicographically.

For example:
If the user enters "testing"
The output should be "eginstt"

My code is working, but we are graded on efficiency so I was wondering if there is a simpler way to do it that I'm missing.

I appreciate any feedback.

Thanks

```import java.util.Scanner;
public class HWTesting1 {

public static void main(String[] args) {
Scanner scan1 = new Scanner(System.in);
String input = scan1.nextLine();
System.out.println(recurse(input));
}

private static String recurse(String s)
{
//if the string is not null
if(s.length()>=1){
//create a string to add letters in order
String temp = s.substring(0,1);
//loop through each letter and compare it to the one that is currently earliest in order
for(int i=1;i<s.length();i++){
if(s.substring(i,i+1).compareTo(temp)<0)
temp = s.substring(i,i+1);
}
//return the letters first lexicographically and then call the method again with a revised string not containing those letters anymore
return handleDuplicates(s, temp) + recurse(s.replaceAll(temp,""));
}
return "";

}

private static String handleDuplicates(String s, String temp){
String n = "";
//loop through the string to find duplicates of the first letter lexicographically
for(int i=0;i<s.length();i++){
if(s.substring(i,i+1).equals(temp))
n+=s.substring(i,i+1);
}
return n;
}

}

```

Is This A Good Question/Topic? 0

Replies To: Recursive method to sort string lexographically

#2 Kakerergodt

Reputation: 89
• Posts: 201
• Joined: 01-May 12

Re: Recursive method to sort string lexographically

Posted 05 October 2012 - 08:26 AM

I think it would be more effective to split the string to a char array (string.toCharArray())

#3 Kinaces

Reputation: 78
• Posts: 230
• Joined: 04-October 12

Re: Recursive method to sort string lexographically

Posted 05 October 2012 - 09:36 AM

If case does not matter you could make the string ALL lowercase or ALL uppercase. Then turn it into a char array like suggest above. Since char's have a int value as well that already has everything in order. Just implement a recursive sorting algorithm. Then turn the char array back to a string. There you go. Won't be the most efficient thing in the world, but will definitely clean up a lot of code. This is just what first came in my head. I will get back to you if I come up with any other ideas.

#4 bcsmith8

Reputation: 0
• Posts: 18
• Joined: 20-August 12

Re: Recursive method to sort string lexographically

Posted 06 October 2012 - 11:19 AM

In the class that I'm in we haven't gone over arrays yet, so I probably won't use them. I probably should have mentioned the concepts we've gone over so far sorry about that. Data types, If statements, loops, and methods are really all we have covered so far which makes it way more restrictive! Thanks for both of your replies though. I will definitely be able to use that advice in the future.

#5 Ytry

Reputation: 16
• Posts: 120
• Joined: 25-July 12

Re: Recursive method to sort string lexographically

Posted 06 October 2012 - 11:26 AM

Just because you haven't covered arrays in class yet shouldn't deter you from using them provided you know how to use them. I think your instructor would likely even be impressed if you managed to successfully implement a concept you haven't covered in class. Just my opinion though.

#6 Kinaces

Reputation: 78
• Posts: 230
• Joined: 04-October 12

Re: Recursive method to sort string lexographically

Posted 06 October 2012 - 11:30 AM

Ytry, on 06 October 2012 - 11:26 AM, said:

Just because you haven't covered arrays in class yet shouldn't deter you from using them provided you know how to use them. I think your instructor would likely even be impressed if you managed to successfully implement a concept you haven't covered in class. Just my opinion though.

I found that if you use concepts that you did not know before, and you show no previous knowledge of programming then they most the time accuse you of cheating. If you go this route I would suggest finding resources that you read/used to learn about anything before you use it in class if you have not gone over it, and show them to your teacher.

#7 bcsmith8

Reputation: 0
• Posts: 18
• Joined: 20-August 12

Re: Recursive method to sort string lexographically

Posted 06 October 2012 - 11:38 AM

I think I'm just going to go with the safe route and use what he's already taught us because he probably would assume I cheated if I used something we haven't covered yet. If he shows us a way that is more efficient than the one I came up with that doesn't deal with arrays, I will post it here in a few days so you guys can see.

#8 baavgai

• Dreaming Coder

Reputation: 6251
• Posts: 13,394
• Joined: 16-October 07

Re: Recursive method to sort string lexographically

Posted 06 October 2012 - 06:18 PM

Well, if you're allowed to use more methods than just recurse(String s), then options open up. Creating a string over and over again is probably the most wasteful thing you can do. You could just leave the string along and walk your way through the values...

I'd go with something like:
```private static String firstCharacter(String s, String greaterThanThis) { /* your code here */ }

private static String recurse(String s, String greaterThanThis) {
if (greaterThanThis==null) { return ""; }
return greaterThanThis + recurse(s, firstCharacter(s, greaterThanThis));
}

private static String recurse(String s) { return recurse(s, firstCharacter(s, null)); }

```