Fast way to sort a list of enum with values

Question

SOLUTION FOUND!

I'm trying to find a way how to implement this code.

What I need to do is to find fast methods to rearrange the array, so that all cheese objects would be a part of the first part of the array and all milk objects are in the middle of the array and bread objects are at the end.

Any help here?

public class Shop {

    enum shoppingList {cheese, milk, bread};

    public static void rearrange (shoppingList[] shopping) {
        shoppingList cheese = shoppingList.cheese;
        shoppingList milk = shoppingList.milk;
        shoppingList bread = shoppingList.bread;

       
    }
}

If this answers your question (I think it does) let us know and we can close this one as a duplicate: https://stackoverflow.com/questions/18895915/how-to-sort-an-array-of-objects-in-java — ControlAltDel, Sep 04 '20 at 18:52
Can you really call it a "shopping list" if there's only milk & cheese? — Kayaman, Sep 04 '20 at 18:54
You can use `Arrays.sort` to sort by ordinal like `Arrays.sort(shopping);` — Eklavya, Sep 04 '20 at 18:55
You could even use `Arrays.stream(shopping).sorted(new Comparator(...` and apply your own comparator for more complex conditions — Mauricio Guzinski, Sep 04 '20 at 19:06
This question is specific about enum list with just two values, please don't change the title to "sort list in java" because that's not the problem to solve (see [`List.sort()`](https://docs.oracle.com/javase/10/docs/api/java/util/List.html#sort(java.util.Comparator)) method for that). — Karol Dowbecki, Sep 04 '20 at 22:08
If you found a solution mark the answer as helpful and remove the "SOLUTION FOUND" from the question. — Karol Dowbecki, Sep 06 '20 at 19:49

Karol Dowbecki · Answer 1 · 2020-09-04T19:31:21.797

2

Since you have only enums, which technically don't have object identity and can be represented as integers, the usual comparative sort e.g. Quicksort is not the best approach as it won't be better than O(n long n).

A non-comparative sort will be faster (e.g. Radix Sort will be O(w n)) but in this problem you only have two distinct values so sorting can be done in single array pass with O(n).

You can implement it as:

Iterate over the array with a counter i.
Each time you spot a milk swap it with the last element in the array which is not milk.
Remember how many elements at the end are milk by storing it in a counter j.
Stop when i reaches j.

So it could be something like:

enum Food { MILK, CHEESE };

void sortMilkLast(Food[] arr) {
    int i = 0;
    int j = arr.length - 1;
    while (j >= 0 && arr[j] == MILK) {
        j--; // avoid swapping MILK already in place
    }
    while (i <= j) {
        if (arr[i] == MILK) {
            arr[i] = arr[j]; // this should always be a CHEESE
            arr[j] = MILK;
            j--;
            while (j >= 0 && arr[j] == MILK) {
                j--; // avoid swapping MILK already in place
            }
        }
        i++;
    }
}

Remember that complexity is not performance and for small arrays (e.g. 5 elements) the difference in approach will make little difference in sorting time.

edited Sep 04 '20 at 19:31

answered Sep 04 '20 at 19:01

Karol Dowbecki

43,645
9
78
111

3

I suggest denoting the sorting method. If I recall, correctly, the algorithm is known as the bubble sort algorithm. In this case, it is specifically the best case scenario of the bubble sort algorithm which is in fact theta(n). – George Xavier Sep 04 '20 at 19:04
1

@GeorgeXavier I never had to think how to sort an array with just two elements, is this a solved problem e.g. with specific algorithm? – Karol Dowbecki Sep 04 '20 at 19:12
Actually now that I think about it, it would not be O(n) it would be O(n^2) my bad. But that algorithm defined is bubble sort. – George Xavier Sep 04 '20 at 19:16
1

@GeorgeXavier I'm swapping with last element in array, not with next. I guess that's not bubble sort it feels like improved selection sort as I'm hoping that most cheese elements are in place. – Karol Dowbecki Sep 04 '20 at 19:17
then perhaps insertion sort? I misread the swapping. Each time you find one, you move it to the back. It's either insertion or selection, albeit a "reverse" selection if that is a thing. Edit: Found it: https://www.geeksforgeeks.org/sort-array-containing-two-types-elements/ – George Xavier Sep 04 '20 at 19:18

George Xavier · Answer 2 · 2020-09-04T19:53:36.257

This algorithm works in O(n) if and only if the array contains 2 distinct elements. First, you should convert the two distinct elements to 0 or 1.

//Driver
public static void main(String[] args) { 

      int arrOfValues[] = { 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1 };


      sortArray(arrOfValues, arrOfValues.length); 
      
      //print array
      for (int loopInt : arrOfValues) {
          
          System.out.print(loopInt + " "); 
      }
}

static void sortArray(int arr[], int n) {

    int valueFor0 = 0; 
    int valueFor1 = n - 1; 

    while (valueFor0 < valueFor1) { 
        
        if (arr[valueFor0] == 1) { 

            // swap type0 and type1 
            arr[valueFor0] = arr[valueFor0] + arr[valueFor1]; 
            arr[valueFor1] = arr[valueFor0] - arr[valueFor1]; 
            arr[valueFor0] = arr[valueFor0] - arr[valueFor1]; 
            valueFor1--; 

        } else { 
        
            valueFor0++; 
        } 
    } 
}

score 0 · Answer 3 · answered Sep 04 '20 at 20:34

It appears here cheese values needs to be moved to the start of array and as long as only two values are used here, rearrange method may be written as:

    public static void rearrange (shoppingList[] shopping) {
        int cheesePos = 0;
        int n = shopping.length;
        // move all cheese to the start
        for (int i = 0; i < n; i++) {
            if (shopping[i] == shoppingList.cheese) {
                shopping[cheesePos++] = shoppingList.cheese;
            }
        }
        // fill the rest with milk
        while (cheesePos < n) {
            shopping[cheesePos++] = shoppingList.milk;
        }
    }

Fast way to sort a list of enum with values

3 Answers3