Общая пирамидальная сортировка: не сортировка + ошибка сегментации

Мне нужно создать «общую» пирамидальную сортировку в C.

У меня есть основной файл, который включает функцию сравнения. По сути, базовый адрес массива, количество элементов, размер каждого элемента и функция сравнения передаются в функции пирамидальной сортировки. Я столкнулся с двумя проблемами: одна программа не сортирует ее, поэтому мне было интересно, может ли кто-нибудь увидеть что-то не так с кодом. Во-вторых, я получаю ошибку сегментации после 1710 элементов.

#include <stdio.h>  
#include <string.h>
#include "srt.h"


void srtheap(void *, size_t, size_t, int (*)(const void *, const void *));
void heapify(void *, size_t, size_t, size_t, int (*)(const void *, const void *)); 

void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
  char *p1, *p2;
  char *qb=base;
  void *last = qb + (size*(nelem-1));
  for (size_t curpos = nelem-1; curpos>0; curpos=-2){
    p1 = qb + ((curpos-1)/2)*size;
    if(compar(last, (last-size)) >= 0){ 
      if(compar(last, p1) > 0){
        swap(last, p1, size);
        heapify(qb, nelem, curpos, size, compar); 
      }
    }
    else { //LEFT>RIGHT
      if(compar(last-size, p1) > 0){
         swap(last-size, p1, size);
         heapify(qb, nelem, curpos-1, size, compar);
      }
           //otherwise, parent is greater than LEFT & RIGHT,
           //or parent has swapped with child, iteration done, repeat through loop
    }      //end else, children have been compared to parent
           //end check for two children, only left child if this loop is skipped
    last = last-(2*size);
  }

/*
  **Now heapify and sort array
  */
  while(nelem > 0){
    last = qb + (size*(nelem-1)); 
    swap(qb, last, size);
    nelem=nelem-1;
    heapify(qb, nelem, 0, size, compar); //pass in array, #elements, starting pos, compare
  }

}

void heapify(void *root, size_t numel, size_t pos, size_t sz, int (*compar)(const void *, const void *)){
  void *rc, *lc, *p1;
  while(pos < numel){
    rc = root+((pos+1)*2)*sz; //right child
    lc = root+(((pos+1)*2)-1)*sz; //left child
    p1 = root+(pos*sz); //parent
    if((pos+1)*2 < numel){ //check if current element has RIGHT
      if (compar(rc, lc)>=0){
    if(compar(rc, p1)>0) {
      swap(rc, p1, sz);
      pos=(pos+1)*2; //move to RIGHT, heapify
        }
    else {
      pos = numel; //PARENT>LEFT&RIGHT, array is heapified for now 
        }
      } //end RIGHT>LEFT
      else { //LEFT>RIGHT
    if(compar(lc, p1) >0 ) {
      swap(lc, rc, sz);
      pos=((pos+1)*2)-1; // move to LEFT, heapify
    }
        else {
      pos = numel; //PARENT>LEFT&RIGHT, array is heapified for now
        } //end inner if, else
      }//end LEFT,RIGHT comparison
    }//end check for RIGHT
    else if (((pos+1)*2)-1 < numel){ //else, check if element has LEFT
      if(compar(lc, p1)>0){
    swap(lc, p1, sz);
    pos=((pos+1)*2)-1; //move to LEFT, continue heapify
      }
      else {
    pos = numel; //PARENT>LEFT, array is heapified for now
      }
    }//end check for LEFT
    else { //current element has no children, array is heapified for now
      pos = numel;
    }
  }
}

c pointers void-pointers function-pointers heapsort
person user1880760    schedule 05.12.2012    source источник
comment
о, спасибо за правку, опечатка.   -  person user1880760    schedule 06.12.2012
comment
Что касается segfault - как насчет того, чтобы запустить его в отладчике?   -  person peterph    schedule 06.12.2012

Ответы (1)


arrow_upward
2
arrow_downward

Ваш код и вопрос кажутся удивительно похожими на этот вопрос из 2010 года, поэтому я подозреваю, что это домашнее задание.

По поводу вылета проблема именно в этой строчке в srtheap:

for (size_t curpos = nelem-1; curpos>0; curpos=-2){

выражение обновления цикла, curpos=-2 неверно. Вы, вероятно, хотите curpos-=2. Однако если это так, проблема все же остается. size_t — это тип без знака, поэтому, если у вас четное количество элементов в исходном массиве, то в конечном итоге программа достигнет точки, где curpos равно 1. Когда он попытается вычесть 2, результатом будет очень большое положительное число, а не -1, как вы могли ожидать. Таким образом, условие цикла curpos>0 будет оценено как истинное, и цикл попытается получить доступ к элементу массива далеко-далеко за концом массива, что приведет к сбою.

Мне не хочется выяснять, почему ваш код не сортируется правильно, поскольку он выглядит излишне сложным. Вот рабочая универсальная пирамидальная сортировка, основанная на этой реализации.

void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *))
{
    char *cb = (char *)base;

    size_t i = (nelem / 2);
    while (1) {
        heapify(cb, size, i, nelem-1, compar);
        if (i == 0) break;
        i--;
    }

    for (size_t i = nelem-1; i >= 1; i--) {
        swap(cb, cb+(size * i), size);
        heapify(cb, size, 0, i-1, compar);
    }
}

void heapify(char *base, const size_t size, size_t root, const size_t bottom, int (*compar)(const void *, const void *))
{
    size_t maxChild = root * 2 + 1;

    if (maxChild < bottom) {
        size_t otherChild = maxChild + 1;
        maxChild = (compar(base + (otherChild * size), base + (maxChild * size)) > 0) ? otherChild : maxChild;
    } else {
        if (maxChild > bottom) return;
    }

    if (compar(base + (root * size), base + (maxChild * size)) >= 0) return;

    swap(base + (root * size), base + (maxChild * size), size);

    heapify(base, size, maxChild, bottom, compar);
}

В этой версии используется рекурсия, но преобразовать ее в цикл несложно. Я оставлю это читателю.

person sjs    schedule 06.12.2012