Selection sort

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.

How Selection Sort Works?

Consider the following elements are to be sorted in ascending order using selection sort-

6, 2, 11, 7, 5

Selection sort works as-

  • It finds the first smallest element (2).
  • It swaps it with the first element of the unordered list.
  • It finds the second smallest element (5).
  • It swaps it with the second element of the unordered list.
  • Similarly, it continues to sort the given elements.

As a result, sorted elements in ascending order are-

2, 5, 6, 7, 11

Algorithm of the Selection Sort Algorithm

The selection sort algorithm is as follows:

Step 1: Set Min to location 0 in Step 1.

Step 2: Look for the smallest element on the list.

Step 3: Replace the value at location Min with a different value.

Step 4: Increase Min to point to the next element

Step 5: Continue until the list is sorted.

 Example

Time Complexity Analysis-

  • Selection sort algorithm consists of two nested loops.
  • Owing to the two nested loops, it has O(n2) time complexity.

  • Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of selection sort is O(n2).
  • Average Case Complexity - It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of selection sort is O(n2).
  • Worst Case Complexity - It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of selection sort is O(n2).

Space Complexity Analysis-

  • Selection sort is an in-place algorithm.
  • It performs all computation in the original array and no other array is used.
  • Hence, the space complexity works out to be O(1).

Important Notes-

  • Selection sort is not a very efficient algorithm when data sets are large.
  • This is indicated by the average and worst case complexities.
  • Selection sort uses minimum number of swap operations O(n) among all the sorting algorithms.

Applications of Selection Sort:

The selection sort technique has the following applications:

  • Applicable for smaller datasets.
  • Used in those algorithms where the cost of swapping does not matter.
  • It cannot work for online data. It needs to have all the array elements for each iteration.
  • Best suitable when the cost of writing in flash memory matters.

Popular posts from this blog

DATA STRUCTURES-II

 UNIT – I  Tree: Header nodes, Threads, Binary search trees, Searching, Insertion and deletion in aBinary search tree , AVL search trees, Insertion and deletion in AVL search tree , m-waysearch tree, Searching, Insertion and deletion in an m-way search tree , B-trees, Searching,Insertion and deletion in a B-tree, B+tree , Huffman’s algorithm , General trees.  UNIT – II  Graphs: Warshall’s algorithm for shortest path , Dijkstra algorithm for shortest path , Operations on graphs , Traversal of graph , Topological sorting .  UNIT – III  Sorting: Internal & external sorting , Radix sort , Quick sort , Heap sort , Merge sort . Searching: Liner search, binary search, merging , Comparison of various sorting and searching algorithms on the basis of their complexity .  UNIT – IV  Files: Physical storage devices and their characteristics , Attributes of a file viz fields, records,Fixed and variable length records, Primary and secondary keys , Clas...
Read more

DATA STRUCTURES FOR BCA

UNIT – I  Introduction: Elementary data organization, Data Structure definition , Data type vs. data structure , Categories of data structures, Data structure operations, Applications of data structures, Algorithms complexity and time-space tradeoff, Big-O notataion.   Strings: Introduction, Storing strings, String operations, Pattern matching algorithms.  UNIT – II  Arrays: Introduction, Linear arrays, Representation of linear array in memory, address calculations, Traversal, Insertions, Deletion in an array, Multidimensional arrays, Parallel arrays, Sparse arrays.  Linked List: Introduction, Array vs. linked list, Representation of linked lists in memory, Traversal, Insertion, Deletion, Searching in a linked list, Header linked list, Circular linked list, Two-way linked list, Threaded lists, Garbage collection, Applications of linked lists.  UNIT – III  Stack: Introduction, Array and linked representation of stacks, Operations on stacks, Ap...
Read more

DATA STRUCTURES FOR B.TECH

DATA STRUCTURES Unit 1: Introduction :   Basic Terminologies:   C oncept of Data Structure, Choice of right Data Structure , Algorithms , how to design and develop algorithm, Complexity of algorithm.   Operations: insertion, deletion, traversal etc,   Analysis of an Algorithm. Searching:  Linear Search and Binary Search Techniques and their complexity analysis. Unit 2: Stacks  and  Queues : Stack  and  its  operations: Algorithms and their complexity analysis, Applications of Stacks: Expression       Conversion and evaluation -corresponding algorithms and complexity analysis. queue, Types of Queue: Simple  Queue, Circular Queue, Priority Queue ; Operations on each types of Queues: Algorithms and their analysis.   Unit 3 : Linked Lists:      Singly   linked  lists: Representation in memory, Algorithms of several operations:...
Read more