Computer Science‎ > ‎

Arrays and Sorting: Selection Sort (C Program/Java Program source code, a tutorial and an MCQ Quiz on Sorting)








A few recommendations for Data Structures and Algorithms:
Data Structures, Algorithm Design and Analysis of Complexity


Introduction to Algorithms 3r...
List Price: Rs.525
Our Price: Rs.357
Buy from FlipKart


   Introduction to Algorithms (CLRS) 



Algorithms 4th Edition
Our Price: Rs.599
Buy from FlipKart


 Algorithms (By Robert Sedgewick) 


An Introduction to the Analys...
List Price: Rs.550
Our Price: Rs.500
Buy from FlipKart


Analysis of Algorithms (By Robert Sedgewick) 

 



Basic Sorting and Searching Algorithms for Arrays, at a glance

To go through the C program / source-code, scroll down to the end of this page

Selection Sort


The idea of the selection sort is to find the smallest element in the list and exchange it with the element in the first position. Then, find the second smallest element and exchange it with the element in the second position, and so on until the entire array is sorted.


Algorithm:


For every index from 0 to number_of_elements-1, we find the element which is appropriate for that index and we swap the element which is already there with the element which has to be there. Finding the element which is appropriate for an index is simple. We just have to find the minimum value which is there from that index till number_of_elements-1.
1. minIndex denotes the index which has the minimum value which for now assumed to be
the value at current index and we update it in a for loop.
2. For elements from minIndex+1 to the last element of the list check if some index has got
element smaller than minimum then update minindex to be that index.
3. Then swap the two elements i.e. the element at minidex in 1 and the element at the
updated minindex.
4. Follow the first three steps for every index from 0 to number_of_elements-1.


To Check out a Java Applet Visualization of Selection Sort, click on the image below :

Selection Sort Visualization

The gadget spec URL could not be found

Properties:


Best case performance – When the list is already sorted O(n2).
Worst case performance - When the list is sorted in reverse order O(n2).
Average case performance – O(n2).
It does not require any extra space for sorting, hence O(1) extra space.
It is not stable.
O(n2) time complexity makes it difficult for long lists.

Tutorial :


Selection Sort - C Program Source Code

#include<stdio.h>
/* Logic : For every index from 0 to number_of_elements-1, we find the element which is appropriate
           for that index and we swap the element which is already there with the element which has to
           be there. Finding the element which is appropriate for an index is simple. We just have to
           find the minimum value which is there from that index till number_of_elements-1.
 */

void SelectionSort(int *array,int number_of_elements)
{
        int iter,jter,minIndex,temp;
        for(iter = 0;iter<number_of_elements;iter++)
        {
                /*minIndex denotes the index which has the minimum value which for now assumed to be
                 the vlaue at current index and we update it in the for loop given below
                 */

                minIndex = iter;
                for(jter = iter+1; jter<number_of_elements;jter++)
                {
                        if(array[jter] < array[minIndex])
                        {
                                /* If some index has got element smaller than minimum then update
                                   minindex  to be that index*/

                                minIndex = jter;
                        }
                }
                temp = array[iter];
                array[iter] = array[minIndex];
                array[minIndex] = temp;
        }
}
int main()
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements];
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        SelectionSort(array,number_of_elements);
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;

}

Selection Sort - Java Program Source Code


Post to LiveJournal
/* Logic : For every index from 0 to number_of_elements-1, we find the element which is appropriate 
           for that index and we swap the element which is already there with the element which has to 
           be there. Finding the element which is appropriate for an index is simple. We just have to 
           find the minimum value which is there from that index till number_of_elements-1.
 */
import java.io.*;
 public class Selection
    {
 
int main()throws IOException
{
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the number of elements");
        int number_of_elements;
        number_of_elements=Integer.parseInt(in.readLine());
        int array[]=new int[number_of_elements]; 
        int iter;
        System.out.println("enter the values one by one");
        for(iter = 0;iter < number_of_elements;iter++)
        {
                array[iter]=Integer.parseInt(in.readLine());
        }
        /* Calling this functions sorts the array */
        SelectionSort(array,number_of_elements); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                System.out.print(array[iter]+ "\t");
        }
        System.out.println("\n");
        return 0;

}
void SelectionSort(int array[],int number_of_elements)
{
        int iter,jter,minIndex,temp;
        for(iter = 0;iter<number_of_elements;iter++)
        {
                /*minIndex denotes the index which has the minimum value which for now assumed to be 
                 the vlaue at current index and we update it in the for loop given below
                 */
                minIndex = iter;
                for(jter = iter+1; jter<number_of_elements;jter++)
                {
                        if(array[jter] < array[minIndex])
                        {
                                /* If some index has got element smaller than minimum then update
                                   minindex  to be that index*/
                                minIndex = jter;
                        }
                }
                temp = array[iter];
                array[iter] = array[minIndex];
                array[minIndex] = temp;
        }
}

}


MCQ Quiz: The Basics of Sorting Algorithms- Quadratic Sorts: Check how much you know about Quadratic Time Sorting Algorithms

Your score will be e-mailed to the address filled up by you.

MCQ Quiz #1: Quadratic Time Sorting Algorithms

Related Tutorials :

Bubble Sort    

One of the most elementary sorting algorithms to implement - and also very inefficient. Runs in quadratic time. A good starting point to understand sorting in general, before moving on to more advanced techniques and algorithms. A general idea of how the algorithm works and a the code for a C program.

Insertion Sort

Another quadratic time sorting algorithm - an example of dynamic programming. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs insertion sort. 

Selection Sort

Another quadratic time sorting algorithm - an example of a greedy algorithm. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs selection sort. 

 Shell Sort

An inefficient but interesting algorithm, the complexity of which is not exactly known.

Merge Sort 

An example of a Divide and Conquer algorithm. Works in O(n log n) time. The memory complexity for this is a bit of a disadvantage.

Quick Sort

In the average case, this works in O(n log n) time. No additional memory overhead - so this is better than merge sort in this regard. A partition element is selected, the array is restructured such that all elements greater or less than the partition are on opposite sides of the partition. These two parts of the array are then sorted recursively.

Heap Sort

 Efficient sorting algorithm which runs in O(n log n) time. Uses the Heap data structure. 

Binary Search Algorithm

 Commonly used algorithm used to find the position of an element in a sorted array. Runs in O(log n) time. 





Testing Zone For Programmers- 

Try out our online Multiple-Choice-Question tests in Programming and Computer Science!



Photo-credits: www.istockphoto.com

 Quizzes on Basic Object Oriented Programming with C++   Quizzes on Java Programming
 Quizzes on C Programming- Arrays, Strings and Pointers
  1. C Programming MCQ Quiz #1:  Strings- 1
  2. C Programming MCQ Quiz #2: Strings (2)
  3. C Programming MCQ Quiz #3: Strings (3)
  4. C Programming MCQ Quiz #4: Arrays(1)
  5. C Programming MCQ Quiz #5: Arrays (2)
  6. C Programming MCQ Quiz #6: Arrays (3)
  7. C Programming MCQ Quiz #7: Pointers (1)
  8. C Programming MCQ Quiz #8: Pointers (2)
 Quizzes on Data Structures, Algorithms and Complexity
  1. MCQ Quiz #1: The Basics of Sorting Algorithms- Quadratic Sorts
  2. MCQ Quiz #2: Efficient Sorting Algorithms- Quick sort, Merge Sort, Heap Sort
  3. MCQ Quiz #3- The Radix Sort
  4. MCQ Quiz #4: Divide and Conquer Techniques- Binary Search, Quicksort, Merge sort, Complexities
  5. MCQ Quiz #5- Dynamic Programming
  6. MCQ Quiz #6- Complexity of Algorithms
  7. MCQ Quiz #7- Application of Master's Theorem
  8. MCQ Quiz #8: Binary Search Trees
  9. MCQ Quiz #9: B-Trees
  10. 10 MCQ Quiz #9: AVL-Trees
  11. 11 MCQ Quiz #10: Representing Graphs as Data Structures
  12. 12 MCQ Quiz #11: Spanning Trees
  13. 13 MCQ Quiz #12: Algorithms - Graphs: Spanning Trees - Kruskal and Prim Algorithms
  14. 14 MCQ Quiz #13: Algorithms - Graphs: Depth and Breadth First Search


Some Important Data Structures and Algorithms, at a glance:

Arrays : Popular Sorting and Searching Algorithms

 

  

Bubble Sort  

Insertion Sort 

Selection Sort Shell Sort

Merge Sort  

Quick Sort 

 
Heap Sort
 
Binary Search Algorithm

Basic Data Structures  and Operations on them


  

Stacks 

Queues  

 
 Single Linked List 

Double Linked List

Circular Linked List 






The gadget spec URL could not be found


 






Tutorials on Sorting- at a glance

 Bubble Sort One of the most elementary sorting algorithms to implement - and also very inefficient. Runs in quadratic time. A good starting point to understand sorting in general, before moving on to more advanced techniques and algorithms. A general idea of how the algorithm works and a the code for a C program.

Insertion Sort - Another quadratic time sorting algorithm - an example of dynamic programming. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs insertion sort.

Selection Sort - Another quadratic time sorting algorithm - an example of a greedy algorithm. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs selection sort.

Shell Sort- An inefficient but interesting algorithm, the complexity of which is not exactly known.

Merge Sort An example of a Divide and Conquer algorithm. Works in O(n log n) time. The memory complexity for this is a bit of a disadvantage.

Quick Sort In the average case, this works in O(n log n) time. No additional memory overhead - so this is better than merge sort in this regard. A partition element is selected, the array is restructured such that all elements greater or less than the partition are on opposite sides of the partition. These two parts of the array are then sorted recursively.

Heap Sort- Efficient sorting algorithm which runs in O(n log n) time. Uses the Heap data structure.

Binary Search Algorithm- Commonly used algorithm used to find the position of an element in a sorted array. Runs in O(log n) time.


ą
Prashant Bhattacharji,
Oct 7, 2012, 9:54 AM