Selection sort

Selection sort is basically a selection of an element position from the start with the other rest of the elements. Elements are compared and exchanged depending on the condition and then selection position is shifted to the next position till it reaches to the end.

Selection sort and selections

Here are the selection positions of these elements. Comparion takes place with selected position to the rest of the next positions.

Selection sort Big(o)

Selection sort of N elements can take (N - 1) steps and (N - 1) iterations in each steps. Thus resultant is (N-1)*(N-1). This sorting algorithm is not however the best in performance when count of the elements are large. Time complexities of Selection sort is Big(o) = N^2. This sorting is well suited for small number of elements and it is easy the implement in C or any other programming languages.

Selection sort source code

Here is a C source code of Selection sorting with 5 integer elements. This code sorts the elements in ascending order.

#include <stdio.h>
void swap_node(int *x, int *y)
{
  int tmp;
  tmp = *x;
  *= *y;
  *= tmp;
}
10  void selection_sort(int elements[], int count)
11  {
12    int select, index;
13    printf("Selection sort started-\n");
14    for (select = 0; select < count - 1; select++)
15    {
16      printf("==== Selection %d ====\n", select+1);
17      print_array(elements, 5);
18      for(index = select + 1; index < count; index++)
19      {
20        printf("#%d:%d ", select+1, index+1);
21        if (elements[select] > elements[index])
22        {
23          printf(" swap %d > %d\n",
24                 elements[select],
25                 elements[index]);
26          swap_node(&elements[select],
27                     &elements[index]);
28        } else
29        {
30          printf("no swap %d <= %d\n",
31                 elements[select],
32                 elements[index]);
33        }
34        print_array(elements, 5);
35      }
36    }
37    printf("Selection sort ended\n");
38    
39  }
40  void print_array(int array[], int count)
41  {
42    int i;
43    printf("[");
44    for(= 0; i < count; i++)
45    printf("%d, ", array[i]);
46    printf("\b\b]\n");
47  }
48  int main(int argc, char *argv[])
49  {
50    int array[5] = { 4, 9, 5, 1, 0 };
51    printf("Unsorted elements\n");
52    print_array(array, 5);
53    selection_sort(array, 5);
54    printf("Selection sorted elements\n");
55    print_array(array, 5);
56  }
57 
58 
59 

Steps and Iterations (diagrams)

selection sort selection of 1st item iteration stages

selection sort selection of 2nd item iteration stages

selection sort selection of 3rd item iteration stages

selection sort selection of 4th item iteration stages

Output

Unsorted elements                                                                                                                       
[4, 9, 5, 1, 0]                                                                                                                         
Selection sort started-                                                                                                                 
==== Selection 1 ====                                                                                                                   
[4, 9, 5, 1, 0]                                                                                                                         
#1:2 no swap  4 <= 9                                                                                                                    
[4, 9, 5, 1, 0]                                                                                                                         
#1:3 no swap  4 <= 5                                                                                                                    
[4, 9, 5, 1, 0]                                                                                                                         
#1:4    swap  4 >  1                                                                                                                    
[1, 9, 5, 4, 0]                                                                                                                         
#1:5    swap  1 >  0                                                                                                                    
[0, 9, 5, 4, 1]                                                                                                                         
==== Selection 2 ====                                                                                                                   
[0, 9, 5, 4, 1]                                                                                                                         
#2:3    swap  9 >  5                                                                                                                    
[0, 5, 9, 4, 1]                                                                                                                         
#2:4    swap  5 >  4                                                                                                                    
[0, 4, 9, 5, 1]                                                                                                                         
#2:5    swap  4 >  1                                                                                                                    
[0, 1, 9, 5, 4]                                                                                                                         
==== Selection 3 ====                                                                                                                   
[0, 1, 9, 5, 4]                                                                                                                         
#3:4    swap  9 >  5                                                                                                                    
[0, 1, 5, 9, 4]                                                                                                                         
#3:5    swap  5 >  4                                                                                                                    
[0, 1, 4, 9, 5]                                                                                                                         
==== Selection 4 ====                                                                                                                   
[0, 1, 4, 9, 5]                                                                                                                         
#4:5    swap  9 >  5                                                                                                                    
[0, 1, 4, 5, 9]                                                                                                                         
Selection sort ended                                                                                                                    
Selection sorted elements                                                                                                               
[0, 1, 4, 5, 9]

You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.

 Vote 0

Similar topics related to this section

Binary Search, Hash Table, Sorting, Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Heap Sort, Merge sort,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan