[bcsmith8]

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)
					//add the earliest letter
					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;
	}

}

[Kakerergodt]

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

[Kinaces]

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.

[bcsmith8]

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.

[Ytry]

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.

[Kinaces]

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.

[bcsmith8]

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.

[baavgai]

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)); }