Created
October 7, 2020 17:48
-
-
Save gabtoschi/5972bc7bf5666e97c9c2160ee7c21175 to your computer and use it in GitHub Desktop.
A snippet of a merge function to a 3-way merge sort in C. The idea was to optimize the code size and the amount of whiles and ifs.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
typedef struct { | |
int *data; | |
int size; | |
int current; | |
} mergeArray; | |
#define COPY_MERGE_ARRAY(dest, source) dest.data[dest.current++] = source.data[source.current++] | |
int copyItemToFinalArray(mergeArray array, mergeArray final) { | |
COPY_MERGE_ARRAY(final, array); | |
return array.current == array.size ? 1 : 0; | |
} | |
int finishArrayToFinalArray(mergeArray array, mergeArray final) { | |
for (int i = array.current; i < array.size; i++) { | |
COPY_MERGE_ARRAY(final, array); | |
} | |
} | |
int* merge(int *allData, int start, int leftSize, int midSize, int endSize) { | |
/* cria mergeArrays, current começa em 0, data tem já o endereço do primeiro elemento de cada parte da Arraya */ | |
mergeArray startArray, midArray, endArray; | |
/* cria mergeArray pra ter o array final, size no tamanho certo, current começa em 0, ponteiro na primeira posição */ | |
mergeArray finalArray; | |
char startFinished, midFinished, endFinished; | |
startFinished = midFinished = endFinished = 0; | |
while (startFinished + midFinished + endFinished < 2) { | |
int startItem = startArray.data[startArray.current]; | |
int midItem = midArray.data[midArray.current]; | |
int endItem = endArray.data[endArray.current]; | |
if (!startFinished && startItem > midItem && startItem > endItem ){ | |
startFinished = copyItemToFinalArray(startArray, finalArray); | |
} else if (!midFinished && midItem > startItem && midItem > endItem ) { | |
midFinished = copyItemToFinalArray(midArray, finalArray); | |
} else { | |
endFinished = copyItemToFinalArray(endArray, finalArray); | |
} | |
} | |
if (!startFinished) finishArrayToFinalArray(startArray, finalArray); | |
if (!midFinished) finishArrayToFinalArray(midArray, finalArray); | |
if (!endFinished) finishArrayToFinalArray(endArray, finalArray); | |
return finalArray.data; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment