Labels

algorithms (22) Design Patterns (20) java (19) linux (14) Snippet (13) service mix (6) soa (4)

Selection Sort in Java

  • Find the smallest entry for an Index
  • Swap it with the index element do this iteratively till the end of the array

Complexity: (n power 2)/2  comparisions & n exchanges

 

 

  /**
     * find the minimum in the series and swap it to the index 
     * @param numbers
     */
    private static void sortList(Integer[] numbers) {
        for (int index = 0; index < numbers.length; index++) {
            int minIndex = findMininRest(index, numbers);
            if (minIndex != index) {
                swap(minIndex, index, numbers);
                printArray(numbers);
            }
        }
    }
    /**
     * swap 2 numbers at the index 
     * @param minIndex
     * @param index
     * @param numbers
     */
    private static void swap(int minIndex, int index, Integer[] numbers) {
        Integer temp = numbers[minIndex];
        numbers[minIndex] = numbers[index];
        numbers[index] = temp;
    }
    /**
     * find the minimum in the rest of the series
     * 
     * @param index
     *            the current index to fill
     * @param numbers
     *            all the numbers
     * @return returns the index of the minimum element in the rest series from
     *         index
     */
    private static int findMininRest(int index, Integer[] numbers) {
        int currentMin = index;
        for (int restIndex = index + 1; restIndex < numbers.length; restIndex++) {
            if (numbers[currentMin] > numbers[restIndex]) {
                currentMin = restIndex;
            }
        }
        return currentMin;
    }

Trace of the sort per Iteration


0 10 2 9 3 8 1 6 5 7 4 INPUT


0 1 2 9 3 8 10 6 5 7 4
0 1 2 3 9 8 10 6 5 7 4
0 1 2 3 4 8 10 6 5 7 9
0 1 2 3 4 5 10 6 8 7 9
0 1 2 3 4 5 6 10 8 7 9
0 1 2 3 4 5 6 7 8 10 9


0 1 2 3 4 5 6 7 8 9 10 OUTPUT

No comments:

Post a Comment

Search 24 Bytes

Loading...