Thread: please help! *find and remove "outcasts" in supposed to be alphabetic sorted list

Hi,

I'm writing my master thesis on document layout recognition and I'm writing a program on recognizing dictionary-pages.

I have a list of what could be lemmas (~the "lookup word"). {cab, calculator, car, cat}.

The list is supposed to be sorted in alphabetic order. But sometimes it isn't and I've gotten a word/words in to the list, which isn't supposed to be a lemma, that is, something that has fulfilled all the criterias of being a lemma, but in reality isn't has snuck in: {cab, calculator, cast, car, call, cat}.

Now, I have to find the word that has been recognized as a lemma but isn't ('cause it doesn't follow the alphabetic order).
I kind of need to find the path most of the words are following and then remove the outcasts.

I'd love to post some example code of what I've been trying, but truth is, that after trying more than a dozen of different methods, I got so frustrated that I deleted everything.

My main approach is to get sublists and find the part of the list where the faulty word is but then I kind of get stuck.

Please, please help, or comment if I haven't explained good enough. I'm going crazy here!

Somehow I imagine this would be great to solve with recursion - something like this:

/**
 * check if the lemmas are listed in alphabetic order. If not, remove fake lemmas.
 * @param lemmings
 * @param finished
 * @return correct lemma-list
 */private List<String> checkingLemmas(List<String> lemmings, ArrayList<String> finished){
	if(isSorted(lemmings))
		return lemmings;
	if(lemmings.size() == 2){
		//what to do here?
		// I don't have anything to compare to anymore so I don't know which of the two to remove.
		//went too far...
 
	}
	if(lemmings.size() == 3){
		ArrayList<String> x = new ArrayList<String>();
		x.add(lemmings.get(0));
		x.add(lemmings.get(lemmings.size()-1));
	}
 	List<String> list1 = lemmings.subList(0, (lemmings.size()/2));
	List<String> list2 = lemmings.subList((lemmings.size()/2), (lemmings.size()-1));
 	if(isSorted(list1)){
 			finished.addAll(list1);
 			Collections.sort(finished);
	}
	else if(!isSorted(list1)){
		finished.addAll(checkingLemmas(list1, finished));
	}
	if(isSorted(list2)){
		finished.addAll(list2);
		Collections.sort(finished);
	}
	else if(!isSorted(list2)){
		finished.addAll(checkingLemmas(list2, finished));
	}
	return finished;
}