Sorting algorithm, insertion sort

Question

ive been trying to the problem and have become stuck. The specification of the problem is a as follows

Median of k numbers is defined as the (k/2)th smallest number if k is even; and the ((k+1)/2)th smallest number if k is odd. For example, median of the 4 numbers: 2 1 8 7 is the 2nd smallest number i.e. 2, and the median of the 5 numbers: 2 1 8 7 6 is the 3rd smallest number i.e. 6. In this problem, you'll be given N numbers. Let the kth median or m(k) be defined as the median of the first k numbers (1<=k<=N). i.e. the 5th median or m(5) is the median of the first 5 numbers, the 8th median or m(8) is the median of the first 8 numbers, etc. In other words, let Ai denote the ith number, then the kth median or m(k) is defined as the median of the numbers A1, A2, …, Ak. Your task is to find m(1) + m(2) + m(3) + ...+ m(n), output the sum modulo 100000

so basically you have to read in numbers, first number is stored in the variable N and dictates how many numbers to be read in after that point is. (this is always 5). Then you must iterate through the reading in of the numbers, storing them in array, then sorting them and then finding the median of the median and then store the value in the and repeating until all numbers have been read in, sorted and median found.

I have managed to read the numbers in fine and i am able to sort them to some degree but my sorting algorithm, sorts them highest values first and smallest values last and in order to get the program to run properly to get the desired output i need it to be the other way round and i cant work out how.

The numbers read in will be like so

5

10

5

1

2

15

and the answer would be 27.

This is my code

Any help on this problem would be amazing because im just going round in cirles, btw the System.out.println(myIntArray [4]) etc is just a tracer to see how the sorting is taking place

Answer 1

You seem to be sorting the entire array each time through. You need to sort from 0 to i (exclusive) at each iteration. Also, for odd length, you need parentheses when computing the subscript: myIntArray[(i+1)/2] instead of myIntArray[i+1/2]. Because of operator precedence, Java will evaluate the latter as myIntArray[i+(1/2)], which is just myIntArray[i], since 1/2 is 0 in integer division.