Sorting random non-repeating numbers

Question

I am working on a program in which 10000 random non-repeating numbers are selectively sorted into ascending order"

import java.util.Random;


public class Sorting {
    public static void main (String[] args){
        //Here, we initiate an array with the integers
        //1 through 10,000 in order.
        Random rgen = new Random();
        int[] intArray = new int[10000];
        for (int i=0; i<10000; i++) {
            intArray[i] = i+1;
        }
        //Here, we randomize the positions.
        for (int i=0; i<10000; i++) {
            int randomPosition = rgen.nextInt(10000);
            int temp = intArray[i];
            intArray[i] = intArray[randomPosition];
            intArray[randomPosition] = temp;
        }
        //Here, we check for the maximum in the 
        //unsorted section of the list.
        int max;
        for (int i=9999; i>=0; i--) {
            max = i;
            for (int j=i-1; j>=0; j--)
                if (intArray[j]>intArray[max]) {
                    max = j;
                }
            //Here, we swap the positions of the 
            //maximum and the last value in the 
            //unsorted section of the list.
            if (max != i) {
                int tmp = intArray[i];
                intArray[i] = intArray[max];
                intArray[max] = tmp;
            }
        }
        //Here, we output the result.
        for (int k=0; k<10000; k++) {
            System.out.println(intArray[k]);
        }
    }
}

Answer 1

Comments

You're adding a bunch of comments almost everywhere in your code. Let see see what does your comments say about your code.

//Here, we initiate an array with the integers
//1 through 10,000 in order.
Random rgen = new Random();
int[] intArray = new int[10000];
for (int i=0; i<10000; i++) {
    intArray[i] = i+1;
}

Your comments is saying exactly what your code is doing. In fact, I don't really need your comment to know what you're doing. A for-each loop is really common and storing integer in an array is nothing new in the programming world. So is a comment a good way to convey that ? I think not.

I could go through each of your comment and say the same thing, but what your comment really tell to me is that this specific piece of code have a specific function. So if you have take the time to explain what this specific piece of code, why not encapsulate it in a function. The method signature of the previous code block could look like this : public static int[] populateArrayFrom1To10000()

Magic Number

You have hard coded 10000 almost everywhere in your code. What if you want to change it to 50000 to test something? You would need to change each occurrence of the number to the new one. One good thing to do is to extract the number to a constant and use this variable instead of "hard-coding" it.

Be aware that refactoring your method in different functions will do something like that. You will have a parameter for each of your functions and will minimize the occurrence of the magic number.

Minor note

  for (int i=0; i<10000; i++) {
        intArray[i] = i+1;
  }

I would re-write this loop for this one :

  for (int i=1; i=<10000; i++) {
        intArray[i] = i;
  }

This is minor, but I find it more clear that you're going through every number and assign it to the array. There is no meaning in doing i + 1 as you don't really need to add 1 to i if you change your loop to actually go to 10000.

Answer 2

I tested it and it works as it should. I would only like to remark a couple of things.

You may want to split your long commented function into shorter ones:

• static int[] InitArray(int length){...}

• static int[] SelectionSort(int[]arr){...}

• static void Swap(int[]arr, int i, int j){...}

• print the result in the main(), as you do know.

This makes your code easier to read and easier to reuse.

Another thing I'd remove is the if(max != i). I'd rather make the swap every time. If you look carefully, there's small chance that you do this operation unnecessarily, and when you do do it, it won't harm you.

Note: If you keep doing the swap as you do now, you won't have any problem by removing the if. However, if you modify it to make the swap without a temp variable, it might go wrong.

Answer 3

Your code for finding the maximum of an array is wrong. It should be

int maxIndex = 0;
for(int k = 1; k < intArray.length; k++)
    if(intArray[k] > intArray[maxIndex])
        maxIndex = k;

Additionally, you will have to run the sorting code intArray.length times if you want the array to be truly sorted. This type of sort takes O(n^2) time, as opposed to O(nlogn) of quicksort.