AlphaCodingSkills

Selection Sort


Advertisements

Previous Page Next Page

Selection sort is based on the idea of finding smallest or largest element in unsorted array and placing it at the correct position in the sorted array. This will result into increasing the length of the sorted array by one and decreasing the length of unsorted array by one after each iteration.

Example:

To understand the selection sort, lets consider an unsorted array $$[1, 10, 23, -2]$$ and discuss each step taken to sort the array in ascending order. In every pass, smallest element is found in the unsorted array and swapped with first element of unsorted array.

First Pass: The whole array is unsorted array and $$(-2)$$ is the smallest number in the array. After finding $$(-2)$$ as smallest number, it is swapped with first element of the array.

Second Pass: In this example, the left hand side array is sorted array and length of this array increase by one after each iteration. After first pass length of the sorted array is one. Rest of the array is unsorted array. $$(1)$$ is the smallest number in the unsorted array which is swapped with first element of the unsorted array. After this swap, length of the sorted array and unsorted array will be two.

Third Pass: $$(10)$$ is the smallest number in the unsorted array and swapped with the first element of the unsorted array.

Fourth Pass: $$(23)$$ is the only number in the unsorted array and found to be at the correct position.

Selection Sort

Implementation of Selection Sort



# function for selection sort
def selectionsort(MyList):
  for i in range(len(MyList)):
    min_idx = i 
    for j in range(i+1, len(MyList)):
      if(MyList[j] < MyList[min_idx]):
        min_idx = j
    MyList[i], MyList[min_idx] = MyList[min_idx], MyList[i]

# function to print list
def PrintList(MyList):
  for i in MyList:
    print(i, end=" ")
  print("\n")
  
# test selection sort code                 
MyList = [1, 10, 23, 50, 4, 9, -4]
print("Original List")
PrintList(MyList)

selectionsort(MyList)
print("Sorted List")
PrintList(MyList)

Output

Original List
1 10 23 50 4 9 -4 

Sorted List
-4 1 4 9 10 23 50 



public class MyClass {
  // function for selection sort
  static void selectionsort(int Array[]) {
  int n = Array.length;
  int temp;
  for(int i=0; i<n; i++)
  {
    int min_idx = i;
    for(int j=i+1; j<n; j++)
    {
      if(Array[j] < Array[min_idx])
      {min_idx = j;}
    }
    temp = Array[min_idx];
    Array[min_idx] = Array[i];
    Array[i] = temp;
  }
  }

  // function to print array
  static void PrintArray(int Array[]) 
    { 
        int n = Array.length; 
        for (int i=0; i<n; i++) 
        {  
          System.out.print(Array[i] + " "); 
        }
        System.out.println(); 
    } 

  //test selection sort code
  public static void main(String[] args) {
    int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
    System.out.println("Original Array");
    PrintArray(MyArray);

    selectionsort(MyArray);
    System.out.println("\nSorted Array");
    PrintArray(MyArray);  
  }
}

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50 



#include <iostream>
using namespace std;

  // function for selection sort
  static void selectionsort(int Array[], int n) 
  {
    int temp;
    for(int i=0; i<n; i++)
    {
      int min_idx = i;
      for(int j=i+1; j<n; j++)
      {
        if(Array[j] < Array[min_idx])
        {min_idx = j;}
      }
      temp = Array[min_idx];
      Array[min_idx] = Array[i];
      Array[i] = temp;
    }
  }

  // function to print array
  static void PrintArray(int Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
    {  
      cout<<Array[i]<<" "; 
    }
    cout<<"\n"; 
  } 

 // test selection sort code
 int main (){
    int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    cout<<"Original Array\n";
    PrintArray(MyArray, n);

    selectionsort(MyArray, n);
    cout<<"\nSorted Array\n";
    PrintArray(MyArray, n);
    return 0;
 }

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50



#include <stdio.h>

  // function for selection sort
  static void selectionsort(int Array[], int n) 
  {
    int temp;
    for(int i=0; i<n; i++)
    {
      int min_idx = i;
      for(int j=i+1; j<n; j++)
      {
        if(Array[j] < Array[min_idx])
        {min_idx = j;}
      }
      temp = Array[min_idx];
      Array[min_idx] = Array[i];
      Array[i] = temp;
    }
  }

  // function to print array
  static void PrintArray(int Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
    {  
      printf("%i ",Array[i]); 
    }
    printf("\n"); 
  } 

 // test selection sort code
 int main (){
    int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    printf("Original Array\n");
    PrintArray(MyArray, n);

    selectionsort(MyArray, n);
    printf("\nSorted Array\n");
    PrintArray(MyArray, n);
    return 0;
 }

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50 



using System;

namespace MyApplication { 
   class MyProgram {
       // function for selection sort
     static void selectionsort(int[] Array) 
     {
      int n = Array.Length;
      int temp;
      for(int i=0; i<n; i++)
      {
        int min_idx = i;
        for(int j=i+1; j<n; j++)
        {
          if(Array[j] < Array[min_idx])
          {min_idx = j;}
        }
        temp = Array[min_idx];
        Array[min_idx] = Array[i];
        Array[i] = temp;
      }
     }

     // function to print array
     static void PrintArray(int[] Array) 
     { 
        int n = Array.Length; 
        for (int i=0; i<n; i++) 
        {  
          Console.Write(Array[i] + " "); 
        }
        Console.Write("\n"); 
     } 
 
    // test selection sort code
    static void Main(string[] args) {
     int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
     Console.Write("Original Array\n");
     PrintArray(MyArray);

     selectionsort(MyArray);
     Console.Write("\nSorted Array\n");
     PrintArray(MyArray);  
    }
  }
}

Output

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50

Time Complexity:

The time complexity of selection sort is $$\mathcal{O}(N^2)$$ in all cases even if the whole array is sorted because the entire array need to be iterated for every element and it contains two nested loops.


Previous Page Next Page