Как адаптировать этот алгоритм QuickSort (на языке C) к массиву строк? - PullRequest
Новая
       7

Как адаптировать этот алгоритм QuickSort (на языке C) к массиву строк?

0 голосов
/ 06 апреля 2020

Мне нужно отсортировать содержимое (в алфавитном порядке, используя strcmp() массива строк, но мне не разрешено использовать функцию qsort(). С этим кодом мне удалось отсортировать числовые значения, но у меня возникли сложности время, чтобы адаптировать его для сортировки строк. 

/* A utility function to swap two elements */
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 

void swap_string(char c[63], char d[63]){
    char temp[63];
    strcpy(temp, c);
    strcpy(c, d);
    strcpy(d, temp);
}

/* This function takes last element as pivot, places 
   the pivot element at its correct position in sorted 
    array, and places all smaller (smaller than pivot) 
   to left of pivot and all greater elements to right 
   of pivot */
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];    /* pivot */
    int i = (low - 1);  /* Index of smaller element */

    for (j = low; j <= high- 1; j++) 
    { 
        /* If current element is smaller than the pivot */
        if (arr[j] < pivot) 
        { 
            i++;    /* increment index of smaller element */
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 

/* The main function that implements QuickSort 
 arr[] --> Array to be sorted, 
  low  --> Starting index, 
  high  --> Ending index */
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        /* pi is partitioning index, arr[p] is now 
           at right place */
        int pi = partition(arr, low, high); 

        /* Separately sort elements before */
        /* partition and after partition */
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
}

1 Ответ

0 голосов
/ 06 апреля 2020

Во-первых, вам просто нужно создать функцию подкачки для строки, а не для int

void swap(char ** a, char ** b) { 
    char * t = *a;
    *a = *b;
    *b = t;
}

Поскольку вы сортируете массив строк, поэтому вместо ввода * 1006 используется ввод ** arr * Здесь функция разделения: 

int partition (char ** arr, int low, int high) { 
    char * pivot = arr[high];    // pivot 
    int i = (low - 1);  // Index of smaller element 

    for (int j = low; j <= high- 1; j++) { 
        // If current element is smaller than the pivot 
        if (strcmp(arr[j],pivot) < 0) { 
            i++;    // increment index of smaller element 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
}

И, функция быстрой сортировки: 

void quickSort(char **arr, int low, int high) { 
    if (low < high) { 
        /* pi is partitioning index, arr[p] is now 
           at right place */
        int pi = partition(arr, low, high); 


        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
}

Тогда основная функция для теста: 

int main(){

   char *a = "abc";
   char *b = "cdf";
   swap(&a, &b);
   printf("a = %s, b= %s\n", a, b);
   char * data[10]={"something2", "something0", "something1", "something6", "something8", "something4", "something5","something7", "something3", "something9"};
   quickSort(data, 0, 9);
   for(int i = 0; i < 10; i++) {
    printf("%s, ", data[i]);
   }

   return 0;
}

ОБНОВЛЕНИЕ:

Если вам нужен именно массив producer[100][63]. Вы можете изменить объявление функции. В этом примере я использую массив data[10][63] для тестирования. Фактически, вы можете использовать 100 вместо 10.

Функция обмена: 

void swap(char a[63], char b[63]) { 
    char t[63];
    strcpy(t, a);
    strcpy(a, b);
    strcpy(b, t);
}

Затем функция разделения: 

int partition (char arr[10][63], int low, int high) { 
    char * pivot = arr[high];    // pivot 
    int i = (low - 1);  // Index of smaller element 

    for (int j = low; j <= high- 1; j++) { 
        // If current element is smaller than the pivot 
        if (strcmp(arr[j],pivot) < 0) { 
            i++;   
            swap(arr[i], arr[j]); 
        } 
    } 
    swap(arr[i + 1], arr[high]); 
    return (i + 1); 
}

Наконец, функция быстрой сортировки: 

void quickSort(char arr[10][63], int low, int high) { 
    if (low < high) { 
        /* pi is partitioning index, arr[p] is now 
           at right place */
        int pi = partition(arr, low, high); 

        // Separately sort elements before 
        // partition and after partition 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
}

Основное для теста: 

int main(){
  char data[10][63]={"something2", "something0", "something1", "something6", "something8", "something4", "something5","something7", "something3", "something9"};
   quickSort(data, 0, 9);
   for(int i = 0; i < 10; i++) {
    printf("%s, ", data[i]);
   }

   return 0;
}
...