Selection sort

Selection sort

In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.
The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Algorithm Implementation : 

First mark the ith element as the imin and then use inner loop j from i+1 to array.length to find the minimum element is there is one less that array[imin].If found one assign ithe index to imin as imin=j.Now come out of inner loop and swap the element in a[imin] with the value in a[i].
So in the selection sort with each pass of the outer element we are making the first ith element as sorted .So at the end of ith iteration of the outer loop the first ith element are in sorted order.  

Java Implementation

int a[]={9,8,7,6,5,4,3,2,1,0};

              int imin = 0;

              for(int i=0;i<a.length;i++){

                     imin = i;
                     //start inner loop from i+1 to find imin

                     for(int j=i+1;j<a.length;j++){
                           //find the imin

                           if(a[j]<a[imin] && imin!= j)
                                  //store the min index

                                  imin=j;
                           //close the innerloop

                           }
                           //swap the elements with ith index using outer loop
                           int temp = a[imin];

                                  a[imin]=a[i];

                                  a[i] = temp;

                          

                     }

              }

Variants

Heapsort greatly improves the basic algorithm by using an implicit heap data structure to speed up finding and removing the lowest datum. If implemented correctly, the heap will allow finding the next lowest element in Θ(log n) time instead of Θ(n) for the inner loop in normal selection sort, reducing the total running time to Θ(n log n).
A bidirectional variant of selection sort, called cocktail sort, is an algorithm which finds both the minimum and maximum values in the list in every pass. This reduces the number of scans of the list by a factor of 2, eliminating some loop overhead but not actually decreasing the number of comparisons or swaps. Note, however, that cocktail sort more often refers to a bidirectional variant of bubble sort.

Cocktail sort

Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuffle sort,^[1] or shuttle sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort.

Pseudocode

procedure cocktailSort( A : list of sortable items ) defined as:

  do

    swapped := false

    for each i in 0 to length( A ) - 2 do:

      if A[ i ] > A[ i + 1 ] then // test whether the two elements are in the wrong order

        swap( A[ i ], A[ i + 1 ] ) // let the two elements change places

        swapped := true

      end if

    end for

    if swapped = false then

      // we can exit the outer loop here if no swaps occurred.

      break do-while loop

    end if

    swapped := false

    for each i in length( A ) - 2 to 0 do:

      if A[ i ] > A[ i + 1 ] then

        swap( A[ i ], A[ i + 1 ] )

        swapped := true

      end if

    end for

  while swapped // if no elements have been swapped, then the list is sorted

end procedure

Java Implementation

                              int a[]={33,98,74,13,55,20,77,45,64,83};

              boolean swapped = false;

              do {

                     for(int i=0;i<=a.length-2;i++){

                           if(a[i]>a[i+1]){

                                  int temp = a[i];

                                  a[i]=a[i+1];

                                  a[i+1]=temp;

                                  swapped =true;

                           }

                           if(swapped = false){

                                  break;

                           }

                     }

                     for(int i= a.length-2;i>=0;i--){

                           if(a[i]>a[i+1]){

                                  int temp = a[i];

                                  a[i]=a[i+1];

                                  a[i+1]=temp;

                                  swapped =true;

                     }

                          

                     }

                    

              }

              while(swapped);

              System.out.println("Sorted array is ");

              for(int i=0;i<a.length;i++)

                     System.out.print(a[i]+" ");