Created
February 7, 2020 08:12
-
-
Save sriharshachilakapati/e57f68cf819ae031cf323b89764cc2ff to your computer and use it in GitHub Desktop.
Sort 3 different arrays into 1 array
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
#include <stdio.h> | |
#include <stdlib.h> | |
void merge_sort(int*, int*, int); | |
void merge2(int* dest, int* a, int* b, int lenA, int lenB) { | |
// Array indices | |
int dI = 0, aI = 0, bI = 0; | |
// Copy the values from all the arrays | |
while (aI < lenA && bI < lenB) { | |
if (a[aI] <= b[bI]) { | |
dest[dI++] = a[aI++]; | |
} else { | |
dest[dI++] = b[bI++]; | |
} | |
} | |
// Copy all the rest of a | |
while (aI < lenA) { | |
dest[dI++] = a[aI++]; | |
} | |
// Copy all the rest of b | |
while (bI < lenB) { | |
dest[dI++] = b[bI++]; | |
} | |
} | |
void merge3(int* dest, int* a, int* b, int* c, int lenA, int lenB, int lenC) { | |
// Array indices | |
int dI = 0, aI = 0, bI = 0, cI = 0; | |
// Copy the values from all the arrays | |
while (aI < lenA && bI < lenB && cI < lenC) { | |
if (a[aI] <= b[bI]) { | |
if (a[aI] <= c[cI]) { | |
dest[dI++] = a[aI++]; | |
} else { | |
dest[dI++] = c[cI++]; | |
} | |
} else { | |
if (b[bI] <= c[cI]) { | |
dest[dI++] = b[bI++]; | |
} else { | |
dest[dI++] = c[cI++]; | |
} | |
} | |
} | |
// After running the above loop, one of the array will be completely merged. | |
// Time to merge the remaining 2 arrays. | |
if (aI == lenA) { | |
merge2(dest + dI, b + bI, c + cI, lenB - bI, lenC - cI); | |
} else if (bI == lenB) { | |
merge2(dest + dI, a + aI, c + cI, lenA - aI, lenC - cI); | |
} else { | |
merge2(dest + dI, a + aI, b + bI, lenA - aI, lenB - bI); | |
} | |
} | |
void merge_sort3(int* dest, int* a, int* b, int* c, int lenA, int lenB, int lenC) { | |
// Create a temporary destination | |
int result[lenA + lenB + lenC]; | |
// Recursively sort using 2-way merge sort | |
merge_sort(result, a, lenA); | |
merge_sort(result + lenA, b, lenB); | |
merge_sort(result + lenA + lenB, c, lenC); | |
// Merge them finally | |
merge3(dest, result, result + lenA, result + lenA + lenB, lenA, lenB, lenC); | |
} | |
void merge_sort(int* dest, int* a, int len) { | |
// No need to sort if the sub length is 1 | |
if (len < 2) { | |
*dest = *a; | |
return; | |
} | |
// Create a temporary destination | |
int result[len]; | |
// Find the mid point | |
int mid = len / 2; | |
// Do the sorting | |
merge_sort(result, a, mid); | |
merge_sort(result + mid, a + mid, len - mid); | |
// Merge back | |
merge2(dest, result, result + mid, mid, len - mid); | |
} | |
int main() { | |
int a[4] = { 5, 3, 2, 11 }; | |
int b[6] = { 2, -1, 23, 34, 4, 5 }; | |
int c[1] = { 4 }; | |
int d[11] = {}; | |
merge_sort3(d, a, b, c, 4, 6, 1); | |
for (int i = 0; i < 11; i++) { | |
printf("%d ", d[i]); | |
} | |
printf("\n"); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment