Sorting Arrays in Java

Question

Write a static method in Java:

public static void sortByFour (int[] arr) 

This takes as an argument an array full of non-negative numbers (zero or positive) and sorts the array as follows:

• At the beginning of the array, all numbers divisible by four will appear.

• After them, all numbers in the array will appear, which are divided by 4 with the remainder of 1.

• After them, all numbers in the array will appear, which are divided by 4 with the remainder of 2.

• At the end of the array, all other numbers will appear (those that are divisible by 4 with the remainder of 3).

(The order of numbers in each group does not matter.)

The method should be as efficient as possible.

The following is what I wrote, but unfortunately this does not work well ... :(

 public static void swap( int[] arr, int left, int right ) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } public static void sortByFour( int[] arr ) { int left = 0; int right = ( arr.length - 1 ); int mid = ( arr.length / 2 ); while ( left < right ) { if ( ( arr[left] % 4 ) > ( arr[right] % 4 ) ) { swap( arr, left, right ); right--; } if ( ( arr[left] % 4 ) == ( arr[right] % 4 ) ) left++; else left++; } } 

How do I fix or rewrite my code so that it works well?

Answer 1

I will do it in psuedocode for you, but doing it in code will give you an answer, and this is homework so you can do your job. = P

Here's how to do it without lists. This example is limited depending on requirements, but will work after its coding.

 int bucketSize = (arr.length() / 4) + 1; int bucket1[bucketSize]; int bucket2[bucketSize]; int bucket3[bucketSize]; int bucket4[bucketSize]; for (int i=0; i<arr.length; i++) { if ((arr[i] % 4) == 0) put arr[i] in bucket 1 else if ((arr[i] % 4) == 1) put arr[i] in bucket 2 else if ((arr[i] % 4) == 2) put arr[i] in bucket 3 else put arr[i] in bucket 4 } for (int i=0; i<4; i++) { this will go for each bucket for (int j=0; j<bucketSize; j++) { do sort of your choice here to sort the given bucket the sort you used in your code will do fine (the swapping) } } 

then combine the four buckets in the proper order to get the final result

Answer 2

You can attack this problem as follows:

• Select the sorting algorithm you want to use. It sounds like you're trying to program Quicksort , but you can also use Bubble Sort .
• Determine the point (s) of the algorithm at which two values ​​from the input array are compared. For example, in the pseudocode for Bubble Sort in a Wikipedia article, the only comparison is the line if A[i] > A[i+1] then...
• Define a method for comparing two numbers, so that a number s having a remainder of 0 when divided by 4 is considered less than a number t having a remainder of 1 when divided by 4. Replace the algorithm comparison operations with comparator (for example, if myIsGreater(A[i], A[i+1]) then... ).

For step 3, you are definitely on the right track by looking at the module operator.

Answer 3

I will repeat what Daniel said: you have a choice of sorting algorithm. Use the most effective that you have considered in the class so far, if this is a requirement. But when you get to the point of your algorithm where two elements are compared, compare their value mod 4. So something like if A[i] > A[j] becomes if A[i] % 4 > if A[j] % 4 . Then you continue to do what the algorithm determines what you do with this element of the array. Change it, release it, return everything you need.

As for the code you posted, I don't think it can be fixed quickly. What algorithm should he use? What is mid ? I think that as soon as you find out which algorithm you are going to use and find out which line of code contains the comparison, you can quickly look through and encode the solution.

In general, with such things, it can help if you focus on getting a working solution before worrying about efficiency. I used sorting sorting the first time I had to do such a problem. I would recommend this first, and then use the experience gained to create the merge, which is O (n log n).

Answer 4

Linear time solution

The most asymptotically effective way to do this would be to use a sorting bucket .

• You have 4 baskets, one for each of the matching classes modulo 4.
• Scan the numbers in the array once
  • Put each number in the right bucket
• Then build the output array
  • First enter all the numbers from bucket 0, then everything from bucket 1, then bucket 2, then bucket 3

Thus, it sorts the numbers in O(N) , which is optimal. The key here is that, sorting by numbers modulo 4, only 4 numbers are sorted in order: 0, 1, 2, 3.

---

Illustrative Solution with List

Here the implementation of the above algorithm is implemented (for the general modulo M ) using List and for each for clarity. Ignore the untested throw warning, just focus on understanding the algorithm.

 import java.util.*; public class BucketModulo { public static void main(String[] args) { final int M = 4; List<Integer> nums = Arrays.asList(13,7,42,1,6,8,1,4,9,12,11,5); List<Integer>[] buckets = (List<Integer>[]) new List[M]; for (int i = 0; i < M; i++) { buckets[i] = new ArrayList<Integer>(); } for (int num : nums) { buckets[num % M].add(num); } nums = new ArrayList<Integer>(); for (List<Integer> bucket : buckets) { nums.addAll(bucket); } System.out.println(nums); // prints "[8, 4, 12, 13, 1, 1, 9, 5, 42, 6, 7, 11]" } } 

Once you fully understand the algorithm, translating this into using arrays (if necessary) is trivial.

see also

• java.util.List<E> API - "ordered collection"
  • add(E e) - "Adds the specified item to the end of this list"
  • addAll(...) - "Adds all items in the specified collection to the end of this list"
• Java / language guide for each loop (introduced in 1.5.0)

---

Special note to %

The caveat that numbers are non-negative is significant because % NOT a modular operator because it is mathematically defined; this is the remainder operator.

 System.out.println(-1 % 2); // prints "-1" 

References

• JLS 15.17.3 Stop operator%
• Wikipedia / Work in the module

Answer 5

Read this page. http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms

This should help you best in the long run. It is also very funny!

Answer 6

Here's the Java-ish path ...

  Arrays.sort(arr,new Comparator<Integer>(){ public int compare(Integer a,Integer b) { return (a % 4) - (b % 4); } });