Shellsort

Shellsort

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort).^[2] The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959.^[3][4] The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.

ShellSort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shellSort is to allow exchange of far items. In shellSort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element is sorted.

Pseudocode

# Sort an array a[0...n-1].

gaps = [701, 301, 132, 57, 23, 10, 4, 1]

# Start with the largest gap and work down to a gap of 1

foreach (gap in gaps)

{

    # Do a gapped insertion sort for this gap size.

    # The first gap elements a[0..gap-1] are already in gapped order

    # keep adding one more element until the entire array is gap sorted

    for (i = gap; i < n; i += 1)

    {

        # add a[i] to the elements that have been gap sorted

        # save a[i] in temp and make a hole at position i

        temp = a[i]

        # shift earlier gap-sorted elements up until the correct location for a[i] is found

        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)

        {

            a[j] = a[j - gap]

        }

        # put temp (the original a[i]) in its correct location

        a[j] = temp

    }

}

Algorithmic Implementation : 

First use a loop to get different value of slots/gaps from the gap array.Use first inner loop to compare the values with (array[gap],array[0]),(array[gap+1],array[1])...and so on . Now use the inner most loop to compare the above value and use swapping after comparing them intelligently as below :-

temp = a[j]  //here j points to a[gap] and same thing will be pointed by a[k] in the inner most loop.
So now a[k] will be emptied before we entered into the inner most loop. So we can make it to hold some value as below :
a[k]=a[k-gap].

Now here again the algorithm works in a smarter way .When you come out of the inner most loop again we are making a[k] as a[0] or a[1]... so after the end of inner loop the statement : 
 a[k]=temp;

we are again swapping the value of a[k]/a[j]/[gap] with a[gap -k].

So in short ,with this algorithm we are using swapping the compared value intelligently. 

Java Implementation

int gaps[]={12,9,8,6,4,3,2,1};
    int gap = 0;
    int j=0;
    int k=0;
    int a[]= {23,12,5,7,25,3,15,1};
    //take the gap from gaps array
    for(int i=0;i<gaps.length;i++){
        gap=gaps[i];
    //now start with the gap value such that it is less than the array length
        for(j = gap ;j<a.length;j++){
            int temp = a[j];
        //now use insertion shorting logic here
            for(k=j;k>=gap && a[k-gap]>temp;k-=gap){
                a[k]=a[k-gap];
            }
            a[k]=temp;
        }
        }
    System.out.println("Sorted");
    for(int element : a)
        System.out.print(element +"||");
  
  
    }

Gap sequences

The question of deciding which gap sequence to use is difficult. Every gap sequence that contains 1 yields a correct sort; however, the properties of thus obtained versions of Shellsort may be very different.
The table below compares most proposed gap sequences published so far. Some of them have decreasing elements that depend on the size of the sorted array (N). Others are increasing infinite sequences, whose elements less than N should be used in reverse order.

General term (k ≥ 1)	Concrete gaps	Worst-case time complexity	Author and year of publication
Floor(N/2^k)	N/2,N/4……….1	Theta(N^2)	Shell 1959
2*Floor(N/2^(k+1))+1	2(N/4)+1,…..3,1	Theta(N^(3/2))	Frank & Lazarus, 1960
2^k-1	1,3,7,15,31,63,……	Theta(N^(3/2))	Hibbard, 1963
2^k+1	1,3,5,9,17,33,65,….	Theta(N^(3/2))	Papernov & Stasevich, 1965
successive numbers of the form 3^p2^q	1,2,3,4,6,8,9,12…..	Theta(Nlog^2N)	Pratt

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]+" ");