boswalt
BAN USERThe algorithm works from the back of the string forwards, first placing the capital letters in their correct position, while shifting the string left. After the capital letters are placed, the algorithm does the same thing, placing the spaces in their correct position. Once the capital letters and spaces are positioned, the lowercase letters will automatically be in their correct places. I think this should still be O(N).
- boswalt August 28, 2015public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
//char[] charArray = new char [] { 'c', 'A', 'B', 'd', ' '};
Sort(charArray);
System.out.print(charArray);
}
public static void Sort(char[]charArray) {
int writePos = charArray.length - 1;
// Search for capital letters in first pass
char lower = 'A';
char upper = 'Z';
for (int pass = 0; pass < 2; pass++)
{
for (int readPos = writePos; readPos >=0; readPos--) {
if (charArray[readPos] >= lower && charArray[readPos] <= upper) {
if (readPos == writePos) {
// This character is in the correct place already
writePos--;
continue;
}
// Put the character in its correct place
// and shift the remaining characters left to fill
// in the gap
char temp = charArray[readPos];
System.arraycopy(charArray, readPos+1, charArray, readPos, writePos - readPos);
charArray[writePos--] = temp;
}
}
lower=upper=' '; // Search for spaces in second pass
}
}
}
- boswalt August 28, 2015
The array copy uses the same array as the source and destination, so there is no additional space used. The copy shifts all elements left into the gap left over. The only question for me is the running time of the copy. The worst case scenario is presented when there is an equal number of spaces, followed by an equal number of uppercase letters, followed by an equal number of lowercase letters.
- boswalt August 29, 2015