diff options
author | Jack Sangdahl <[email protected]> | 2024-07-21 22:30:32 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-07-21 22:30:32 -0600 |
commit | 759fef99897d7e63865779ccb90ee9ca332d7b91 (patch) | |
tree | b5775933ed61127735b8dc22668660d6f83c8752 /sort_people.c | |
parent | 9737c3c7b514ec7abf057d9cb59297283988bb61 (diff) | |
download | leetcode-759fef99897d7e63865779ccb90ee9ca332d7b91.tar.gz leetcode-759fef99897d7e63865779ccb90ee9ca332d7b91.zip |
2418. sort the people
Diffstat (limited to 'sort_people.c')
-rw-r--r-- | sort_people.c | 70 |
1 files changed, 70 insertions, 0 deletions
diff --git a/sort_people.c b/sort_people.c new file mode 100644 index 0000000..2bba7dc --- /dev/null +++ b/sort_people.c @@ -0,0 +1,70 @@ +// 2418. Sort the People +#include "leetcode.h" + +/* + * you are given an array of strings 'names' and an array 'heights' that + * consists of distinct positive integers. both arrays are of length 'n'. for + * each index 'i', 'names[i]' and 'heights[i]' denote the name and height of the + * i'th person. return 'names' sorted in descending order by the people's + * heights. + */ + +void swap(int *a, int *b) { + int tmp = *a; + *a = *b; + *b = tmp; +} + +void swap_str(char **a, char **b) { + char *tmp = *a; + *a = *b; + *a = tmp; +} + +int partition(char **names, int *heights, int size, int l, int r) { + int i = l - r, j = r + 1, pivot = heights[l]; + while (1) { + do + ++i; + while (heights[i] > pivot); + do + --j; + while (heights[j] < pivot); + if (i < j) { + swap(&heights[i], &heights[j]); + swap_str(&names[i], &names[j]); + } else + return j; + } +} + +void quick_sort(char **names, int *heights, int size, int l, int r) { + if (l >= r) + return; + int p = partition(names, heights, size, l, r); + quick_sort(names, heights, size, l, p); + quick_sort(names, heights, size, p + 1, r); +} + +char **sortPeople(char **names, int namesSize, int *heights, int heightsSize, + int *returnSize) { + quick_sort(names, heights, namesSize, 0, namesSize - 1); + *returnSize = namesSize; + return names; +} + +int main() { + char *n1[] = {"Mary", "John", "Emma"}, *n2[] = {"alice", "Bob", "Bob"}; + int h1[] = {180, 165, 170}, h2[] = {155, 185, 150}, rs1, rs2; + char **sp1 = + sortPeople((char **)n1, ARRAY_SIZE(n1), h1, ARRAY_SIZE(h1), &rs1); + char **sp2 = + sortPeople((char **)n2, ARRAY_SIZE(n2), h2, ARRAY_SIZE(h2), &rs2); + for (int i = 0; i < rs1; i++) + printf("%s ", sp1[i]); // expect: "Mary","Emma","John" + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%s ", sp2[i]); // expect: "Bob","Alice","Bob" + printf("\n"); + free(sp1), free(sp2); +} |