Selection Sort in C

What is Selection Sort in C

In this Sorting technique the list is divided into two parts. first one is left end and second one is right end .  The selection Sort is very  simple sorting algorithm.

Sorting
Time Complexity (Best)Ω(n2)
Time Complexity (Avg)Θ(n2)
Time Complexity (Worst)O(n2)
Space ComplexityO(1)

Steps for Selection Sort in C

There are following Step of selection sort algorithm.

  • Step 1-Select the smallest value in the list.
  • Step 2-Swap smallest value with the first element of the list.
  • Step 3-Again select the smallest value in the list (exclude first value).
  • Step 4- Repeat above step for (n-1) elements untill the list is sorted.

Implementation of Selection Sort

  • We have been given a unsorted array. which we’ll  make  a sorted array using selection sort. first of all  find the smallest value in the array and then swap smallest value with the starting value.
  • According to the below image,  8 is smallest value in this array so 8 is swapped with the first element that is 72.
  • Similarly, in the next iteration we’ll  find the next smallest value, excluding the starting value so in this array  10 is second smallest value, which is to be swapped with 50.
  • These iteration will continue until we have the largest element to the right most end, along with all the other elements in their correct position.
  • And then we can finally say that the given array is converted in sorted array.
Selection Sort in C with example– 1

Code of Selection sort in C

Output

Before sorting: 
72 50 10 44 8 20

After sorting:
8 10 20 44 50 72

Performance

The Selection Sort best and worst case scenarios both follow the time complexity format O(n^2) as the sorting operation involves two nested loops. The size of the array again affects the performance.[1]

Strengths

  • The arrangement of elements does not affect its performance.
  • Uses fewer operations, so where data movement is costly it is more economical

Weaknesses

  • The comparisons within unsorted arrays requires O(n^2) which is ideal where n is small
Insertion Sort Algorithm in C meme
Selection sort in C meme

Time Complexity
For Selection Sort

Best

Ω(n2)

Average

Θ(n2)

Worst

O(n2)

Space Complexity

O(1)

Quiz time

Quiz Time

Question 1. Array = [10, 11, 12, 13, 14, 15], the number of iterations bubble sort(without flag variable) and Selection sort would take –

  1. 5 and 5
  2. 5 and 4
  3. 4 and 4
  4. 6 and 6

(Cognizant – Mettl Test)

In bubble sort they are talking about passes, even though the question says iterations.

A bubble sort with n items takes (n-1) passes.

In selection sort also for n items its (n-1) passes.

Thus, 4 and 4 is answer

Option C

Question 2. Array = [10, 11, 12, 13, 14, 15], the number of iterations bubble sort(with flag variable) and Selection sort would take –

  1. 5 and 5
  2. 5 and 4
  3. 4 and 4
  4. 1 and 4

(Cognizant – Mettl Test)

In bubble sort they are talking about passes, even though the question says iterations.

A bubble sort with n items takes (n-1) passes. But, since the whole array is sorted, bubble sort will have just one pass to realize the array is sorted and abandon other passes

In selection sort also for n items its (n-1) passes, even though the array is sorted

Thus, 1 and 4 is answer

Option C

Question 3. What is the best case complexity of selection sort?

  1. O(nlogn)
  2. O(logn)
  3. O(n)
  4. O(n2)

(Wipro – AMCAT Test)

In selection sort all cases the time complexity is : O(N^2)

Explanation: The best, average and worst case complexities of selection sort is O(n2).
(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2.

Question 4. Array[] = {72, 50, 10, 44, 8, 20} how would the array look like in iteration 4

  1. 8, 10, 44, 20, 72, 50
  2. 8, 10, 20, 44, 72, 50
  3. 8, 10, 20, 44, 50, 72
  4. None

(Wipro – AMCAT Test)

Answer : B

The array will look like – 8, 10, 20, 44, 72, 50

Check image

Selection Sort in C with example– 1

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting

Selection Sort in Java

Selection Sort in Java

Selection Sort is a technique where a array is sequentially sorted by placing the smallest or the largest element from the array one after the other in multiple iterations. The time complexity of selection sort is more  then the time complexity of insertion sort. Algorithm is not suitable for large data sets.

sort
Time Complexity (Best)Ω(n2)
Time Complexity (Avg)Θ(n2)
Time Complexity (Worst)O(n2)
Space ComplexityO(1)

Implementation

At any point during the selection sort implementation, we will have the array divided into a sorted array part on the left and an unsorted array part on the right.

  • We find the smallest item in the unsorted side of the array
  • We replace that with the first item in the unsorted array part
  • This way we will have one more item added to the sorted part of the array on left
  • One lesser item in the unsorted part of the array on the right
Selection Sort in Java
Selection Sort in Java Example

Algorithm for selection sort in JAVA

  • sort(Arr[]):
  • l= Arr.length
  • FOR i from 1 to l-1:
  • min = i
  • FOR j = i+1 to l
  • if Arr[j]<Arr[min]
  • min = j
    swap(Arr[j], Arr[min])
  • END of FOR
  • END of FOR

Program for selection sort in JAVA

Run
// Java Program for Insertion Sort
// Time Complexity : O(N^2)
// Space Complexity : O(1)
// Best Case, Worst Case, Avg Case : O(n^2)
class Main
{
    // Main method, responsible for the execution of the code
    public static void main(String args[])
    {
        int arr[] = {72, 50, 10, 44, 20};

        selectionSort(arr);

        System.out.println("Sorted array");

        printArray(arr);
    }

    static void selectionSort(int a[])
    {
        int len = a.length;      
        
        // One by one move boundary of unsorted sub-array
        for (int i = 0; i < len-1; i++)
        {
            // Find the minimum element in unsorted array
            int min = i;
            for (int j = i+1; j < len; j++)
                if (a[j] < a[min])
                    min = j;

            // Swap the found minimum element with the
            // first element in unsorted part of the array
            int temp = a[min];
            a[min] = a[i];
            a[i] = temp;
        }
    }

    // Prints the sorted array
    static void printArray(int a[])
    {
        int len = a.length;
        for (int i=0; i<len; ++i)
            System.out.print(a[i] + " ");

        System.out.println();
    }
}

Highlights

  • Selection sort gives a time complexity of O(n2) in all cases regardless of arrangement of data
  • It could be useful in cases when swapping operation are very costly to do this would help as number of swaps in selection sort are :  size – 1
Selection sort in java meme

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting
WordPress › Error

There has been a critical error on this website.

Learn more about troubleshooting WordPress.