Sorting other types of data

// swap two integer elements
inline void exch(int &a, int &b)
{
   int t = a;
   a = b;
   b = t;
}

// sort an array of integers using bubble sort
void bsort(int data[], int N)
{
   int p, i;
   for(p=N-1;p>0;p--)
      for(i=0;i<p;i++)
         if( data[i] > data[i+1] ) 
            exch(data[i], data[i+1]);
}

Our question is: what do we need to change to sort not an array of integers, but an array or floating point numbers? And the answer is very simple - all we need to do is to change the data type from int to double.

// swap two floating point elements
inline void exch(double &a, double &b)
{
   double t = a;
   a = b;
   b = t;
}

// sort an array of floating point numbers using bubble sort
void bsort(double data[], int N)
{
   int p, i;
   for(p=N-1;p>0;p--)
      for(i=0;i<p;i++)
         if( data[i] > data[i+1] ) 
            exch(data[i], data[i+1]);
}

What do we need to do to sort an array of character? Same thing - just change the data type from int to char.

What do we do if we need to sort an array of C-strings? This case is a little bit more difficult, because it is not enough to change the data type from int to char*. The small problem is - the comparison operation is not defined for this type of data. More exactly, it is defined, but it compares addresses not the strings located at these addresses. To overcome this problem we need to use a special comparing function named strcmp() that takes two strings and returns a positive number if the first string is greater than the second, zero if they are equal, and a negative number if the first is less than the second. So, we need to do two things:

• change the data type and
• use another way co compare elements

Now let's consider a more general question. What do we need to do if we need to sort an array of some structures, for example

struct Record {
  int  ssn;
  char fname[32];
  char lname[32];
};

// swaps two element of any type
template <class Element>
inline void exch(Element &a, Element &b)
{
  Element t = a;
  a = b;
  b = a;
}

// sort an array of element of any type using bubble sort
template <class Element>
void bsort(Element data[], int N)
{
   int p, i;
   for(p=N-1;p>0;p--)
      for(i=0;i<p;i++)
         if( data[i] > data[i+1] ) 
            exch(data[i], data[i+1]);
}

For example, if we need to sort an array of the structures Record mentioned earlier, we need to define the comparison operator > for those structures. We can define this operator like this

bool operator>(const Record &a, const Record &b)
{
	return a.ssn > b.ssn;
}

Record *data = new Record[N];
// get some data into the array
bsort(data, N);

Idea of index sorting

N = 10,000 Structure size Runtime in msec 4+16 4,697 4+64 5,683 4+256 6,991 4+1024 12,047

N = 20,000 Structure size Runtime in msec 4+16 18,837 4+64 23,441 4+256 29,523 4+1024 47,673

N = 40,000 Structure size Runtime in msec 4+16 106,343 4+64 142,574 4+256 178,707 4+1024 198,025

As you can see from the table the runtime grows as well as the size of the string part of the structure grows. (In the notation 4+256 4 is the size of the integer part and 256 is the size of the strong part.) Since we are using the Bubble sort method, the number of comparison stays the same and always equal to N*(N-1)/2. Because the price of each comparison also stays the same (we use only the integer part of the structure to compare two elements and we pass elements by reference to the comparison operator), we can conclude that the price of exchange grows up.

To avoid the exchanging those big elements of the arrays we will use the idea of index. We will create a separate array of integers index[], such that the element index[i] will contain the number of the right spot for the element data[i]. During the sorting process we will swap only the indexes; that is, elements of the original array data[] will b used only for comparisons. Thus, the initial picture will look like

Index array and data array before sorting.

and after the sorting the elements of the index array will be ordered like

Index array and data array after sorting.

Implementation of indexes

To implement the idea of index sorting we will define a new class Index as

class Index {
   private:
      int value;
   public:
      TIndex() { value=0; };
      TIndex(int v) { value=v; };
      operator =(int v) { return (value=v); };
      operator int() const { return value; };
};

As you can see, the Index element contains nothing but an integer value. This integer value will contain the number of the element in the original array data[]. For this class we defined two constructors and we also defined two operators:

• the assignment operator - to be able to write code like

  Index ind = 5;

• and the int operator - to automatically convert elements if the type Index into integers. This gives us opportunity to use elements of the Index type as indexes:

  Index ind = 5;
  if( data[ind] < ... ) 

Now we need to recall that when we compare two elements from the index array (e.g. elements 0 and 1 from pictures), we actually need to compare the corresponding elements from the array data[]. In other words, we have to define comparisons operators for the new type Index as something like

// Remember: when comparing two elements of the Index type we are NOT interested
//  in comparing the values of these Index elements, instead we have to compare
//  the corresponding records in the array data[]
bool operator>(const Index &i, const Index &j)
{
	return data[i] > data[j];
}

Now we are ready to sort the indexes instead of the real data records. The only thing we need to do is the initialization of Index array:

// initialize the index array
Index *index = new Index[N];
for(i=0;i<N;i++) 
   index[i] = i;
   
// sort the array of indexes   
bsort(index, N);


// print the data[] array back in the sorted order
for(i=0;i<N;i++)
   cout<<data[ index[i] ];

If we measure runtime of the index sorting, then we can see that the time doesn't really depend now on the size of the data elements:

N = 10,000 Structure size Runtime in msec 4+16 6,620 4+64 6,810 4+256 6,730 4+1024 6,730

N = 20,000 Structure size Runtime in msec 4+16 26,619 4+64 27,439 4+256 27,079 4+1024 27,089

N = 40,000 Structure size Runtime in msec 4+16 106,594 4+64 109,718 4+256 109,057 4+1024 108,436

Comparing with the previous table, we can note that for small records the index method doesn't give any speed advantage, moreover, sometimes it produces worst results.

Rearranging elements by indexes

Since the index array contains all information about the right order of the elements in the data array, we can use that information to rearrange the array for just one pass through the data array. The algorithm that does it is simple to explain. Since index[i] contains the index of the element that has to take position i in the array data[], then to place all elements at their places, we need

1. assign i = 0
2. look at the index[i]. If index[i] is equal to i, then we don't have to do anything. Otherwise, index[i] gives us the index of the element that should take this position. Thus, we need to
   • assign service variable k value of i
   • save data[k] in a temporary location
   • move data[ index[k] ] into data[k]
   • save this position j=k and jump to the next k=index[k]
   • do not forget to save information about the moves we have made index[j]=j
   • keep repeating these instructions until the chain meets its end (k becomes equal i)
3. increment the value of the variable i

Rearranging data by indexes.