Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

Selection Sort in Java

farenda 2016-07-25 0

Selection Sort in Java

Selection Sort is one of many sorting algorithms, but unlike a few others it is easy to understand and implement as we’re going to show here!

How it works

The sorting algorithm consists of 3 elements:

  1. Iteration over given elements.
  2. Finding index of the smallest number (selection), starting from the current position up to the end of the given array.
  3. Swapping the smallest element with the one at current position.

Notice that the algorithm goes through the input array only once (linear execution time), but the selection part is executed for each step and also goes through whole input array, but -1 in each loop. Swap is executed values.length times.

Selection Sort properties

  • the running time is ϴ(n²) (Big Theta n²), which means that it won’t run faster nor slower than n²,
  • doesn’t have worst nor best case and always run in ϴ(n²),
  • selection (indexOfMinimum method) will be executed n²/2 + n/2 times,
  • memory complexity in O(1), because the algorithm reuses the same array.

Selection Sort implementation

package com.farenda.tutorials.algorithms.sorting;

public class SelectionSorter {

    public void sort(int[] values) {
        for (int i = 0; i < values.length; i++) {
            int minPos = indexOfMinimum(values, i);
            swap(values, i, minPos);
        }
    }

    private int indexOfMinimum(int[] values, int i) {
        int minPos = i;
        for (; i < values.length; ++i) {
            if (values[i] < values[minPos]) {
                minPos = i;
            }
        }
        return minPos;
    }

    private void swap(int[] values, int first, int second) {
        int tmp = values[first];
        values[first] = values[second];
        values[second] = tmp;
    }
}

Notice that all parts of the algorithm have been implemented in separate methods. This make code more readable and is good style. If you are worried about the cost of calling methods in a loop, then no need to. JVM Hot-Spot is taking care of that and will optimize (e.g. inline methods) code where needed.

Unit tests

Let’s write a couple of JUnit tests to make sure that our implementation of Selection Sort algorithm behaves correctly:

package com.farenda.tutorials.algorithms.sorting;

import org.junit.Test;

import static org.junit.Assert.assertArrayEquals;

public class SelectionSortTest {

    private SelectionSorter sorter = new SelectionSorter();

    @Test
    public void shouldDoNothingWithEmptyArray() {
        int[] values = {};

        sorter.sort(values);
    }

    @Test
    public void shouldDoNothingWithOneElementArray() {
        int[] values = {42};

        sorter.sort(values);

        assertArrayEquals(new int[] {42}, values);
    }

    @Test
    public void shouldSortValues() {
        int[] values = { 9, -3, 5, 0, 1};
        int[] expectedOrder = { -3, 0, 1, 5, 9};

        sorter.sort(values);

        assertArrayEquals(expectedOrder, values);
    }
}

References:

  • Binary Search is expecting to receive sorted data
Share with the World!
Categories Algorithms Tags algorithms, java
Previous: Clojure for loop
Next: Insertion Sort in Java

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2021

sponsored
We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.Ok