Java - Sorting parts of arrays

[Earendil]

I'm working on a project for my class (school class), and I'm on the absolute final method I need to code, and I don't know how to do it.

Here's the situation: I've read in a Bush speech, and counted the number of times each word occurs, and sorted those.

As of now, I have two arrays, one of Strings and one of ints, consisting of all the words, and the number of times they occured. They're sorted from occurence max to min.

So, it outputs the following.


the: 216
and: 165
.
.
.
Casablanca: 1
around: 1
Zarqawi: 1

My problem is that I need to organize all words whose occurence are the same alphabetically.

So all words who occur once need to be in alphabetical order (as you can see they're not).

I just need to figure out how to figure out which words need to be sorted, and sort those. I don't know either how to figure out which words have the same count, and then how to sort those. The code below was the best I could come up with, and it failed. I tried to figure out which indices for count were equal, then sorting all the elements between those two indices for the words array.

Any help would be super, either corrections to my code, or suggesting a new algorithm.




public static String[] countOrgan(String[] words, int [] count) {

int high, low, min;
String temp;

for(int i=1;i<count.length-1;i++) {
if (count[i]==count[i-1]&&count[i]!=count[i+1]){
low = i;
do {
if(count[i]==count[i-1])
i++;
else break;
} while(true);
high = i-1;
i--;
}
else continue;

for(int j=low; j<high-1;j++) {
min = j;
for(int k=j+1;k<high;k++) {
if (words[k].compareTo(words[min])<0)
min = k;
}
temp = words[j];
words[j] = words[min];
words[min] = temp;

}
}

return words;
}

[Bad_Kharma]

Seems that to sort your matches alphabetically, you simply search in your count array at which position the next value stands. Then use that value to go to your words array, isolate the part you need and create a subarray from it. Sort your subarray alphabetically, and replace the values in your main array.

The below should return your stringArray sorted as you wish it. If not, tweak away, I'm no java wizz, I just know a few words :eek13: . hope it helps ... and isn't to confusing v.v



private static String [] orderBy (int[] intArray, String[] stringArray)
{
//initialising variables
int j = 0;
String [] copyStringArray = stringArray;

//go through the intArray
for (int i = 0; i<intArray.length; i++)
{
//find at which position we have a different value
if(i != intArray.length-1 && intArray[i] != intArray[i+1])
{
//determine the length of the subarray
int length = (i-j+1);

//create the subarray
String [] subarray = new String [length];

//copy the part of your word array you wish to sort, into the subarray
//System.arraycopy(OriginalArrayName,StartingIntOrig ,SubArrayName,StartingIntSub,Length)
System.arraycopy(copyStringArray,j,subarray,0,leng th);

//sort the subarray
subarray = sortStrings(subarray);

//replace the taken values by the sorted values
for (int k=0; k<subarray.length;k++)
{
copyStringArray[j+k] = subarray[k];
}

//store the next beginning position for the next subarray
j=i+1;
}
}

//return the new string array
return copyStringArray;
}


private static String[] sortStrings (String [] stringArray)
{
Arrays.sort(stringArray, new Comparator()
{
public int compare(Object o1, Object o2)
{
return (((String) o1).toLowerCase().
compareTo(((String) o2).toLowerCase()));
}
});
return stringArray;
}

[Earendil]

It works for taking out the subarrays, but it sorts them backwards...

So, it goes from z-a, instead of a-z. I've tried replacing your sort (Which I don't understand), with a simple selection sort, and it returns the same problem. With no sort, they're out of order, so it's not the product of previous sorting in my class.

Maybe a reverse sort would work? I just can't remember how to implement one (preferably a selection sort for consistency)...

Since the normal one compares to the min value, and swaps if it's lower, do I just compare it to the max, and if it's bigger, swap?

[Bad_Kharma]

Goes A-Z on mine ... just switch (Object o1, Object o2) (the compareTo operate retruns an int value which the comparable uses here. If it return +1, it means the first string is greater then, 0 means equal to, -1 smaller then the second one (alphabetically speaking)) around and it'll reverse. You can of course just replace the code in it as well with your own makings since I don't onderstands the depths of it either, I just use it :tongue:

Thing is (I think if I read it right ... I'm tired, sue me), your code only goes through the entire array once and switches the values which follow. Which doesn't sort your array completely, you just swap sequential values.

So in case of 9,7,3,12,5 your code would change that into 7,3,9,5,12. to make it complete, you'd have to perform the swapping another time for every element in your array, so a double for loop (long time ago since I last saw this, I should have paid attention in class damnit >.<)

For ways to sort, do a search for bubble sort (though this sort is the slow sort) or quick sort (this one is quick, go figure).

[Earendil]

Well, considering I've got a GUI, the speed of the program is already junk, I don't want to hassle a bubble sort with 10k or so elements.

As for my suggestion to the selection sort, I was just trying to figure out what to test in each loop. Apparently I was right (Yay me), and it works fine.

Mmm... Thanks for the help, I think I've got it now, minus some nice documentation and cleaning up. What a pain in the butt this was.

[snoop]

It seens like you could write a more efficient sort by doing something similar to a radix sort; except by using 26 different queues rather than 10 (or 2).
That way ou make no comparisons and you get an O(Nln(N) algorithm out of it... SO essentially what you should do is look at each char in the string individually and assign them queues by the character in the string... so write a method that returns values 0-25 for each letter of the alphabet (0 for space/numbers), make an array of java queues, put the strings into queues for each letter, after you finish each string, empty each queue back into your array in order 0,1,2,3,4, etc. Do this for each letter in each string; it'll be efficient and NOT a bubble sort.