• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
  • Skip to footer
  • Core Java
  • Design Patterns
  • JSP
  • Servlets
  • Building Tools
  • jQuery
  • Spring
  • Hibernate
  • Mongo DB
  • More
    • HTML
    • SCJP
    • AJAX
    • UML
    • Struts
    • J2EE
    • Testing
    • Angular JS

J2EE Reference

  • Home
  • About Us
    • Java Learning Centers
  • Contact Us

Selection Sort in java

June 10, 2015 By j2eereference Leave a Comment

Selection Sort in java

 

The idea behind selection sort is we put the smallest item at the start of the list, then the next smallest item at the second position in the list, and so on until the list is in order.

Algorithm:

1
2
3
4
5
6
7
8
9
10
11
for i=0 to N-2
{
    set smallest = i
    for j=i+1 to N-1
    {
       compare list[smallest] to list[j]
       if list[smallest] > list[j]
       smallest = j
    }
    swap list[i] and list[smallest]
}

 

Example:

72  69  27  92  7  52  65  37  69  28

We indicate the initial sub-array with square brackets and the smallest element outside the array with round brackets:

72  69  27  92  (7)  52  65  37  69  28 — find smallest

7  69  27  92  (72)  52  65  37  69  28 — swap with first outside

7   69  (27)  92  72  52  65  37  69  28 — find

7   27  (69)  92  72  52  65  37  69  28 — swap

[7 27 ] 69 92 72 52 65 37 69 (28) — find

[7 27 ] 28 92 72 52 65 37 69 (69) — swap

[7 27 28 ] 92 72 52 65 (37) 69 69 — find

[7 27 28 ] 37 72 52 65 (92) 69 69 — swap

[7 27 28 37 ] 72 (52) 65 92 69 69 — find

[7 27 28 37 ] 52 (72) 65 92 69 69 — swap

[7 27 28 37 52 ] 72 (65) 92 69 69 — find

[7 27 28 37 52 ] 65 (72) 92 69 69 — swap

[7 27 28 37 52 65 ] 72 92 (69) 69 — find

[7 27 28 37 52 65 ] 69 92 (72) 69 — swap 4

[7 27 28 37 52 65 69 ] 92 72 (69) — find

[7 27 28 37 52 65 69 ] 69 72 (92) — swap

[7 27 28 37 52 65 69 69 ] (72) 92 — find

[7 27 28 37 52 65 69 69 ] (72) 92 — swap

[7 27 28 37 52 65 69 69 72 ] (92) — find

[7 27 28 37 52 65 69 69 72 ] (92) — swap

[7 27 28 37 52 65 69 69 72 92] — Done.

 

Java implementation of selection sort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void selectionSort(int[] list)
{
int minIndex; // index of current minimum item in array
boolean newMinFound = false; // indicates if we need to swap
// items or not on this pass
for (int i=0; i < list.length-1; i++)
{
minIndex = i;
for (int j=i+1; j < list.length; j++)
{
if (list[j] < list[i])
{
// new minimum found, update minIndex
minIndex = j;
newMinFound = true;
}
}
if (newMinFound)
{
swap(list,i,minIndex);
}
newMinFound = false; // reset our ‘‘swap’’ flag
}
}

The swap method looks like this

1
2
3
4
5
6
7
8
9
10
11
public void swap(int[] list, int index1, int index2)
{
// Save a copy of the number at the first index, so that
// we don’t overwrite it
int temp = list[index1];
// Copy number at second index into first index slot
list[index1] = list[index2];
// Copy number that was originally in the first index slot
// into the second index slot.
list[index2] = temp;
}

Notice that we don’t return the array after we swap the two items. This is one feature of arrays, and of objects in general: because we refer to an array by its address, if we change an item in the array within a method, the change holds outside of the method

Performance of selection sort:

  1. The best case for selection sort occurs when the list is already sorted. In this case, the number of swaps is zero. We still have to compare each item in the list to each other item in the list on each pass through the 6 algorithm. The first time through, we compare the first item in the list to all other items in the list, so the number of comparisons is (N-1). The second time through, we compare the second item in the list to the remaining items in the list, so the number of comparisons is (N-2). It turns out that the total number of comparisons for selection sort in the best case is (N − 1) + (N − 2) + … + 2 + 1. This equation simplifies to N(N + 1)/2 − 1, which is approximately N2 . Thus, even in the best case, selection sort requires O(N2 ) comparisons.
  2. The worst case for selection sort occurs when the first item in the list is the largest, and the rest of the list is in order. In this case, we perform one swap on each pass through the algorithm, so the number of swaps is N. The number of comparisons is the same as in the best case, O(N2 ).
  3. The average case requires the same number of comparisons, O(N2 ), and roughly N/2 swaps. Thus, the number of swaps in the average case is O(N).

 

Let’s see whether selection sort is stable and in-place or not:

Stability:

Stable means that elements with the same key appear in the same order in the sorted array as they did in the original.

Selection sort algorithm is not stable because:

Selection sort algorithm picks the minimum and swaps it with the element at current position.
Suppose the array is:5 2 3  8 4 5 6
Let’s distinguish the two 5’s as 5(a) and 5(b) .
So our array is:
5(a)  3 4  5(b) 2 6 8

After iteration 1:
2 will be swapped with the element in 1st position:

So our array becomes:
2 3 4 5(b) 5(a) 6 8
Since now our array is in sorted order and we clearly see that 5(a) comes before 5(b) in initial array but not in the sorted array.
So we can clearly see that selection sort is not stable.

 

In place:

In place means it uses the array passed in and the sorting algorithm is only allowed to use constant extra space.

For in-place implementation in Java, starting from 1st index, find the smallest element (takes O(n) ) and put it at the first index of unsorted sub array. So there will be 2 parts of main array, left one will have sorted element and right one will have unsorted. We choose smallest from the right one and will put it at the beginning of the unsorted sub array. Now Sorted array will have one more element and unsorted array will have one less. Continue this process till we reach the end of element. ( takes O(n)). So finding smallest for one loop will take O(n) and there will be at most n loop so it total time in worst case will be O(n^2).

Related Posts

  • Busy Spinning in mutithreading
  • Implementing queue in java
  • TreeSet vs ConcurrentSkipListSet
  • How to create immutable class?
  • Implementing Stack in java
  • What is ReentrantLock?
  • What is Semaphore in java
  • Why AtomicInteger class
  • What is CyclicBarrier?
  • CountDownLatch in java

Filed Under: Core Java

Reader Interactions

Leave a Reply Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Primary Sidebar

FOLLOW US ONLINE

  • View J2eereference-166104970118637’s profile on Facebook
  • View j2eereference’s profile on Twitter
  • View j2eereference’s profile on LinkedIn

Subscribe by email

Recent posts

  • What is parallel Stream
  • reduce method of the Stream class
  • Difference between the findFirst() and findAny() method
  • intern() method of String class
  • SOLID – Five principles of object-oriented software design
  • Java Coding Best Practices
  • How to use lambda expression effectively
  • Enhanced pseudo-Random Number Generators in java17
  • How to use Foreign-Memory Access API
  • Pattern Matching for instanceof
  • Text Blocks – Feature added in Java17
  • Record – The new feature added in java 17
  • What is Sealed Class
  • Features added in Java 17
  • Java Buzzwords

Footer

Core Java
Design Patterns
JSP
Servlets
HTML
Building Tools
AJAX
SCJP
jQuery
Testing
Spring
UML
Struts
Java Centers
Java Training
Home
About Us
Contact Us
Copyright © j2eereference.com. All right reserved.