0

For a homework assignment, I need to write method which can sort array, the sort method should be efficient as possible.

  1. Beginning of the array will appear all the numbers that divide by 4 without remainder.
  2. Will be followed by all the numbers that divide by 4 with remainder of 1
  3. Will be followed by all the numbers that divide by 4 with remainder of 2
  4. At the end of the array will all the other numbers (those that divide by four with the remaining three).

I tried this set 4 pointers:
2 pointers At first the remainder of 0 and 1
2 pointers at the last of the array for the remainder of 2 and 3

This is what I could find so far (with problem of course), I appreciate your help !

public static void sortByFour (int[] arr)
{
    int temp;
    int noRemainderIndex = 0;
    int remainder1Index = 1;
    int remainder2Index = arr.length - 2;
    int remainder3Index = arr.length - 1;

    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] % 4 == 0)
        {
            temp = arr[noRemainderIndex];
            arr[noRemainderIndex] = arr[i];
            arr[i] = temp;
            noRemainderIndex++;
            remainder1Index++;
        }
        else if (arr[i] % 4 == 1)
        {
            temp = arr[remainder1Index];
            arr[remainder1Index] = arr[i];
            arr[i] = temp;
            remainder1Index++;
        }
        else if (arr[i] % 4 == 2)
        {
            temp = arr[remainder2Index];
            arr[remainder2Index] = arr[i];
            arr[i] = temp;
            remainder2Index--;
        }
        else if (arr[i] % 4 == 3)
        {   
            temp = arr[remainder3Index];
            arr[remainder3Index] = temp = arr[i];
            arr[i] = temp;
            remainder3Index--;
            remainder2Index--;
        }
    }
Improve this question
4
  • 2
    What about the order among numbers divide 4 with the same remainder? Commented May 26, 2012 at 16:01
  • Are you allowed to the Array.sort method? Commented May 26, 2012 at 16:02
  • no need to organize them Commented May 26, 2012 at 16:03
  • no, i need to write it in my self this should be as much of a place and time saving Commented May 26, 2012 at 16:04

4 Answers 4

Reset to default
2

Hints for your homework.

  1. If you are allowed to use existing library methods, look at Array.sort(...) and the Comparator interface. (Noting that to use a custom comparator when sorting an array of a primitive type, you have to convert to the wrapper type first; e.g. convert int[] to Integer[], sort, and convert back.)

  2. If you are not allowed to use Array.sort(...) (or similar), figure out if this is a sorting problem or a collating problem. In other words if there is any requirement to reorder (or retain the order of) the numbers in the 4 categories.

  3. You could simplify the problem by using 4 temporary arrays, but there are other (more tricky) solutions that involve making multiple passes through the array and swapping pairs of elements.

  4. One of the problems that needs to be solved is that you don't know beforehand how many numbers there are in each of the 4 categories. So you don't know beforehand the destinations for moving the numbers. But there are solutions to this ...

... the sort method should be efficient as possible.

Is this a homework requirement, or your requirement?

If this is something that you've added yourself - BEWARE - your marker may give higher marks for a simple solution than a (supposedly) more efficient but overly complicated solution.

A good software engineer does not strive for the ultimate in efficiency in every program. Rather, he balances various things:

  • functionality requirements,
  • requirements for performance,
  • requirements for software maintainability, and
  • project deadlines,

noting that some of these requirements may be implied, and / or not properly understood by management.

(Or to put it another way, a program that is fast .... but doesn't work reliably, or isn't maintainable, or isn't ready in time ... is a failure.)

On the other hand, if performance is a requirement for this homework exercise, then your lecturers should have explained how to measure performance of small program in Java. (Trust me ... this is NOT a simple thing to do.) You need to apply this to your homework problem to decide which of the alternative solutions is fastest.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Note, though, that a Comparator can only compare Objects. The int[] array would have to be converted to Integer[], sorted, and converted back to int[].
0

I think you want something similar to partition algorithm used in quicksort.

4 pointers is a good start, but let me change their functions:
1) points to the end of remainder = 0
2) points to the end of remainder = 1
3) points to the end of remainder = 2
4) points to the start of unclassified

The array is split into 5 parts: remainder = 0, 1, 2, 3 and unclassified.

If remainder = 3, just increment the pointer 4. The number if included in remainder = 3 group.
If remainder = 2, increment the pointer 3 and swap the current value with the value at pointer 3. Increment pointer 4.
If remainder = 1, increment the pointer 2, swap with current value; increment the pointer 3, swap with current value. Increment pointer 4.
If remainder = 0, well, do the swapping 3 times.

Improve this answer

Comments

0

I think a better way to do this would be to have 4 arrays, one for each case. Treat each array as a queue. Iterate through the array and push onto the respective arrays. Once that is done, just append the arrays to each other. A very clean solution.

Improve this answer

1 Comment

if i want to use more arrays i need to calculate the complexity because it should be effecient
0

Why don't you create a custom class which holds two values, the number and the remainder. Create an array of this mini class, pass the values and pre-calculate your remainder. This will help you on not having to re-calculate the remainder every time you pass through an element of your list. You have to move and sort your elements based on the remainder property.

Then you have a classic problem of sorting a list with only few unique elements. The performance of the sorting algorithm you choose depends on the initial condition. I might say the best option is the Shell sorting algorithm or the Quick3.

http://www.sorting-algorithms.com/few-unique-keys

Improve this answer

1 Comment

Not sure if instantiating a class only to avoid a few modulo computations would be more efficient.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.