// 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); }