Question

I want to sort my array by pushing the findMax number to the end of the list with this idea

The Idea of sort the arraylist: (assume that the arraylist has n elements)Search the n elements of the arraylist for the maximum value then put this maximum value at the last position of the arraylist. Hence at index n-1. Move all other elements forward. Search the first n- 1 elements of the arraylist for the maximum value then put this maximum value at the second to last position of the arraylist. Hence at index n-2. Move all other elements forward. Search the first n- 2 elements of the arraylist for the maximum value then put this maximum value at the third to last position of the arraylist. Hence at index n-3. Move all other elements forward. get this outcome:

Unsorted Size: 1 -> 580 Sorted Size: 1 -> 580 Average: 580.000

Median: 580.000

Unsorted Size: 2 -> 580 316 Sorted Size: 2 -> 316 580

Average: 448.000 Median: 448.000

Unsorted Size: 3 -> 316 Sorted Size: 3 -> 143 Average: 346.333

Median: 316.000

Unsorted Size: 4 -> 143 Sorted Size: 4 -> 143 Average: 486.500

Median: 448.000

Unsorted Size: 5 -> 143 Sorted Size: 5 -> 143 Average: 559.600

Median: 580.000

580 143 316 580

316 580 907 316 580 907

316 580 907 852 316 580 852 907

Unsorted Size: 6 -> 143 316 580 852 907 905 Sorted Size: 6 -> 143 316 580 852 905 907

Average: 617.167 Median: 716.000

Unsorted Size: 7 -> 143 316 580 852 905 907 700 Sorted Size: 7 -> 143 316 580 700 852 905 907

Average: 629.000 Median: 700.000

Unsorted Size: 8 -> 143 316 580 700 852 905 907 542 Sorted Size: 8 -> 143 316 542 580 700 852 905 907

Average: 618.125 Median: 640.000

Unsorted Size: 9 -> 143 316 542 580 700 852 905 Sorted Size: 9 -> 114 143 316 542 580 700 852

Average: 562.111 Median: 580.000

Unsorted Size: 23 -> 74 114 143 156 225 240 316 Sorted Size: 23 -> 74 114 143 156 225 240 316

Average: 577.348 Median: 674.000

Unsorted Size: 24 -> 74 114 143 156 225 240 316 Sorted Size: 24 -> 74 114 143 156 225 240 316

Average: 580.917 Median: 668.500

Unsorted Size: 25 -> 74 114 143 156 225 240 316 Sorted Size: 25 -> 74 114 143 156 225 240 316

Average: 591.720 Median: 674.000

I currently have

//******************************************************************************
// Imports
//******************************************************************************

import java.util.ArrayList;
import java.util.Random;

//******************************************************************************
// Code
//******************************************************************************
public class PA2 {

  
public static void main(String[] args)
{
int size=1;
int max=25;

for(size=1;size<=max;size++)
{

ArrayList<Integer>unsortedList=createRandomArray(size);
System.out.println("Unsorted Size: "+ size+" -> "+ unsortedList);

sortArray(unsortedList);
ArrayList<Integer>sortedList=unsortedList;
System.out.println("Sorted Size: "+size+" -> "+sortedList);

System.out.printf("Average: %.3f\n",average(sortedList));

System.out.printf("Median: %.3f\n",median(sortedList));
}
}
  
/* Generates method */
public static ArrayList<Integer> createRandomArray(int size)
{
ArrayList<Integer> array = new ArrayList<>(size);
Random randomGenerator = new Random ();
for (int i = 0; i<size;i++)
{
int randomNumber = randomGenerator.nextInt(100);
array.add(new Integer(randomNumber));
}
return array;
}
public static void sortArray(ArrayList<Integer> array)

/* Average method */
public static double average(ArrayList<Integer> array)
{
double total=0;
for(Integer value:array)
total+=value;
return total/array.size();
}
/* Median method */
public static double median(ArrayList<Integer> array)
{
Collections.sort(array);
int size=array.size();

if ( size% 2 != 0)
return (double)array.get(size/2);
  
return (double)(array.get((size-1)/2) + array.get(size/2))/2.0;
}
} //end of the class

Answer 1

Here is the implementation for the sort functionality you are looking for. In the array I am trying to find the index of the maximum element in the array between 0 and endIndex. Then i swap the two values, the value at endIndex with the value at maxNumIndex each time in a loop. Loop iterates from right to left in the array with the range to find maximum index decreasing by 1 from right with each iteration in the array. That is, the range to find maximum number is between 0 and endIndex all the time. The endIndex starts with the last element in the array and this value decrements by 1 each time within the loop.

/**

* Sort the array by moving the maximum value in the array to the last.

* @param array the array which needs to be sorted.

*/

public static void sortArray(ArrayList<Integer> array) {

ArrayList<Integer> testList = new ArrayList<>();

for (int i : array) {

testList.add(i);

}

Collections.sort(testList);

for (int index = array.size() - 1; index >= 0; index--) {

int maxNumIndex = findMaxNumIndex(array, index);

int temp = array.get(index);

array.set(index, array.get(maxNumIndex));

array.set(maxNumIndex, temp);

}

}

/**

* Find the index of the maximum number between 0 and the given end index.

* @param array the array in which maximum number index is to be found.

* @param endIndex the end index with in the array to search for.

* @return

*/

public static int findMaxNumIndex(ArrayList<Integer> array, int endIndex) {

int maxNumIndex = 0;

for (int i = 1; i <= endIndex; i++) {

if (array.get(i) > array.get(maxNumIndex)) {

maxNumIndex = i;

}

}

return maxNumIndex;

}

I tested these methods with the data you shared and they work as expected. I am sharing screenshots of the indented code along with sample output. Look at the java doc (comments above the two methods to understand what each method is doing).

Please let me know if you did not understand something here or in case you need help with anything else.