selection sort

Selection Sort in Java and Complexity Analysis

Selection sort is a sorting algorithm, precisely an in-place comparison sort. The selection sort improves over the bubble sort by reducing the number of swapping necessary from O(n2) to O(n). But the number of comparisons remains O(n2).

Selection Sort Java Example

Output

Note: At each new position of j, the elements inArray[j] and inArray[min] are compared. At the end of the inner loop, min points to the minimum value and the array elements pointed to by j and min are swapped.

Time Complexity

The selection sort performs the same number of comparisons as the bubble sort, which is n*(n-1)/2. However the number of swaps required is fewer when compared to bubble sort. But for larger values of n, the comparison time will dominate compared to swap time, so we should say that selection sort runs in O(n2) time like bubble sort.

Space Complexity

The space for section sort is O(1), because the above algorithm requires only a single additional memory space for temp variable.

Recommended Posts

References:

  1. Different kinds of sorting
  2. Wikipedia sorting algorithm

Leave a Reply

avatar
  Subscribe  
Notify of