{"id":25046,"date":"2017-10-15T14:08:54","date_gmt":"2017-10-15T08:38:54","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25046"},"modified":"2017-10-15T14:08:54","modified_gmt":"2017-10-15T08:38:54","slug":"selection-sort","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/selection-sort\/","title":{"rendered":"Selection Sort"},"content":{"rendered":"

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) <\/span>from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.<\/p>\n

1) The subarray which is already sorted.
\n2) Remaining subarray which is unsorted.<\/p>\n

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.<\/p>\n

Following example explains the above steps:<\/p>\n

arr[] = 64 25 12 22 11<\/p>\n

\/\/ Find the minimum element in arr[0…4]\n

\/\/ and place it at beginning 11 <\/strong>25 12 22 64<\/p>\n

\/\/ Find the minimum element in arr[1…4]\n

\/\/ and place it at beginning of arr[1…4] 11 12 <\/strong>25 22 64<\/p>\n

\/\/ Find the minimum element in arr[2…4]\n

\/\/ and place it at beginning of arr[2…4] 11 12 22 <\/strong>25 64<\/p>\n

\/\/ Find the minimum element in arr[3…4]\n

\/\/ and place it at beginning of arr[3…4] 11 12 22 25 <\/strong>64<\/p>\n

C and C++<\/p>\n

c and c++<\/span> <\/div> 
\/\/ C program for implementation of selection sort#include <stdio.h> void swap(int *xp, int *yp){    int temp = *xp;    *xp = *yp;    *yp = temp;} void selectionSort(int arr[], int n){    int i, j, min_idx;     \/\/ One by one move boundary of unsorted subarray    for (i = 0; i < n-1; i++)    {        \/\/ Find the minimum element in unsorted array        min_idx = i;        for (j = i+1; j < n; j++)          if (arr[j] < arr[min_idx])            min_idx = j;         \/\/ Swap the found minimum element with the first element        swap(&arr[min_idx], &arr[i]);    }} \/* Function to print an array *\/void printArray(int arr[], int size){    int i;    for (i=0; i < size; i++)        printf("%d ", arr[i]);    printf("\\n");} \/\/ Driver program to test above functionsint main(){    int arr[] = {64, 25, 12, 22, 11};    int n = sizeof(arr)\/sizeof(arr[0]);    selectionSort(arr, n);    printf("Sorted array: \\n");    printArray(arr, n);    return 0;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Python<\/p>\n
 
 python<\/span> <\/div> 
# Python program for implementation of Selection# Sortimport sysA = [64, 25, 12, 22, 11] # Traverse through all array elementsfor i in range(len(A)):         # Find the minimum element in remaining     # unsorted array    min_idx = i    for j in range(i+1, len(A)):        if A[min_idx] > A[j]:            min_idx = j                 # Swap the found minimum element with     # the first element            A[i], A[min_idx] = A[min_idx], A[i] # Driver code to test aboveprint ("Sorted array")for i in range(len(A)):    print("%d" %A[i]), <\/code><\/pre> <\/div>\n
Java<\/p>\n
 
 java<\/span> <\/div> 
\/\/ Java program for implementation of Selection Sortclass SelectionSort{    void sort(int arr[])    {        int n = arr.length;         \/\/ One by one move boundary of unsorted subarray        for (int i = 0; i < n-1; i++)        {            \/\/ Find the minimum element in unsorted array            int min_idx = i;            for (int j = i+1; j < n; j++)                if (arr[j] < arr[min_idx])                    min_idx = j;             \/\/ Swap the found minimum element with the first            \/\/ element            int temp = arr[min_idx];            arr[min_idx] = arr[i];            arr[i] = temp;        }    }     \/\/ Prints the array    void printArray(int arr[])    {        int n = arr.length;        for (int i=0; i<n; ++i)            System.out.print(arr[i]+" ");        System.out.println();    }     \/\/ Driver code to test above    public static void main(String args[])    {        SelectionSort ob = new SelectionSort();        int arr[] = {64,25,12,22,11};        ob.sort(arr);        System.out.println("Sorted array");        ob.printArray(arr);    }}<\/code><\/pre> <\/div>\n
 <\/p>\n
Output:<\/p>\n
Sorted array: 11 12 22 25 64<\/p>\n
Time Complexity:<\/strong> O(n2<\/sup>) as there are two nested loops.<\/p>\n
Auxiliary Space:<\/strong> O(1)<\/p>\n
The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.<\/p>\n[ad type=”banner”]\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Selection Sort – searching and sorting algorithm – The selection sort algorithm sorts an array by repeatedly finding the minimum element .<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,71670,83471],"tags":[70962,70963,70978,70975,70972,70260,70966,70979,70976,70969,70968,70977,70971,70974,70964,70539,70961,70973,70548,70960,70965,70970,70541,70967,70257],"class_list":["post-25046","post","type-post","status-publish","format-standard","hentry","category-coding","category-searching-and-sorting","category-selection-sort","tag-algorithm-for-selection-sort","tag-algorithm-of-selection-sort","tag-bubble-sort-c","tag-bubble-sort-example","tag-c-program-for-selection-sort","tag-complexity-of-selection-sort","tag-insert-sort","tag-insertion-sort-c","tag-insertion-sort-example","tag-java-sorting-algorithms","tag-program-for-selection-sort","tag-quicksort-java","tag-selection-sort-algorithm-in-c","tag-selection-sort-c-program","tag-selection-sort-code","tag-selection-sort-complexity","tag-selection-sort-example","tag-selection-sort-in-c-program","tag-selection-sort-in-data-structure","tag-selection-sort-java","tag-selection-sort-program","tag-selection-sort-program-in-c","tag-selection-sort-time-complexity","tag-sorting-algorithms-java","tag-time-complexity-of-selection-sort"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25046","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25046"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25046\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25046"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25046"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25046"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}