Skip to main content

Posts

Showing posts with the label selection sort

Scala language implementation of Selection Sort

Introduction Selection sort is the simplest sorting algorithm in terms of implementation. Let's consider we have a list of elements i.e. {3, 9, 0, 5, 4 } a) Selection sort maintains two sublists, one sorted and initially empty and second unsorted sublist i.e. [ {}, {3, 9 , 0, 5 ,4 }] b) It searches for the minimum element (for ascending sort) OR for a maximum element( for descending sort) in the unsorted list in each step. Step 1 [ {0 }, {9,3,5,4}] Minimum element = 0 , swapped with 3 Step 2 Minimum element = 3 , swapped with 9 [{0,3) , {9,5,4} ] Step 3 Minimum element = 4 , swapped with 9 [{0,3,4} , {5,9}] Step 4 Minimum element = 5 , swapped with itself [{0,3,4,5}, {9}] Step 5 Minimum element = 9 , swapped with itself [{0,3,4,5,9}, {}] Worst Complexity: O(n*n) Best Complexity   : O(n * n) Implementation package main.scala object SelectionSort { val array = Array(0, 5, 2, 6, 3, 1) def main(args: Array[String]) { print(&quo

Java Example of Selection Sort

Introduction Selection sort is the simplest sorting algorithm in terms of implementation. Let's consider we have a list of elements i.e. {3, 9, 0, 5, 4 } a) Selection sort maintains two sublists, one sorted and initially empty and second unsorted sublist i.e. [ {}, {3, 9 , 0, 5 ,4 }] b) It searches for the minimum element (for ascending sort) OR for a maximum element( for descending sort) in the unsorted list in each step. Step 1 [ {0 }, {9,3,5,4}] Minimum element = 0 , swapped with 3 Step 2 Minimum element = 3 , swapped with 9 [{0,3) , {9,5,4} ] Step 3 Minimum element = 4 , swapped with 9 [{0,3,4} , {5,9}] Step 4 Minimum element = 5 , swapped with itself [{0,3,4,5}, {9}] Step 5 Minimum element = 9 , swapped with itself [{0,3,4,5,9}, {}] Worst Complexity: O(n*n) Best Complexity   : O(n * n) Imperative style implementation using Java 7 public class SelectionSortExample { private static int array[] = {3,9,0,5,4}; public static void mai