Selection Sort

Selection: Google Images
Selection sort is another O(N2) worst case time complexity algorithm.

 It repeatedly finds the minimum element from the unsorted part.
As the name suggests it "selects" a position in the array and finds out the minimum element from current position till the last index.

Algorithm:

// for an array of size n
1. for i = 0 to n-1
2.  for j = i+1 to n-1
3.   if arr[i] > arr[j]
4.    swap(arr[i], arr[j])
5.   end if
6.  end for
7. end for

Example:

Let the arr = [3, 2, 4, 1, 5]
n = 5
1.  i = 0, j = 1
    arr[i] = 3, arr[j] = 2
    arr[i] > arr[j] -> swap(3, 2)
    updated arr = [2, 3, 4, 1, 5]
    
    i = 0, j = 2
    arr[i] = 2, arr[j] = 4
    arr[i] < arr[j] -> skip
    
    i = 0, j = 3
    arr[i] = 2, arr[j] = 1
    arr[i] > arr[j] -> swap(2, 1)
    updated arr = [1, 3, 4, 2, 5]
    
    i = 0, j = 4
    arr[i] = 1, arr[j] = 5
    arr[i] < arr[j] -> skip
    
    i = 0, j = 5
    j > n-1 -> break internal loop

Updated arr after 1st iteration -> arr = [1, 3, 4, 2, 5]
As you can see the smallest element of the arr[0...(n-1)], 1, came at index 0 
after the first iteration completed.

2.  i = 1, j = 2
    arr[i] = 3, arr[j] = 4
    arr[i] < arr[j] -> skip
    
    i = 1, j = 3
    arr[i] = 2, arr[j] = 2
    arr[i] > arr[j] -> swap(3, 2)
    updated arr = [1, 2, 4, 3, 5]
    
    i = 1, j = 4
    arr[i] = 2, arr[j] = 5
    arr[i] < arr[j] -> skip
    
    i = 1, j = 5
    j > n-1 -> break internal loop

Updated arr after 2nd iteration -> arr = [1, 2, 4, 3, 5]
As you can see the smallest element of the arr[1...(n-1)], 2, came at index 1 
after the second iteration completed.

Similarly after the 3rd iteration updated arr will be -> arr = [1, 2, 3, 4, 5]
Similarly after the 4rd iteration updated arr will be -> arr = [1, 2, 3, 4, 5]

Code in Python:

# selection sort function
def selection_sort(arr):
    n = len(arr)
    for i in range(0, n):
        for j in range(i+1, n):
            # if the value at i is > value at j -> swap
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]


# input arr
arr = [3, 2, 4, 1, 5]
print('Before selection sort:', arr)

# call selection sort function
selection_sort(arr)
print('After selection sort:', arr)

"""
Output:
Before selection sort: [3, 2, 4, 1, 5]
After selection sort: [1, 2, 3, 4, 5]
"""

Time Complexity:

Selection sort has the same worst case and average case time complexity i.e. O(N2) as in each iteration we traverse the complete array from i to (n-1) even if the array is sorted.

Here is the code in C language: Selection Sort in C

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal

Comments

Post a Comment

Popular posts from this blog

Segregate Even Odd value nodes in a linked list

Image
Given the head of a singly linked list, segregate even value nodes with odd value nodes such that all the even value nodes come before all the odd value nodes in the order of their appearance. Segregate Even and Odd value nodes Algorithm: Remember the pivot logic we used in QuickSort ? In QuickSort the pivot value was used to separate all the values which are smaller than pivot towards the left of the pivot and all the values greater than pivot value towards the right of the pivot. We will use a similar logic here. 1. Find the first even value node. 2. Bring this node to the start of the linked list. (Call it pivot) 3. Find the next even value node. 4. Insert this node after the pivot and increment pivot one node ahead. 5. Repeat this until we reach Null or None. The algorithm states to bring the first even value node to the start of the linked list and make a pointer pivot point towards it. Whenever we find an even value node, we need to link the previous node to ...
Keep reading

Tree data structure

Image
Tree Data structure Till now we have seen linear data structures such as arrays and linked lists. In these data structures, we had only one child following the previous parent. 5 is parent of 7 7 is parent of 3 3 is parent of 4 Tree are hierarchical data structures. Here each node can have multiple children. A popular implementation of Tree is a Binary tree where each node has at most 2 children (known as the left child and right child). The top most node is known as the root of the tree similar to the head node in a linked list.  The node directly above some node is called its parent. Application: Trees can are used in various applications that we see every day.  For example, the directory structure that we see in our operating systems (file explorer in Windows, finder in MacOS) is a great example of using tree where each folder is a node and each sub folder are its children, the files can be considered as leaf nodes i.e. the bottom most nodes in the ...
Keep reading

Reverse alternate k nodes in a linked list

Image
Given a pointer to the head of a Singly linked list, our objective is to reverse the linked list in alternate groups of K nodes. Reversed alternate K nodes in a linked list Algorithm: We discussed Reversing a linked list in groups of K nodes in the previous post. The logic here is also the same, the only difference is that before the recursive call we traverse K more nodes so that we can skip them. """ Perform the skip after reversing the previous k nodes """ count = 0 # traverse the k nodes to be skipped while current is not None and count < k-1: current = current.next count += 1 Code in Python: # Python program to alternately reverse a linked list in group of given size k # Node class class Node: # Constructor to initialise data and next def __init__(self, data=None): self.data = data self.next = None class SinglyLinkedList: # Constructor to initialise head def __init__(self): self...
Keep reading