Amazon Prime




 
Tagged
  • Algorithm
  • Sorting
  • Selection Sort
  •  

    Selection Sort Algorithm

    Introduction

    Selection Sort Algorithm works by finding the minimum element of the array and placing the min element at its correct position. In the selection sort, the first element is selected as minimum and visits other elements of the array, If any element is found lesser than the current minimum, the minimum value gets updated. This process gets repeated for other elements of the array.

    Algorithm

    1Step 0 : Initialize n to length of the array
    2
    3Step 1 : Initialize j to 0 and compare a[j] with a[j+1]
    4 (compare adjacent elements starting from 0th index)
    5
    6Step 2 : if a[j] > a[j+1] swap a[j] and a[j+1]
    7
    8Step 3 : repeat steps 1 and 2 until j reached end of the array
    9 (by end of this one element will be placed at its correct order)
    10
    11Step 4 : continue from Step 1 n-1 times
    12 (so that all elements will be in proper order)

    Example Explanation

    1Input array : a = {5, 3, 13, 2, 11, 4, 7}

    Iteration 1 : (i = 0)

    Step 1 : Initialize i = 0

    Step 2: Initialize min to i and j = i+1 So min = 0 and j = 1.

    Step 3: Compare a[min] with a[j] & change min index if a[min] > a[j]

    Step 4: Increment j & repeat from Step 3 until j reaches end of the array.

    Selection Sort - Iteration1

    Iteration 2 : (i = 1)

    Selection Sort - Iteration2

    Iteration 3 : (i = 2)

    Selection Sort - Iteration3

    Iteration 4 : (i = 3)

    Selection Sort - Iteration4

    Iteration 5 : (i = 4)

    Selection Sort - Iteration5

    Iteration 6 : (i = 5)

    Selection Sort - Iteration6

    Implementation

    1public class SelectionSort {
    2
    3 // Method to sort a given array
    4 public void sort(int[] array) {
    5 int n = array.length;
    6 for(int i=0;i<n-1;i++){
    7 // Let us assume a[i] is the smallest element of unsorted array
    8 // initialize min index with i
    9 int min = i;
    10
    11 for(int j=i+1;j<n;j++){
    12 // compare a[min] with a[j] and change min index accordingly
    13 if(array[min] > array[j]){
    14 // as array[min] is greater that current element, update min index with j
    15 min = j ;
    16 }
    17 }
    18 // at the end of the iteration we know what is min of the unsorted array
    19 // swap elements at min and i
    20 // it means element at i is part of sorted array
    21 // continue same process for remaining un sorted array
    22 swap(array, i, min);
    23 // if you want to see the array at the end of every iteration, uncomment below lines
    24 // System.out.println("Iteration "+i);
    25 // print(array);
    26 }
    27 }
    28
    29 // method swap values at index i and j of array
    30 private void swap(int[] array, int i, int j){
    31 int temp = array[i];
    32 array[i] = array[j];
    33 array[j] = temp;
    34 }
    35
    36 // Helper method to print an array
    37 private void print(int[] array) {
    38 for(int i=0; i<array.length; i++) {
    39 System.out.print(array[i]+"\t");
    40 }
    41 System.out.println();
    42 }
    43
    44 // Driver Code
    45 public static void main(String[] args){
    46 int[] a = {5, 3, 13, 2, 11, 4, 7};
    47 SelectionSort obj = new SelectionSort();
    48 obj.print(a);
    49 obj.sort(a);
    50 obj.print(a);
    51 }
    52}

    Complexity Analysis

    • Time Complexity : O(n^2).
    • Space Complexity : O(1) .
     

  • Algorithm
  • Sorting
  • Selection Sort
  •  
    ...