I have the following code where I am trying to create a sorting algorithm that finds the min and max elements in an array, exchanges those elements with the first and last elements in the array, and then reduces the array's size by 2 after excluding the two elements that are already in the proper positions, and repeats that process again until the array is sorted.

I am aware that one can use an int[] array as the main array, but I went with an ArrayList for this instead. After removing the two elements from the ArrayList, the program is supposed to find the next min and max, but for whatever reason, the min and max are still the previous elements that were supposedly removed. I even adjusted the left and right index variables.

How would I fix this issue?

public static int[] novel_sort(ArrayList<Integer> array) {
        //array for sorted elements
        int[] sorted = new int[array.size()];
        //variables
        int left = 0;    
        //int right = fully_sorted.length - 1;    
        int right = array.size() - 1;
        int min = array.get(0);       //both min and max initially start at first element
        int max = array.get(0);
        
        while (array.isEmpty() != true) {
            //compare elements and interchange min and max until found
            for (int i = 0; i < array.size(); i  ) {
                if (array.get(i) > max) {
                    max = array.get(i);
                }
                else if (array.get(i) < min || array.get(i) == min) {
                    min = array.get(i);
                }
            }
            //insert elements into 'sorted' array
            sorted[left] = min;
            sorted[right] = max;
        
            //remove elements
            array.remove(array.indexOf(min));
            array.remove(array.indexOf(max));
            
            
            //decrement and increment the indices (going inward)
            right--;
            left  ;
        }
       
         for (int i = 0; i <= (sorted.length - 1); i  ) {
            System.out.println(sorted[i]);
        }
         return sorted;
}

CodePudding user response：

This initialization must be in the for loop:

int min = array.get(0);       //both min and max initially start at first element
int max = array.get(0);

Some other considerations:

1. You should also consider when min and max are having the same value, what will you do in that scenario? The same value can be either pointing to same index, but it can also point to different index i.e. duplicated values.

2. Try to sort even number of integers, then try odd number of integers. Do both works?

3. Should you store the min max index instead of the min max value?

CodePudding user response：

Assume you have a list of array elements a1,a2,a3,....,an such that a1<a2<a3<a4<.....,<an (sorted list). Applying the above algorithm to this list ,after first iteration of for loop min holds the value of a1 and max holds the value of an. This values get stored in the values in array sorted[0] and sorted[arr.size-1]. After that the algorithm removed the a1,an and but did not changed the values of max and min. They still holds a1 and an. Since there are no values less than a1 and greater than an , the values of max and min doesn't change . Thus during successive iteration - sorted[0],sorted[1],......,sorted[array.size()/2 -1] holds the values of a1 and sorted[array.size()/2 1]...., sorted[array.size-1] holds the value of an.

[Solution] --- Initialize the value of max and min after the while loop.

[Tips]- If you are stuck in a problem try to output the values of intermediate variables like max and min and check what values are they holding when the program runs. This might give you an idea where the code might went wrong. The time complexity of this algorithm is quadratic why not use Mergesort or Heapsort!!

CodePudding user response：

You need to reset min and max on each iteration of the while loop.
Just move the following two lines of your code to inside that loop.

int min = array.get(0);       //both min and max initially start at first element
int max = array.get(0);

The entire method (with some optimizations and adhering to Java naming conventions) as a minimal, reproducible example:

import java.util.ArrayList;
import java.util.Arrays;

public class Exercise {

    public static int[] novelSort(ArrayList<Integer> array) {
        //array for sorted elements
        int[] sorted = new int[array.size()];
        //variables
        int left = 0;
        //int right = fully_sorted.length - 1;
        int right = array.size() - 1;

        while (!array.isEmpty()) {
            int min = array.get(0);       //both min and max initially start at first element
            int max = array.get(0);
            //compare elements and interchange min and max until found
            for (int i = 0; i < array.size(); i  ) {
                int elem = array.get(i);
                if (elem > max) {
                    max = elem;
                }
                else if (elem < min) {
                    min = elem;
                }
            }
            //insert elements into 'sorted' array
            sorted[left] = min;
            sorted[right] = max;

            //remove elements
            array.remove(array.indexOf(min));
            array.remove(array.indexOf(max));

            //decrement and increment the indices (going inward)
            right--;
            left  ;
        }
        for (int i = 0; i <= (sorted.length - 1); i  ) {
            System.out.println(sorted[i]);
        }
        return sorted;
    }

    public static void main(String args[]) {
        novelSort(new ArrayList<>(Arrays.asList(5, 4, 3, 2, 1, 0)));
    }
}