Selection Sort

The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of in-place comparison sort.

Pseudocode of selection sort

1. Get the smallest element and put it in the first position
2. Get the next smallest element and put it in the 2nd position
3. ....

Sorting takes place by stepping through all the data items one-by-one while looking for either largest or smallest data item and making only one swap after finding either largest or smallest data item. Hence, this sorting algorithm is referred to as the selection sort because on each pass this algorithm selects either largest or smallest of the remaining unsorted data items and places them in the right order.

For example, consider the following array:

Now we select the first smallest element, i.e. 4 and put it in first location.

And so on with 7,10 and 18.

Finally we have a sorted array:

Implementation in c
Will come soon - comment if you need early
 
Implementation in cpp

 #include <iostream>
 
 class SelectionSort
 {
     public:
         SelectionSort();
         ~SelectionSort();
 
         void sort(int arr[], int size);
 
     private:
         void exchange(int &x, int &y);
 };
 
 //Constructor
 SelectionSort::SelectionSort() {}
 
 //Destructor
 SelectionSort::~SelectionSort() {}
 
 void SelectionSort::sort(int arr[], int size)
 {
     for(int outerLoopIdx = 0; outerLoopIdx < size - 1; ++outerLoopIdx)
     {
         int min = outerLoopIdx;
         for(int innerLoopIdx = outerLoopIdx + 1; innerLoopIdx < size; ++innerLoopIdx)
         {
             if(arr[min] > arr[innerLoopIdx])
             {
                 min = innerLoopIdx;
             }
         }
         exchange(arr[outerLoopIdx], arr[min]);
     }
 }
 
 void SelectionSort::exchange(int &x, int &y)
 {
     int t = x;
     x = y;
     y = t;
 }
 
 void print(int arr[], int size)
 {
     for(int i = 0; i < size; ++i)
         std::cout << arr[i] << " ";
 }
 
 int main()
 {
     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
     SelectionSort ss;
     ss.sort(arr, 9);
     print(arr, 9);
 }

Selection sort in java
 To come soon - comment if you need early

Selection sort in java using generics

 import org.junit.Assert;
 import org.junit.Test;
 
 class GenericSelectionSorter
 {
     public <T extends Comparable<T>> void sort(T[] elems) {
         int size = elems.length;
 
         for (int outerLoopIdx = 0; outerLoopIdx < size - 1; ++outerLoopIdx) {
             int min = outerLoopIdx;
             for (int innerLoopIdx = outerLoopIdx; innerLoopIdx < size; ++innerLoopIdx) {
                 if (elems[min].compareTo(elems[innerLoopIdx]) > 0) {
                     min = innerLoopIdx;
                 }
             }
 
             // exchange elements at outerIndexLoop and min positions
             T temp = elems[min];
             elems[min] = elems[outerLoopIdx];
             elems[outerLoopIdx] = temp;
         }
     }
 }
 
 public class SelectionSortTester
 {
     private String[] unsortedNames = new String[] {
             "Pankaj",
             "Paresh",
             "Ankit",
             "Sankalp",
             "Aditya",
             "Prem",
             "Rocket",
             "Singh",
             "Alabama",
             "Alaska",
             "Animal" };
 
     private String[] sortedNames = new String[] {
             "Aditya",
             "Alabama",
             "Alaska",
             "Animal",
             "Ankit",
             "Pankaj",
             "Paresh",
             "Prem",
             "Rocket",
             "Sankalp",
             "Singh" };
 
     @Test
     public void testStringSort() {
         GenericSelectionSorter ss = new GenericSelectionSorter();
         ss.sort(unsortedNames);
         Assert.assertArrayEquals(unsortedNames, sortedNames);
     }
 }

Thanks