Homework SourseJava 1 Create a new workspace with one class 2 In your java
Java:
1. Create a new workspace with one class.
2. In your java program, create a method named main.
3. In your java program, create another method named sort with the following heading:
public static void sort(char[] a)
We know that arrays are objects, so any changes made to array a in the sort method will affect the array in the calling program (i.e., main()). Therefore, sort doesn’t need to return a new array. It can change the array a[] instead.
4. In sort, create a new array named temp that will hold a sorted version of the array named a
char[] temp = new char[a.length] ;
5. For the first character a[0], there isn’t anything in temp yet, so just move the character in a[0] into the first slot in temp:
temp[0] = a[0] ;
6. For all of the remaining characters in the array a, create a for-loop that will cycle through each character in that array. In pseudocode:
for (int index = 1 ; index < a.length ; index++)
{
[ insert a[index] into its appropriate spot in temp[] ]
}
Notice that we are starting at index 1, the 2nd character in array a. The first character in array a was taken care of in step 5 above
7. Inside this loop, we need to move the character at a[index] into its appropriate position in the new array temp in such a way that temp is always sorted.
Inside the “for” loop, we know that there are currently index elements in temp, so loop through each character until we find the appropriate spot. That means that the loop should continue until either:
we have run out of characters in temp, or
the character being tested in temp “appears after” the character we are trying to insert (a[index]). (By appears after, we mean that one character occurs after the other character in the Unicode table).
int insertHere = 0 ;
while ((insertHere < index) && (temp[insertHere] < a[index]))
{
insertHere++ ;
}
The test: insertHere < index will ensure that there aren’t any more characters to check in temp.
The test: temp[insertHere} < a[index] means that the character at temp[insertHere] appears in the Unicode table before the character we are trying to insert, namely a[index].
8. We need to make room for this new character by moving all of the characters after insertHere in temp one position down in the array. We can use another for-loop to do this:
for (int i = insertHere ; i < index ; i++)
{
temp[i + 1] = temp[i] ;
}
9. Once everything has been moved “down” one position in the temp array, move the character to be inserted into its appropriate position in temp:
temp[insertHere] = a[index] ;
That should complete the outer for-loop.
10. At the very end of the sort method (sorting is completed), copy the contents of the temp array back to the a array;
for (int index = 0 ; index < a.length ; index++)
{
a[index] = temp[index] ;
}
11. That should complete the sort method. Your method should look something like:
public static void sort(char[] a)
{
// Create a temporary array to insert characters sorted
char[] temp = new char[a.length] ;
// Move the first character in a[] into the temp[] array
temp[0] = a[0] ;
// Loop through remaining chars, inserting them into temp[]
for (int index = 1 ; index < a.length ; index++)
{
// Find the appropriate spot in temp[] to insert a[index]
int insertHere = 0 ;
while ((insertHere < index) &&
(temp[insertHere] < a[index]))
{
insertHere++ ;
}
// Move all characters after insert point down one in temp[]
for (int i = insertHere ; i < index ; i++)
{
temp[i + 1] = temp[i] ;
}
// Insert the character from a[] into its sorted spot
temp[insertHere] = a[index] ;
} // end of for loop
// All done sorting, so copy the temp[] array back into a[]
for (int index = 0 ; index < a.length ; index++)
{
a[index] = temp[index] ;
}
} // end of sort() method
12. Now debug your code. Try a couple of easy ones first. For main, use the following:
Curly brackets
public static void main(String[] args)
{
char[] test = new char[] { \'a\', \'b\' } ;
System.out.println(\"Unsorted: \" + new String(test)) ;
sort(test) ;
System.out.println(\"Sorted: \" + new String(test)) ;
}
That should work ok.
13. A few more test cases. Change the line that creates the test array to:
char[] test = new char[] { \'b\', \'a\' } ;
That one should work, too.
14. Curly brackets
14.Here’s another one. Change the line that creates the testarray to:
char[] test = new char[] { \'X\' } ;
Looks like your method works with arrays having 1 and 2 elements!
15. Curly brackets
15.Test your program with an empty array of characters. In main, change the line that creates the testarray to:
char[] test = new char[] {} ;
There’s an issue – the sort method can’t handle empty arrays. Based on the Java error message, it likely stopped at the line temp[0] = a[0]. Since there’s nothing to sort in empty arrays, just insert the following code at the top of the sort method and test to make sure it works:
if (a.length == 0)
{
return ;
}
16. Try more difficult arrays. In main, change the line that creates test to:
char[] test = new char[] {\'e\', \'d\', \'c\', \'b\', \'a\'} ;
It returned abbb
17. Find out what’s going on inside the sort program by placing a “print” statement just before last statement of the outside for-loop. Insert the following code at the end of the outer “for” loop in sort:
System.out.print(\"When index = \" + index + \": \") ;
for (int i = 0 ; i <= index ; i++)
{
System.out.print(temp[i]) ;
}
System.out.println() ;
The program should print the following sequence:
When index = 1: de
When index = 2: cdd
When index = 3: bccc
When index = 4: abbbb
The problem is that the loop to move characters “down” in temp before insertion is copying over the characters. Instead, the loop has to work backwards from the last character in temp “up” to the character position to be inserted. To do this, change the code used in step 8 to work in reverse order:
for (int i = index - 1 ; i >= insertHere ; i--)
{
temp[i + 1] = temp[i] ;
}
18. Try a few more test cases to make sure that your program works.
19. Make sure to use the following test cases:
The character array { \'G\' }
The character array { \'a\', \'b\', \'c\', \'d\' }
The character array { \'d\', \'c\', \'b\', \'a\' }
The character array { \'m\', \'X\', \'%\', \'B\', \'e\', \'!\' }
The empty array { }
20. In additoin, create separate methods to:
find the insertion index for a[index] in temp (step 7)
move characters down one position in temp (steps 8 & 17)
insert a[index] into temp[] (step 9)
copy the temp array to a (step 10)
Use these methods in your sort program.
Solution
// The following code is as per the point number 11. The test cases will be run on this till 14.
public class SortArray {
public static void main(String args[]) {
char[] test = new char[] { \'a\', \'b\' } ;
System.out.println(\"Unsorted: \" + new String(test)) ;
sort(test) ;
System.out.println(\"Sorted: \" + new String(test)) ;
}
public static void sort(char[] a)
{
// Create a temporary array to insert characters sorted
char[] temp = new char[a.length] ;
// Move the first character in a[] into the temp[] array
temp[0] = a[0] ;
// Loop through remaining chars, inserting them into temp[]
for (int index = 1 ; index < a.length ; index++)
{
// Find the appropriate spot in temp[] to insert a[index]
int insertHere = 0 ;
while ((insertHere < index) &&
(temp[insertHere] < a[index]))
{
insertHere++ ;
}
// Move all characters after insert point down one in temp[]
for (int i = insertHere ; i < index ; i++)
{
temp[i + 1] = temp[i] ;
}
// Insert the character from a[] into its sorted spot
temp[insertHere] = a[index] ;
} // end of for loop
// All done sorting, so copy the temp[] array back into a[]
for (int index = 0 ; index < a.length ; index++)
{
a[index] = temp[index] ;
}
} // end of sort() method
}
------------------output/test cases till 14--------------------
No12.
Unsorted: ab
Sorted: ab
No 13.
Unsorted: ba
Sorted: ab
No 14.
Unsorted: X
Sorted: X
No 15. exception
Unsorted: Exception in thread \"main\"
java.lang.ArrayIndexOutOfBoundsException: 0
at SortArray.sort(SortArray.java:19)
at SortArray.main(SortArray.java:10)
---------------------------------test cases end till 14--------------------
//Program top handle 15 th test cases
// The following code is as per the point number 11. The test cases will be run on this till 14.
public class SortArray {
public static void main(String args[]) {
//char[] test = new char[] { \'a\', \'b\' } ;
//char[] test = new char[] { \'b\', \'a\' } ;
//char[] test = new char[] { \'X\' } ;
char[] test = new char[] {} ;
System.out.println(\"Unsorted: \" + new String(test)) ;
sort(test) ;
System.out.println(\"Sorted: \" + new String(test)) ;
}
public static void sort(char[] a)
{
// if the input array length is 0 then return back
if (a.length == 0)
{
return ;
}
// Create a temporary array to insert characters sorted
char[] temp = new char[a.length] ;
// Move the first character in a[] into the temp[] array
temp[0] = a[0] ;
// Loop through remaining chars, inserting them into temp[]
for (int index = 1 ; index < a.length ; index++)
{
// Find the appropriate spot in temp[] to insert a[index]
int insertHere = 0 ;
while ((insertHere < index) &&
(temp[insertHere] < a[index]))
{
insertHere++ ;
}
// Move all characters after insert point down one in temp[]
for (int i = insertHere ; i < index ; i++)
{
temp[i + 1] = temp[i] ;
}
// Insert the character from a[] into its sorted spot
temp[insertHere] = a[index] ;
} // end of for loop
// All done sorting, so copy the temp[] array back into a[]
for (int index = 0 ; index < a.length ; index++)
{
a[index] = temp[index] ;
}
} // end of sort() method
}
-------------output/test---------------
No 15
Unsorted:
Sorted:
No 16.
Unsorted: edcba
Sorted: abbbb
No 17. test
Unsorted: edcba
When index = 1: de
When index = 2: cdd
When index = 3: bccc
When index = 4: abbbb
Sorted: abbbb
No 17. after fix
Unsorted: edcba
When index = 1: de
When index = 2: cde
When index = 3: bcde
When index = 4: abcde
Sorted: abcde
No 19.
a) Unsorted: G
Sorted: G
b) Unsorted: abcd
When index = 1: ab
When index = 2: abc
When index = 3: abcd
Sorted: abcd
c) Unsorted: dcba
When index = 1: cd
When index = 2: bcd
When index = 3: abcd
Sorted: abcd
d) Unsorted: mX%Be!
When index = 1: Xm
When index = 2: %Xm
When index = 3: %BXm
When index = 4: %BXem
When index = 5: !%BXem
Sorted: !%BXem
e) Unsorted:
Sorted:
-------------output/test ends---------------
// For no 20 making all the lines as seperated input
// The following code is as per the point number 11. The test cases will be run on this till 14.
public class SortArray {
public static void main(String args[]) {
//char[] test = new char[] { \'a\', \'b\' } ;
//char[] test = new char[] { \'b\', \'a\' } ;
//char[] test = new char[] { \'X\' } ;
//char[] test = new char[] {} ;
//char[] test = new char[] {\'e\', \'d\', \'c\', \'b\', \'a\'} ;
//char[] test = new char[] { \'G\' } ;
//char[] test = new char[] { \'a\', \'b\', \'c\', \'d\' } ;
//char[] test = new char[] { \'d\', \'c\', \'b\', \'a\' };
char[] test = new char[] { \'m\', \'X\', \'%\', \'B\', \'e\', \'!\' };
//char[] test = new char[] {};
System.out.println(\"Unsorted: \" + new String(test)) ;
sort(test) ;
System.out.println(\"Sorted: \" + new String(test)) ;
}
public static void sort(char[] a)
{
// if the input array length is 0 then return back
if (a.length == 0)
{
return ;
}
// Create a temporary array to insert characters sorted
char[] temp = new char[a.length] ;
// Move the first character in a[] into the temp[] array
temp[0] = a[0] ;
// Loop through remaining chars, inserting them into temp[]
for (int index = 1 ; index < a.length ; index++)
{
// Find the appropriate spot in temp[] to insert a[index]
int insertHere = 0 ;
insertHere = tempSort(a, temp, index, insertHere);
// Move all characters after insert point down one in temp[]
/*for (int i = insertHere ; i < index ; i++)
{
temp[i + 1] = temp[i] ;
}*/
// in reverse order
moveArray(temp, index, insertHere);
// Insert the character from a[] into its sorted spot
insertValue(a, temp, index, insertHere);
System.out.print(\"When index = \" + index + \": \") ;
for (int i = 0 ; i <= index ; i++)
{
System.out.print(temp[i]) ;
}
System.out.println() ;
} // end of for loop
// All done sorting, so copy the temp[] array back into a[]
copyArray(a, temp);
} // end of sort() method
/**
* @param a
* @param temp
* @param index
* @param insertHere
* @return
*/
private static int tempSort(char[] a, char[] temp, int index, int insertHere) {
while ((insertHere < index) &&
(temp[insertHere] < a[index]))
{
insertHere++ ;
}
return insertHere;
}
/**
* @param temp
* @param index
* @param insertHere
*/
private static void moveArray(char[] temp, int index, int insertHere) {
for (int i = index - 1 ; i >= insertHere ; i--)
{
temp[i + 1] = temp[i] ;
}
}
/**
* @param a
* @param temp
* @param index
* @param insertHere
*/
private static void insertValue(char[] a, char[] temp, int index,
int insertHere) {
temp[insertHere] = a[index] ;
}
/**
* @param a
* @param temp
*/
private static void copyArray(char[] a, char[] temp) {
for (int index = 0 ; index < a.length ; index++)
{
insertValue(temp, a, index, index);
}
}
}
--------------output/test---------------
No 20
Unsorted: mX%Be!
When index = 1: Xm
When index = 2: %Xm
When index = 3: %BXm
When index = 4: %BXem
When index = 5: !%BXem
Sorted: !%BXem
//NOte: Please go trhough each comments. Fell free to ask any questions. God bless you!
