Shell Sort

Shell sort is improvement of insertion sort.

Shell sort start comparing elements far apart,then element less apart and finally adjacent to each other.By this stage the elements are sufficiently sorted than the running time is much closer to O(n) than O(n*n).

First it sorts elements which are t distance far away from each other and eventually this distance is decreases and than it becomes one.

example

Array :

9 4 1 2 5 6 8 16 7 3 12 14 15 18 19 10 11 13 17 20

if gap is 4 than

9 4 1 2
5 6 8 16
7 3 12 14
15 18 19 10
11 13 17 20

After sorting elements which are 4 elements away from each other

5 3 1 2
7 4 8 10
9 6 12 14
11 13 17 16
15 18 19 20

and than decreases the distance and make them sorted.

Java implemetation of code

https://ideone.com/v7hJbR

Other resources of the Shell Sort

http://en.wikipedia.org/wiki/Shellsort

http://www.sorting-algorithms.com/shell-sort

Advertisements

Sorting in Java (Comparable v/s Comparators)

This post will help u if u have trouble with sorting class instances by different data fields. Also distinction between Comparable & Comparator Interfaces is show.

java.util.Arrays has many overloaded sorting methods. Simply if you want to sort any primitive type like int, boolean, char, long, double

java.util.Arrays.sort(arr);

where arr is array name!
It will use QuickSort for any primitive type.
What if the array of non-primitive type :-

Eg. Suppose you want to sort an array emp[] of type Employee class given below

public class Employee{
   int id,salary,yearOfJoining;
}

(The problem here is Arrays.sort() doesn’t know how to compare two Employees)

There are two ways according to the requirement :-

1. Comparable Interface

Comparable Interface has only one method

int compareTo(Object );

Arrays.sort() method implicitly calls compareTo(Object ) method when the array is of non-primitive type to compare two Objects.
So one just has to add an additional method to class definition.

Eg.

public class Employee{
   int id, salary, yearOfJoining;
   
   public Employee(int id,int salary,int yearofJoining){
      this.id = id;   this.salary = salary;    this.yearofJoining = yearofJoining;      
   }
   int compareTo(Object x){
      return this.id - ((Employee) x).id;
   }
}

public class Main{
   public static void main(String args[]){
      int n = 8;
      Employee es[n] = new Employee[n];
      for(int i=0;i<n;i++){
          es[i] = new Employee(n-i,100000-i*1000,2011-i);
       }
      Arrays.sort(es);
   }
}


Arrays.sort() method will sort the array with respect to employees’ ids!

2. Comparator Interface

If one wants to sort by different data members, then one must use Comparators as shown below…

Comparator Interface also has only one method

int compare(Object , Object);

But the Use of Comparator is phenomenon. Suppose now you want to sort the given array with respect to their salaries or by their yearOfJoining.
One can’t write other compareTo() method.

Here the Comparator comes Handy!

Arrays.sort(Object arr[], Comparator obj)

is the method using different Comparators.

Eg.

public class Employee{
   int id, salary, yearOfJoining;
}

public class bySalary implements Comparator<Employee>{
   int compare(Employee one, Employee two){
      return one.salary-two.salary;
   }
}

public class byYearOfJoining implements Comparator<Employee>;{
   int compare(Employee one, Employee two){
      return one.yearOfJoining - two.yearOfJoining;
   }
}

When you want to sort by Salary

Arrays.sort(array, new bySalary<Employee>())

and when by yearOfJoining

Arrays.sort(array, new byYearOfJoining<Employee>())

This is because overloaded sort method expects a comparator object.
For non-primitive types Arrays.sort() method uses MergeSort to make sure the time complexity remains O(nlogn).


“The most important property of a program is whether it accomplishes the intention of its user.”

C.A.R. Hoare

Keep Coding

Manish M Berwani

Sorting by Inbuilt Functions in C

For competitive coding purposes, writing sorting code can be messy, full of bugs, and redundant.  There is no need of writing sorting algorithms because the most efficient of them are already implemented.

In C,Inbuilt QuickSort is availabe in <stdlib.h> under the signature


void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));

Where
base                 = void pointer towards the array to be sorted,
nitems            = number of elements in the array to be sorted
size                  = sizeof(“Your DataType“)
function ptr   = pointer towards a function returning an int by comparing two values.

The function type casts void pointer to required data type and returns the difference between values.

int cmpfunc (const void * p1, const void * p2)
{
   return ( *(int*)p1 - *(int*)p2 );
}

If cmpfunc returns:

  • < 0 The element pointed by p1 goes before the element pointed by p2
  • = 0 The element pointed by p1 is equivalent to the element pointed by p2
  • > 0 The element pointed by p1 goes after the element pointed by p2

This comparator function can be used to sort structures and unions also where one has to specify which data member of by what criteria comparison between two structure variable will be done!

Eg.

#include <stdio.h>;
#include <stdlib.h>;

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

void main(){
   int arr[] = {6,5,9,8,2,1,0,69,47,58,25,11,66,23}, i;
   qsort(arr,sizeof(arr),sizeof(arr[0]),cmpfunc);
   for(i=0;i<sizeof(arr);i++)
      printf("%d\n",arr[i]);
}

Output of this code is

0
1
2
5
6
8
9
11
23
25
47


“The most important property of a program is whether it accomplishes the intention of its user.”

C.A.R. Hoare

Keep Coding
Manish M Berwani