-
Notifications
You must be signed in to change notification settings - Fork 1
Merge sort algorithm in C. This program demonstrates merge sort of an array of unsigned integers. This C code is written with the mindset of OOP, and features objects, constructor/destructor, separation of data and algorithm.
License
ariel1segal/mergesort
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
Merge Sort Algorithm in C. -------------------------- This program demonstrates merge sort of an array of unsigned integers. This C code is written with the mindset of OOP, and features objects, constructor/destructor, separation of data and algorithm. The program essentially runs unit tests and black box tests of the algorithm. Build and Run ------------- 1. clone the project 2. cd <project directory> 3. go to the source directory: cd src 4. make 5. the execution file 'sort' is in the binary directory cd ../bin 6. ./sort Description ----------- Implementation of the merge sort is written in C in OOP fashion. The following is an introduction to the code. After reading this, it will be easy to read the code and understand it. The source code is well commented. * Object typedef struct { unsigned size; // Length of list. unsigned *ar; // pointer to an unsigned int array. } list_t; * Compare Function - Pointer to function type typedef compare_t (*compareFunction_t)(unsigned, unsigned); The user provides the compare function, to gain more flexibility. The tests give two examples of compare functions, one for ascending order sort, and the other for descending order sort. The compare function returns a value of compare_t type, to make the compare function more general. Subtracting two elements will not give a direct indicator of which one is bigger in the case of sorting unsigned integers, as it will do for signed integers. The compare function returns three values, left element bigger, right element bigger, and both are equal. The criteria which to return one of these values is determined in the implementation of the compare function The return type: typedef enum { Tie_e , LeftWins_e , RightWins_e } compare_t; This is also a preparation for modifying the code to support sorting of arrays of other types. * constructors Creates a new list from an array of unsigned integers. This function allocates memory for the object of type list_t and for the array, and copies the array. This function does not change the original array accepted as parameter. list_t *CreateList(unsigned size, unsigned ar[]); Creates a new empty list. This function gets the size and allocates memory for an array of unsigned integers. The memory is not initialized. list_t *CreateEmptyList(unsigned size); Clones a list_t object. list_t *CloneList(list_t *orig); * destructor First frees the memory allocated to the array, and then releases the object. void DestroyList(list_t **list); * The Merge Function Implementation the merge sort algorithm list_t *MergeSort(list_t *list, compareFunction_t compare); * Helper Functions Splits the list into two new objects. Does not free the original list. void SplitList(list_t *orig, list_t **left, list_t **right); Creates a new object by merging two objects. Does not free memory. void MergeLists(list_t **merged, list_t *left, list_t *right, compareFunction_t compare); * Compare Functions Two compare functions, one will make the sort algorithm sort the list in descending order, and the other in ascending order. compare_t DescendingOrder(unsigned left, unsigned right); compare_t AscendingOrder(unsigned left, unsigned right);
About
Merge sort algorithm in C. This program demonstrates merge sort of an array of unsigned integers. This C code is written with the mindset of OOP, and features objects, constructor/destructor, separation of data and algorithm.
Resources
License
Stars
Watchers
Forks
Packages 0
No packages published