Selection Sort Program and Complexity (Big-O)


Selection sort is a simple sorting algorithm, it’s also known as in-place comparison sort. In selection sort algorithm, sorts an array of items by repeatedly finding the minimum item from unsorted part of array and move it at the beginning. This algorithm considers two sub arrays in a given array.

  1. The sub array of already sorted items.
  2. Remaining sub array unsorted items.

Points to remember

  • Data structure: Array
  • Worst-case performance : О(n2) comparisons and O(n)swaps
  • Best-case performance : O(n2) comparisons and O(n) Swaps
  • Average performance: О(n2) comparisons and O(n) Swaps
  • Worst-case space complexity :О(n) total, O(1) auxiliary

See Also : Data Structure and Algorithms Complexity (Big-O)

Advantage

  • Simple Implementation and efficient for small data set.
  • Efficient in  comparison to other Quadratic Sort (i.e O(n2)) like Bubble Sort or  Insertion Sort.
  • Efficient for data set that are already sorted. Time Complexity ( i.e O(n))
  • Not change relative order of elements which are already sorted. Space Complexity (i.e O(1))

Disadvantage

  • Selection sort is much less efficient on large lists in compare to algorithms such as quicksort, heapsort, or merge sort.

Selection Sort Steps

Here * marks the value set on particular iteration.

2 6 3 8 4 1 5 0
0* 6 3 8 4 1 5 2
0 1* 3 8 4 6 5 2
0 1 2* 8 4 6 5 3
0 1 2 3* 4 6 5 8
0 1 2 3 4* 6 5 8
0 1 2 3 4 5* 6 8
0 1 2 3 4 5 6* 8

Selection Sort with Loop

public class SelectionSort {
	public static void main(String[] args) {
		int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
		System.out.println("Before Selection Sorting :");
		printArray(items);

		// Perform selection sort
		selectionSort(items);

		System.out.println("After Selection Sorting :");
		printArray(items);
	}

	static void selectionSort(int items[]) {

		// select item one by one based on index
		for (int i = 0; i < items.length - 1; i++) {
			// Find the minimum item in unsorted array
			int min_idx = i;
			for (int j = i + 1; j < items.length; j++)
				if (items[j] < items[min_idx])
					min_idx = j;

			// Swap the found minimum selected item with
			// the first selected item
			int temp = items[min_idx];
			items[min_idx] = items[i];
			items[i] = temp;
		}
	}

	static void printArray(int items[]) {
		for (int item : items) {
			System.out.print(item + " ");
		}
		System.out.println();
	}
}

Output


Before Insertion Sorting :
2 6 3 8 4 1 5 0 
After Insertion Sorting :
0 1 2 3 4 5 6 8 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s