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 pageSelection SortThe 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. 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> 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 AlgorithmsYour score will be e-mailed to the address filled up by you. Related Tutorials :
Testing Zone For Programmers-Try out our online Multiple-Choice-Question tests in Programming and Computer Science!Photo-credits: www.istockphoto.com |
Computer Science >