#include "srt.h"
#include <stdio.h>
#define ElementCount(array) sizeof(array) / sizeof((array)[0])
////////////////////////////
// FLoat helper functions //
////////////////////////////
int FloatCompare(const void * first, const void * second)
{
return *(float *)first - *(float *)second;
}
void PrintFloatArray(float * array, size_t elementCount)
{
for (size_t i = 0; i < elementCount; i++)
printf("%f, ", array[i]);
printf("\n");
}
///////////////////////////
// Byte helper functions //
///////////////////////////
typedef unsigned char byte;
int ByteCompare(const void * first, const void * second)
{
return *(signed char *)first - *(signed char *)second;
}
void PrintByteArray(byte * array, size_t elementCount)
{
for (size_t i = 0; i < elementCount; i++)
printf("%hhu, ", array[i]);
printf("\n");
}
////////////////////////////
// Sort testing functions //
////////////////////////////
void TestBubbleSort(const float * originalFloatArray, size_t floatElementCount, const byte * originalByteArray, size_t byteElementCount)
{
printf("Bubble Sort Test:\n");
printf("=================\n");
// Create a copy of the original arrays
float floatArray[floatElementCount];
memcpy(floatArray, originalFloatArray, sizeof(float) * floatElementCount);
byte byteArray[byteElementCount];
memcpy(byteArray, originalByteArray, sizeof(byte) * byteElementCount);
// Test the float sorting
printf("Float array before sorting: ");
PrintFloatArray(floatArray, floatElementCount);
srtbubb(floatArray, sizeof(float), floatElementCount, FloatCompare);
printf("Float array after sorting: ");
PrintFloatArray(floatArray, floatElementCount);
// Test the byte sorting
printf("\nByte array before sorting: ");
PrintByteArray(byteArray, byteElementCount);
srtbubb(byteArray, sizeof(byte), byteElementCount, ByteCompare);
printf("Byte array after sorting: ");
PrintByteArray(byteArray, byteElementCount);
printf("\n\n");
}
void TestHeapSort(const float * originalFloatArray, size_t floatElementCount, const byte * originalByteArray, size_t byteElementCount)
{
printf("Heap Sort Test:\n");
printf("===============\n");
// Create a copy of the original arrays
float floatArray[floatElementCount];
memcpy(floatArray, originalFloatArray, sizeof(float) * floatElementCount);
byte byteArray[byteElementCount];
memcpy(byteArray, originalByteArray, sizeof(byte) * byteElementCount);
// Test the float sorting
printf("Float array before sorting: ");
PrintFloatArray(floatArray, floatElementCount);
srtheap(floatArray, sizeof(float), floatElementCount, FloatCompare);
printf("Float array after sorting: ");
PrintFloatArray(floatArray, floatElementCount);
// Test the byte sorting
printf("\nByte array before sorting: ");
PrintByteArray(byteArray, byteElementCount);
srtheap(byteArray, sizeof(byte), byteElementCount, ByteCompare);
printf("Byte array after sorting: ");
PrintByteArray(byteArray, byteElementCount);
printf("\n\n");
}
void TestInsertionSort(const float * originalFloatArray, size_t floatElementCount, const byte * originalByteArray, size_t byteElementCount)
{
printf("Insertion Sort Test:\n");
printf("====================\n");
// Create a copy of the original arrays
float floatArray[floatElementCount];
memcpy(floatArray, originalFloatArray, sizeof(float) * floatElementCount);
byte byteArray[byteElementCount];
memcpy(byteArray, originalByteArray, sizeof(byte) * byteElementCount);
// Test the float sorting
printf("Float array before sorting: ");
PrintFloatArray(floatArray, floatElementCount);
srtinsr(floatArray, sizeof(float), floatElementCount, FloatCompare);
printf("Float array after sorting: ");
PrintFloatArray(floatArray, floatElementCount);
// Test the byte sorting
printf("\nByte array before sorting: ");
PrintByteArray(byteArray, byteElementCount);
srtinsr(byteArray, sizeof(byte), byteElementCount, ByteCompare);
printf("Byte array after sorting: ");
PrintByteArray(byteArray, byteElementCount);
printf("\n\n");
}
void TestMergeSort(const float * originalFloatArray, size_t floatElementCount, const byte * originalByteArray, size_t byteElementCount)
{
printf("Merge Sort Test:\n");
printf("================\n");
// Create a copy of the original arrays
float floatArray[floatElementCount];
memcpy(floatArray, originalFloatArray, sizeof(float) * floatElementCount);
byte byteArray[byteElementCount];
memcpy(byteArray, originalByteArray, sizeof(byte) * byteElementCount);
// Test the float sorting
printf("Float array before sorting: ");
PrintFloatArray(floatArray, floatElementCount);
srtmerg(floatArray, sizeof(float), floatElementCount, FloatCompare);
printf("Float array after sorting: ");
PrintFloatArray(floatArray, floatElementCount);
// Test the byte sorting
printf("\nByte array before sorting: ");
PrintByteArray(byteArray, byteElementCount);
srtmerg(byteArray, sizeof(byte), byteElementCount, ByteCompare);
printf("Byte array after sorting: ");
PrintByteArray(byteArray, byteElementCount);
printf("\n\n");
}
int main()
{
// Create test data
float floatArray[] = { 9.9f, 8.8f, 7.7f, 6.6f, 5.5f, 4.4f, 3.3f, 2.2f, 1.1f, 0.0f };
size_t floatElementCount = ElementCount(floatArray);
byte byteArray[] = { 9u, 8u, 7u, 6u, 5u, 4u, 3u, 2u, 1u, 0u };
size_t byteElementCount = ElementCount(byteArray);
// Run the sort tests
TestBubbleSort(floatArray, floatElementCount, byteArray, byteElementCount);
TestHeapSort(floatArray, floatElementCount, byteArray, byteElementCount);
TestInsertionSort(floatArray, floatElementCount, byteArray, byteElementCount);
TestMergeSort(floatArray, floatElementCount, byteArray, byteElementCount);
return 0;
}
#ifndef SRT_H
#define SRT_H
#include <string.h>
#define MAX_BUF 256
#define swap(qx,qy,sz) \
do { \
char buf[MAX_BUF]; \
char *q1 = qx; \
char *q2 = qy; \
for (size_t m, ms = sz; ms > 0; ms -= m, q1 += m, q2 += m) { \
m = ms < sizeof(buf) ? ms : sizeof(buf); \
memcpy(buf, q1, m); \
memcpy(q1, q2, m); \
memcpy(q2, buf, m); \
} \
} while (0)
void srtbubb(void *, size_t, size_t, int (*)(const void *, const void *));
void srtheap(void *, size_t, size_t, int (*)(const void *, const void *));
void srtinsr(void *, size_t, size_t, int (*)(const void *, const void *));
void srtmerg(void *, size_t, size_t, int (*)(const void *, const void *));
#endif /* SRT_H */
#include "srt.h"
void srtbubb(void * buffer, size_t elementSize, size_t elementCount, int (*compare)(const void *, const void *))
{
for (size_t i = 0; i < elementCount - 1; i++)
{
for (size_t j = 0; j < elementCount - 1 - i; j++)
{
if (compare(buffer + elementSize * j, buffer + elementSize * (j + 1)) > 0)
swap(buffer + elementSize * j, buffer + elementSize * (j + 1), elementSize);
}
}
}
void srtheap(void * buffer, size_t elementSize, size_t elementCount, int (*compare)(const void *, const void *))
{
// TODO: Implement funciton
}
void srtinsr(void * buffer, size_t elementSize, size_t elementCount, int (*compare)(const void *, const void *))
{
// TODO: Implement funciton
}
void srtmerg(void * buffer, size_t elementSize, size_t elementCount, int (*compare)(const void *, const void *))
{
// TODO: Implement funciton
}