Fast way to sort a list of enum with values

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;

       
    }
}

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:

1. Iterate over the array with a counter i.

2. Each time you spot a milk swap it with the last element in the array which is not milk.

3. Remember how many elements at the end are milk by storing it in a counter j.

4. 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.

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++; 
        } 
    } 
} 

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;
        }
    }