OOP in C - Merge Sort Algorithm

Introduction

Object Oriented Programming is a well known programming methodology, that is supported by some leading programming languages such as C++, Java, C# to name a few. This is the methodology I use most when I program. Most of the time, I program in C++.

However, the principles of OOP can be applied in any language. OOP is a way of thinking that influences the way of programming whether or not the programming language supports it.

In this experiment, I apply OOP to writing a program in C. The result may not be the ideal way to do it in C, since C is the choice language for programs that are closer to the hardware, and in situations where performance is critical. Usually, there is a trade off between writing in a reusable manner on one hand, and conforming with high performance requirements on the other hand.

The Code

I attempt here to follow my OOP habits without trying to make the code particularly reusable, and see what I come up with.

The program demonstrates the merge sort algorithm. It sorts an array of unsigned integers. The program essentially runs unit tests and black box tests on my implementation of the algorithm.

• Download from: https://github.com/ariel1segal/mergesort/releases

Or clone the git repository:

git clone https://github.com/ariel1segal/mergesort.git

The code has the OOP features:

• An object to represent a list of items
• Constructors
• Destructor
• Delegation of the compare operation
• Decomposition of the algorithm

All these features are oriented towards code reuse, while as I mentioned above, it is not the intuitive way to code in C.

Benefits of Using OOP Principles in this Case

Let's examine the benefits of using OOP principles for this particular C program:

Object Constructors/Destructor

The object type is defined as this simple structure.

typedef struct
{
    unsigned size; // Length of list.
    unsigned *ar; // pointer to an unsigned int array.
} list_t;

Obviously, no attempt is made to support different element types. Elements are created only with the help of the constructors, that allocate the memory, and initialize the elements.

The Constructors

list_t *CreateList(unsigned size, unsigned ar[]);
list_t *CreateEmptyList(unsigned size);
list_t *CloneList(list_t *orig);

The names of the constructors are self explanatory.

The only proper way to dispose an element is to use the destructor:

void DestroyList(list_t **list);

It first frees the memory allocated to the array, and then releases the object.

Benefit number 1: Thread safe code. When manipulating a list object, there is no access to global variables.

Delegation of the Compare Operation

The basic operation used in order to sort elements is to compare two elements. The delegation of this operation generalizes the type of sort to do. I provide in the code two implementations for the compare operation. One, precedes the bigger value for descending order sort, and the other precedes the smaller value for ascending order sort. So in general, when comparing two elements, the operation decides which element precedes in order.

The delegation is done with a pointer to a function. It is declared as a type:

typedef compare_t (*compareFunction_t)(unsigned, unsigned);

The compare function returns a value of compare_t type:

typedef enum
{
    Tie_e
    , LeftWins_e
    , RightWins_e
} compare_t;

Benefit number 2: Some degree of reusability of the code. To reuse the code for sorting elements other than unsigned integers is a more complicated task. This is an example that it is enough to have an OOP mind set when coding to get some aspects of the code reusable.

Algorithm Decomposing

The Object Oriented mind set leads to decomposing the algorithm into smaller parts, making them operations that can be applied on the object. The three building blocks of the algorithm are:

• Compare - discussed above, uses delegation

The other two do not use delegation.

• Split - splitting a list into two lists, of the same length, as much as possible

  void SplitList(list_t *orig, list_t **left, list_t **right);

• Merge - merge together two sorted lists into one sorted list

void MergeLists(list_t **merged, list_t *left, list_t *right,

compareFunction_t compare);

Now the sort algorithm in pseudocode looks like this:

if list length is greater than 1
    split the list into left_list and right_list
    sort left_list // recursive call
    sort right_list // recursive call
    merge left_list and right_list into sorted list
    return sorted list
else if list length equals 1
    the list is sorted - return it

Benefit number 3: It is very easy to change the code, to make it sort other type rather than unsigned integer. Simply, change the type of array in list_t, and provide the appropriate compare function.

This code is not reusable, because:

1. The code must be changed in order to use it for other types.
2. The code must be duplicated for each type that the program needs to sort.

Conclusion

OOP is all about code reuse and easy maintainability. While maintainability should be never compromised, regardless of the programming language, code reusability has some downsides for most software written in C. As I mentioned earlier, C is a choice language for pieces of code that must adhere to strict performance requirements. In my attempt to apply OOP principles to the C language, I was inspired by C++. Code reuse the way C++ implements it, tends to reduce performance. Another problem is, that OOP design tends to produce code that uses a lot of heap memory, which might not be suited for systems with limited ROM memory.

The benefits of applying OOP to C are mostly in degrees of code reusability, though, I have explained above why this code is not truly reusable.

The encapsulation feature of OOP tends to produce thread safe code, which is a big advantage for many systems that the C language if the first choice, such as real time applications.

The Next Step

Is it possible to write true reusable code in C?

Such a code will have to conform with two rules:

1. One piece of code can be used for more than one instance of the same functionality, or for multiple threads of executions.
2. No need to change the code to support different data types.

These two rules also derive the requirement that the reusable code should support multiple instances of different data types in the same program.

In my next post, I will experiment with attempts to change the code to be more reusable.