Module 3: Arrays of chars and strings

Using toCharArray() in a string, one can pull out (a copy of) the letters of a string into an array:

public class StringToChars {

    public static void main (String[] argv)
    {
	String s = "Avast ye scallywags!";
	char[] letters = s.toCharArray ();
	for (int i=0; i<letters.length; i++) {
	    System.out.print (letters[i]);
	}
	System.out.println ();
    }

}
     

This is useful when we want to manipulate the letters. As an example, let's sort the letters in a word:

• Note: we can't change the letters inside a string.

• What we'll need to do: pull out the letters into an array and sort the letters within that array.

• How to sort? We'll use this idea:
  • Find the (alphabetically) smallest letter and put that in the first spot in the array.
  • Then find the next smallest letter.
  • And so on.

For example:

• Suppose we want to sort the letters

       s  h  a  l  o  m
       

• We want to search through for the letter that should go into the first position:

       s  h  a  l  o  m
       

  and swap that with whatever is there now:

       a  h  s  l  o  m
       

• That's done and we don't look back.

• Next we scan from "h" onwards for the smallest.

       a  h  s  l  o  m
       

  Nothing is smaller than h, so we leave it there.

• Now look from "s" onwards:

       a  h  s  l  o  m
       

  The smallest is "l" so swap that with "s"

       a  h  l  s  o  m
       

• The next letter is "s" (which got moved):

       a  h  l  s  o  m
       

  and the smallest among the remaining is "m"

       a  h  l  s  o  m
       

• After that swap:

       a  h  l  m  o  s
       

• Then, we look from "o" onwards:

       a  h  l  m  o  s
       

  Nothing is smaller so it stays.

• Lastly, there's "s" but nothing to its right. And so we're done:

       a  h  l  m  o  s
       

  (Remember the ahlmos?)

Here's sample code using a different word whose letters we wish to sort:

public class CharSort {

    public static void main (String[] argv)
    {
	// A string whose letters we want to sort:
	String w = "Cowabunga";
	// Pull the letters out into a char array:
	char[] letters = w.toCharArray ();

	for (int i=0; i<letters.length-1; i++) {

	    // Start by assuming i-th letter is the smallest.
	    char smallest = letters[i];
	    // We'll need to record the position where the smallest occurs.
	    int smallestIndex = i;

	    // Now try each position to the right of the i-th position:
	    for (int j=i+1; j<letters.length; j++) {
		// If the letter here is smaller than the smallest so far
		// then update the smallest and its location.
		if (letters[j] < smallest) {
		    smallest = letters[j];
		    smallestIndex = j;
		}
	    }

	    // We now know the smallest and where it occurs.
	    // Next: swap char at i with char at smallestIndex
	    char temp = letters[i];
	    letters[i] = letters[smallestIndex];
	    letters[smallestIndex] = temp;
	}

	// Print result.
	for (int i=0; i<letters.length; i++) {
	    System.out.print (letters[i]);
	}
	System.out.println ();
    }

}
     

This is a bit long so let's work through this in steps.

3.9 Exercise: Type and execute the above program.

Let's now explain:

• First, the easy parts:

  	// This part pulls out the letters:
  	String w = "Cowabunga";
  	char[] letters = w.toCharArray ();
  
  	// ... the sorting part we'll explain later ... 
  
  	// Print result.
  	for (int i=0; i<letters.length; i++) {
  	    System.out.print (letters[i]);
  	}
  	System.out.println ();
       

• OK, now let's focus on the outer loop:

  	for (int i=0; i<letters.length-1; i++) {
              // We want to get the i-th smallest letter 
              // and put that in letters[i]
  
              letters[i] = ... (somehow find the i-th smallest letter)
          }
  
       

• The first thing to observe is that this sorts the array because:
  • The 0-th smallest letter (the smallest of all letters) will end up in letters[0].
  • The next smallest will end up in letters[1].
  • And so on.
  • That means the array will be sorted.

• Now let's focus on getting the i-th smallest.

• Suppose we are able to find the location of the smallest letter, then we could swap that letter into the i-th location:
  • Suppose i=2 and the location of the smallest is 5.
  • Move whatever's at location 5 into location 2.
  • Move whatever's at location 2 into location 5.
  • Now we have the smallest in location 2.

• So, here's the swap:

  	for (int i=0; i<letters.length-1; i++) {
              // We want to get the i-th smallest letter 
              // and put that in letters[i]
  
              // Suppose the i-th smallest occurs at position smallestIndex.
  	    // We swap to get that one into letters[i].
  	    char temp = letters[i];
  	    letters[i] = letters[smallestIndex];
  	    letters[smallestIndex] = temp;
          }
  
       

• All that's left is to find the i-th smallest.

  	for (int i=0; i<letters.length-1; i++) {
  
              // Default is what's at i:
  	    char smallest = letters[i];
  	    int smallestIndex = i;
  
  	    // Look to the right of i (from i+1 onwards)
  	    for (int j=i+1; j<letters.length; j++) {
                  // Compare with smallest so far (in the smallest variable)
  	        // and update smallest and position if needed.
              }
  
              // Do the swap etc (we've seen this) ... 
        
          }
  
       

3.10 Exercise: In module3.pdf, trace through the program drawing out the array at each step, as well as the values of the key variables: i, j, smallest, smallestIndex. Even though this is tedious, it will be worth it. Understanding sorting will help you understand how to work with many types of array problems.

3.11 Video:

3.12 Exercise: In StrangeComparison.java use the following template:

public class StrangeComparison {

    public static void main (String[] argv)
    {
        // Two strings:
        String w1 = "verbose";
        char[] letters1 = w1.toCharArray ();
        String w2 = "observe";
        char[] letters2 = w2.toCharArray ();

        // Sort the letters of the first string:

        // Sort the letters of the second string:

        // Now letters1 and letters2 are sorted.

        // Compare the corresponding chars in letters1
        // and letters2 to see if the two arrays are equal:

    }

}