如何使用快速排序對一對整數的結構進行排序？

Question

假設我有下面的結構：

struct Pair { 
    int x; 
    int y; 
} 

欲由該對中的第一個元素的數組進行排序，即，X，然後通過所述第二元件，所以如果我們給出下列：

input: [(1,2), (1,0), (2,3), (1,4), (2,2)] 
output: [(1,0), (1,2), (1,4), (2,2), (2,3)] 

現在我有兩個函數，其中一個按第一個元素排序數組，第二個按第二個元素排序，但效率較低。我怎樣才能遍歷數組一次，並達到預期的結果？

void sort1(Pair ps[], int size) { 
    int i, j; 

    for (i = 0; i < size; i++) { 
     for (j = i + 1; j < size; j++) { 
      if (ps[j].x > ps[j+1].x) { 
       Pair temp = ps[j+1]; 
       ps[j+1] = ps[j]; 
       ps[j] = temp; 
      } 
     } 
    } 
} 

void sort2(Pair ps[], int size) { 
    int i, j; 

    for (i = 0; i < size; i++) { 
     for (j = i + 1; j < size; j++) { 
      if (ps[j].y > ps[j+1].y) { 
       Pair temp = ps[j+1]; 
       ps[j+1] = ps[j]; 
       ps[j] = temp; 
      } 
     } 
    } 
} 

此外，有沒有一種快速的方法來做到這一點，使用內置的排序功能？

Answer 1

您可以使用qsort()這是一個快速排序的C庫實現。

爲了使用這個功能，你需要設計一個cmp功能兩個x值對彼此進行比較，如果它們是關係，然後排序y。

爲了這個不被凌亂成一個cmp功能，你可以先製作一個小功能，測試兩個整數的平等：

int compare_int(const int a , const int b) { 
    if (a < b) { 
     return -1; 
    } else if (a > b) { 
     return 1; 
    } 
    return 0; 
} 

然後你就可以在這個整合到你的主cmp功能， qsort()將會打電話。該函數可以簡單：

int cmp_func(const void *a, const void *b) { 
    const pair_t *num1 = (pair_t *)a; 
    const pair_t *num2 = (pair_t *)b; 

    if (num1->x == num2->x) { 
     return compare_int(num1->y, num2->y); 
    } else if (num1->x > num2->x) { 
     return +1; 
    } 
    return -1; 
} 

然後，你可以簡單地調用qsort()如下所示：

qsort(ps, sizeof(ps)/sizeof(ps[0]), sizeof(pair_t), cmp_func); 

下面是一些例子代碼做到這一點：

#include <stdio.h> 
#include <stdlib.h> 

#define ARRAYSIZE(x) ((sizeof(x))/sizeof(x[0])) 

typedef struct { 
    int x; 
    int y; 
} pair_t; 

int compare_int(const int a , const int b) { 
    if (a < b) { 
     return -1; 
    } else if (a > b) { 
     return 1; 
    } 
    return 0; 
} 

int cmp_func(const void *a, const void *b) { 
    const pair_t *num1 = (pair_t *)a; 
    const pair_t *num2 = (pair_t *)b; 

    if (num1->x == num2->x) { 
     return compare_int(num1->y, num2->y); 
    } else if (num1->x > num2->x) { 
     return +1; 
    } 
    return -1; 
} 

void print_array(pair_t ps[], size_t n) { 
    printf("["); 
    for (size_t i = 0; i < n; i++) { 
     printf("(%d,%d)", ps[i].x, ps[i].y); 
     if (i != n-1) { 
      printf(", "); 
     } 
    } 
    printf("]\n"); 
} 

int main(void) { 
    pair_t ps[] = {{1,2}, {1,0}, {2,3}, {1,4}, {2,2}}; 

    printf("Input: "); 
    print_array(ps, ARRAYSIZE(ps)); 

    qsort(ps, ARRAYSIZE(ps), sizeof(pair_t), cmp_func); 

    printf("Output: "); 
    print_array(ps, ARRAYSIZE(ps)); 

    return 0; 
} 

，輸出：

Input: [(1,2), (1,0), (2,3), (1,4), (2,2)] 
Output: [(1,0), (1,2), (1,4), (2,2), (2,3)] 

注意：您的原始代碼正在實施氣泡排序，平均運行時間爲O（n^2）。但是，如果您使用qsort()代替，則可以實現平均運行時間更快的平均運行時間（O（logN））。如果n變大，這種差異將有助於達到更快的結果。

Answer 2

你只需要一個適當的功能來比較兩個對：

int comparePairs (const void * a, const void * b) 
{ 
    const Pair* A = (const Pair*) a; 
    const Pair* B = (const Pair*) b; 
    return (A.x == B.x) ? (A.y - B.y) : (A.x - B.x); 
} 

然後你可以使用內置的功能qsort。