What is stable sorting?
Created May 4, 2012
Stability in sorting becomes an issue for class-type objects with two or more data members. We'd obviously need to choose a data member whose values will be used to order the objects for sorting. Let's say we have multiple objects in a list whose values for the data member chosen for comparison are the same, but whose values for the other data members are different. A stable sorting algorithm will leave the original order of such objects untouched.
Stability in sorting, or lack thereof, is best illustrated by comparing the sorted order obtained through the quicksort algorithm with the sorted order obtained through the mergesort algorithm. An optimized implementation of quicksort is slightly faster than an optimized implementation of mergesort but does not guarantee stability. On the other hand, mergesort guarantees stability.
To show the comparative results obtained with quicksort and mergesort,
let's define the following class:
On the other hand, if we sort the same original list with a quicksort
algorithm using again the name field for comparison, we get
The quicksort results I showed above were obtained with a C++ program
that invoked the well-known qsort function with the following
invocation
class Person {
String name;
int rank;
Person( String nam, int r )
{
name = new String( nam );
rank = r;
}
String getName() { return name; };
public String toString() { return name + " " + rank; }
}
We will sort Person objects by using the following
Comparator object:
class PersonComparator implements Comparator {
public int compare( Object o1, Object o2 )
{
Person p1 = ( Person ) o1;
Person p2 = ( Person ) o2;
return p1.getName().compareTo( p2.getName() );
}
}
This will compare Person objects on the basis of the
name field. For the purpose of sorting, let's now construct a
list of Person objects by
List perList = new ArrayList();
perList.add( new Person( "Zaphod", 0 ) );
perList.add( new Person( "Zaphod", 1 ) );
perList.add( new Person( "Zaphod", 2 ) );
perList.add( new Person( "Betelgeuse", 0 ) );
perList.add( new Person( "Betelgeuse", 1 ) );
perList.add( new Person( "Betelgeuse", 2 ) );
perList.add( new Person( "Trillion", 0 ) );
perList.add( new Person( "Trillion", 1 ) );
perList.add( new Person( "Trillion", 2 ) );
A stable sorting algorithm will reorder the names in the list, but for
each name will leave untouched the order of appearance with respect to
the rank. We can sort this list by a mergesort algorithm by invoking
Collections.sort( perList, new PersonComparator() );
The sorted listed will be as follows:
Betelgeuse 0
Betelgeuse 1
Betelgeuse 2
Trillion 0
Trillion 1
Trillion 2
Zaphod 0
Zaphod 1
Zaphod 2
where the name is followed by the associated rank in each Person
object.
Betelgeuse 0
Betelgeuse 2
Betelgeuse 1
Trillion 2
Trillion 0
Trillion 1
Zaphod 0
Zaphod 2
Zaphod 1
Notice that objects that are equal with respect to the name field
are getting shuffled by the quicksort algorithm.
qsort( perList, 9, sizeof( Person* ), comparePersons );
where the list of Person objects was declared as
Person* perList[9];
with each element of the list instantiated by a statement like
perList[0] = new Person( "Zaphod", 0 );
perList[1] = new Person( "Zaphod", 1 );
...
...
The comparison function needed for the fourth argument of qsort
was defined by
int comparePersons( const void* arg1, const void* arg2 )
{
string str1 = (*( Person** )arg1)->name;
string str2 = (*( Person** )arg2)->name;
return ( str1 ).compare( str2 );
}