Page 1 of 1

Understanding Selection Sort

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,586
  • Joined: 27-December 08

Posted 10 June 2010 - 11:10 PM

Selection Sort is a fairly basic and intuitive sorting algorithm. Basically, you swap the Nth largest element with the Nth position from the end. So the largest element is swapped with the last element in the list, the second largest with the second to last element, etc.

So let's go ahead and look some pseudo-code for Selection Sort.
selectionSort(array x){
   for i <-- x.length-1 to 0, i <-- i-1
         max <-- i
         for j <-- 0 to i-1, j <-- j+1
             if(x[j] > x[max]) 
                  max <-- j
             end if
         end for
         swap(x[max], x[i])    
   end for
}



Some things we see here are nested for loops, the first linear on the array, and the inner loop linear on the outer loop. So when we some k from 1 to n-1 for (n-k), we get an O(n^2). In addition, in this pseudo-code, we are placing the largest elements at the end for an ascending order sort. Consider how we would place the array in descending order. It would be as easy as placing the smallest elements at the end instead of the largest.

Is This A Good Question/Topic? 2
  • +

Page 1 of 1