Sunday, 25 March 2018

Selection sort algorithm in data structures

Selection sort algorithm in data structures


Selection sort


Selection sort is an in-place sorting algorithm with the worst case time complexity of O(n2). It works as follows;
Let us consider an array A of size n stored in memory.

  • The selection sort algorithm first selects the smallest element in the array A and place it at array index 0; [the index position 0 is sorted now]
  • Then it selects the next smallest element in the array A excluding index 0 (considered sorted) and place it at array index 1. [the index positions 0 and 1 are sorted now]
  • Then it selects the next smallest element in the array A excluding indexes 0, 1 (considered sorted) and place it at array index 2. [the index positions 0,1, 2  are sorted now]
  • The algorithm continues this procedure until it places the biggest element in the last position of the array.

Algorithm/Pseudo-code:

for (i = 1, i n 1; i + +)
{
low_index = i; low_key = A[i];
for (j = i + 1; j n; j + +)
if (A[j] < low_key)
{
low_key = A[j];
low_index = j
}
swap (A[i], A[low_index])
}


Example:
 
**********

 







No comments:

Post a comment

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents