1

Объявление qsort() выглядит так:

void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));

Каким образом происходит работа с указателем base внутри данной функции? Обычный указатель можно сдвигать можно шифтить:

 a += 5// a += 5 * sizeof(*a);

Как это можно сделать, зная размер элементов (size)?

3
  • a += 5 * size?
    – VladD
    3 июн 2016 в 15:00
  • Только я не думаю, что есть гарантия, что указатель будет указывать на элемент массива, а не на его копию. Так что адресная арифметика имеет не слишком много смысла.
    – VladD
    3 июн 2016 в 15:02
  • Хм.. Стоп. Внутри какой именно функции? Внутри компаратора или внутри внутри самого qsort?
    – Qwertiy
    3 июн 2016 в 15:05

3 ответа 3

5

Собственно сам void не сдвигают,а приводят его к типу, который можно сдвигать - к указателю на char.

Соответственно, Ваш код стает таким

 char *pa = (char*)a; // вначале сделаем приведение
 a = a + 5 * sizeof(элемент); // а теперь можно свободно двигать

На самом деле все можно посмотреть и изучить самостоятельно. Например, тут https://android.googlesource.com/platform/bionic.git/+/eclair-release/libc/stdlib/qsort.c

0
1

Его не нужно сдвигать. Нужно просто привести его к указателю на нужный тип (тот, которому принадлежат сравниваемые объекты) и дальше работать с ними.

0

Вот написал небольшой простой пример на примере "Выборочной сортировке".

#include <stdio.h>

//выборочная сортировка
void ssort(void* base, size_t num, size_t size, int (*cmp)(const void*,const void*)){
    size_t t, i;
    char*  a, *b, *p, *e, c;

    e = (char*)base + (size * num);
    for(a = (char*)base;  a < e; a += size){
         b = a;
         for(p = (char*)a + size; p < e; p += size){
             if((*cmp)((const void*)p, (const void*)b) < 0)
                 b = p;
         }
         if(a == b)
             continue;

         if(sizeof(size_t) == size){
             t = *(size_t*)a;
             *(size_t*)a = *(size_t*)b;
             *(size_t*)b = t;
         } else {
             for(i = 0; i < size; ++i){
                 c = *(a + i);
                 *(a + i) = *(b + i);
                 *(b + i) = c;
             }
        }
     }
 }

 int icmp(const void* a, const void* b){//int
     return *(int*)a - *(int*)b;
 }

 int ccmp(const void* a, const void* b){//char
     return *(char*)a - *(char*)b;
 }

 int dcmp(const void* a, const void* b){//double
     double d1 = *(double*)a;
     double d2 = *(double*)b;
     if(d1 < d2)
          return -1;
     return (d1 > d2) ? 1 : 0;
 }

 int main(void){
    int i;
    int a[] = { 4, 8, 3, 2, 0, 2, 1 };
    int n1  = sizeof(a)/sizeof(a[0]);

    char b[] = { 'E', 'Z', 'C', 'F', 'B', 'D', 'A' };
    int  n2  = sizeof(b)/sizeof(b[0]);

    double c[] = { 1.2, 5.4, 1.2, 0.9, 0.2, 3.3, -7.1, 1.9, 1.2 };
    int    n3  = sizeof(c)/sizeof(c[0]);

    ssort(a, n1, sizeof(a[0]), &icmp);//int
    for(i = 0; i < n1; ++i)
        printf("%d ", a[i]);
    putchar('\n');

    ssort(b, n2, sizeof(b[0]), &ccmp);//char
    for(i = 0; i < n2; ++i)
        printf("%c ", b[i]);
    putchar('\n');

    ssort(c, n3, sizeof(c[0]), &dcmp);//double
    for(i = 0; i < n3; ++i)
        printf("%lg ", c[i]);
    return 0;
}

p.s. пример без оптимизации, просто привёл для наглядности

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.