Scribd
Upload
3 views2 pages

Selection Sort Algorithm Explained

Selection sort is a simple sorting technique that repeatedly selects the smallest element from the unsorted portion of the list and swaps it with the first unsorted element, resulting in a sorted array in ascending order. The algorithm has a time complexity of O(n^2) in both worst and average cases, while the best case occurs when the array is already sorted, resulting in O(n). A sample program in C++ demonstrates the implementation of selection sort.

Uploaded by

Chandni Patel
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views2 pages

Selection Sort Algorithm Explained

Selection sort is a simple sorting technique that repeatedly selects the smallest element from the unsorted portion of the list and swaps it with the first unsorted element, resulting in a sorted array in ascending order. The algorithm has a time complexity of O(n^2) in both worst and average cases, while the best case occurs when the array is already sorted, resulting in O(n). A sample program in C++ demonstrates the implementation of selection sort.

Uploaded by

Chandni Patel
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

SELECTION SORT Selection sort is one of simplest sorting technique in which we select smallest item in the list and

exchange it with the first [Link] the second smallest element in the list and exchange it with the second element and so [Link] all the items will be arranged in ascending [Link] otherwords selection sort performs sorting by repeatly putting the largest element in the unprocessed portion of the array to the end of the this unprocessed portion until the whole array is sorted. 1 The Algorithm: for i1 to n 1 do pos i for j i + 1 to n if A[j] < A[pos] then posj if pos = i then A[i] A[pos] Selection sort has two loops each of which execute n times. Hence the selection sort is O(n2 ). The current element is assumed to be the smallest and is compared with remaining elements. The position of the smallest element is found. If the smallest element is not the current position, then the two elements are swapped. Consider a test case with elements 45 20 40 5 15 (45 20 40 5 15 ) (5 20 40 45 15) (5 15 40 45 20) (5 15 20 45 40) (5 15 20 40 45) 2 Worst Case Worst case occurs if the elements are already sorted in the non-ascending order, because for each iteration the smallest element needs to be swapped and thus the Worst Case is O(n2 ). 3 Best Case Best case occurs if the elemsnts are already sorted in non-descending order, because current element is smallest and no element needs to be swapped and thus the Best Case is O(n).

SELECTION SORT PROGRAM BY [Link] #include<iostream.h> #include<conio.h> void main() { clrscr(); int a[10],i,j,small,pos,temp; cout<<"\n******************************* SELECTION SORT *******************************"; cout<<"\n\t Enter 10 Values :\t"; for(i=0;i<=9;i++) { cin>>a[i]; } for(i=0;i<=9;i++) { small=a[i]; pos=i; for(j=i;j<=9;j++) { if(small>a[j]) { small=a[j]; pos=j; } } temp=a[i]; a[i]=small; a[pos]=temp; } cout<<"\n\t Array after sorting is :\n\n\t"; for(i=0;i<=9;i++) { cout<<a[i]<<"\t\t"; } getch(); }

You might also like