From 759fef99897d7e63865779ccb90ee9ca332d7b91 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sun, 21 Jul 2024 22:30:32 -0600 Subject: 2418. sort the people --- sort_people.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 70 insertions(+) create mode 100644 sort_people.c (limited to 'sort_people.c') 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); +} -- cgit v1.2.3