Логическая ошибка - сортировка вставок

Question

Структура каталогов кода,

$ pwd
/home/Personal/../Computing
$ ls -LR
.:
list testList.c testList.exe type.h

./list:
arrayImpl.c  linkedListImpl.c  list.h

---

/********* type.h ********/
#ifndef TYPE_H
#define TYPE_H /* Header guard */
 #include<stdbool.h>
 #include<stddef.h>
 #include<stdlib.h>
 #include<stdio.h>
 #include<string.h>
#endif /* TYPE_H */

---

/************ list.h ************/

#ifndef LIST_H /* Header guard */
#define LIST_H
#include"type.h"

/***************** Usage-start ************/

#if defined(ARRAY) || (LINKED_LIST)

  /* To ensure Encapsulation(i.e., maintain invariants of array & linked list)
     So, Just provide the `List` declartion, to avoid mis-use of `List`
  */
  typedef struct List List;

#else
  #error "Wrong list implementation macro name !!!"
#endif



 void listInsertItem(List *, void *newItem);
 void *listDeleteItem(List *, int listIndex);
 void *listDeleteLastItem(List *);
 void *listDeleteFirstItem(List *);
 const void *listGetItem(List *, const int index); /* 'index' is array index */
 int listGetSize(List *);


 /*********** Searching & Sorting algorithm - start*************/

 typedef int (*compareTo)(const void *key, const void *item);
 typedef bool (*isLess)(const void *key, const void *item);
 typedef bool (*isEqual)(const void *key, const void *item);

 void *linearSearch(const void *key, List *, size_t listSize, isEqual);
 /*
   bsearch() function returns a pointer to a matching member
   of the array, or NULL if no match is found
 */
 void *binarySearch(const void *key, List *, size_t listSize, compareTo);


 /*'listSize' elements. First argument points to list.*/
 void insertionSort(List *, size_t listSize, isLess);
 void selectionSort(List *, size_t listSize, compareTo);
     void shellSort(List *, size_t listSize, compareTo);
     void mergeSort(List *, size_t listSize, compareTo);
     void quickSort(List *, size_t listSize, compareTo);
/**************** Sorting algorithm - end*************/

 List* createList();
 void freeList(List *);
#endif /* LIST_H */

/***************** Usage-end ***************/

---

Ниже приведена реализация массива,

/***************** arrayImpl.c **************/

#include"list/list.h"

#if defined(ARRAY)
typedef enum {DOUBLE_THE_LIST, HALF_THE_LIST}ListResizeOperation;

static List *resizeList(List *, ListResizeOperation);
static void *bSearchRecur(const void *, void**, int, int, compareTo);
static void *bSearchIter(const void *, void **, int, int, compareTo);

static void swap(void **, int i, int j);
static void insSort(void **, size_t, isLess);

/************ Representation - start ************/
typedef struct List{
  void **array;

  /* Housekeeping - Array enhancement/shrink */
  int lastItemPosition;
  int size;
}List;

#define INITIAL_LIST_SIZE 50
#define FIRST_ITEM_INDEX 0
/********************* Representation - end ************/




/************* Usage - start ***************/
List *createList(){

    List *list = malloc(sizeof(List));
    if(list != NULL){

      list->array = malloc(INITIAL_LIST_SIZE*sizeof(void*));
      if(list->array != NULL){

        /* Is it safe to initialise zero to  array of  pointers? */
        list->array = memset(list->array, 0, INITIAL_LIST_SIZE*sizeof(void *));
        list->lastItemPosition = -1;
        list->size = INITIAL_LIST_SIZE;
      }else{
        free(list);
        list = NULL;
      }
    }

    return list;
}

void freeList(List *list){

  if(list != NULL){
    if(list->array != NULL){
      int index = 0;
      while( index < list->size){
        free(list->array[index++]);
      }
      free(list->array);
    }else{
      fprintf(stderr, "Invalid list sent to freeList()\n");
    }
    free(list);
  }
}


int listGetSize(List *list){
  if(list != NULL){
    return list->lastItemPosition + 1;
  }else{
    fprintf(stderr, "List is NULL\n ");
    return -1;
  }
}

const void *listGetItem(List *list, const int index){
  if((index >=0) && (index < list->size)){
    return (const void *)list->array[index];
  }else{
    return NULL;
  }
}

void listInsertItem(List *arrayList, void *newItem){

  if(arrayList == NULL){
    fprintf(stderr, "listInsertItem() -Invalid list \n");
    return;
  }
  /* House keeping - Enhance the array */
  if(arrayList->lastItemPosition + 1 == arrayList->size){
    arrayList = resizeList(arrayList, DOUBLE_THE_LIST);
    if(arrayList == NULL){
      fprintf(stderr, "insertItem() - Unable to allocate memory \n");
      exit(1);
    }
  }


  /* Insert new element - O(1) operation */
  arrayList->array[++(arrayList->lastItemPosition)] = newItem;


}

void *listDeleteItem(List *arrayList, int listIndex){

  if(arrayList == NULL){
    fprintf(stderr, "Invalid list \n");
    return NULL;
  }

  void *returnElement  = arrayList->array[listIndex];

  /* Delete operation - O(n) operation */
  for(int accumulator = listIndex; accumulator <= arrayList->lastItemPosition; accumulator++){
    arrayList->array[accumulator] = arrayList->array[accumulator + 1];
  }

  arrayList->lastItemPosition--;


  /* House keeping - Half the list */
  if(arrayList->size > INITIAL_LIST_SIZE){ /* Minimum size maintained */
    if((arrayList->lastItemPosition + 1) == ((arrayList->size)/2)){
      arrayList = resizeList(arrayList, HALF_THE_LIST);
      if(arrayList == NULL){
        fprintf(stderr, "deleteItem() - Unable to allocate memory \n");
        exit(1);
      }
    }
  }
  return returnElement; /* User must free this element*/
}


void * listDeleteLastItem(List *arrayList){
  return listDeleteItem(arrayList, arrayList->lastItemPosition);
}

void *listDeleteFirstItem(List *arrayList){
  return listDeleteItem(arrayList, FIRST_ITEM_INDEX);
}



/**************Searching & Sorting -start **************/
void *linearSearch(const void *key, List *list, size_t listSize, isEqual equal){

  if(list != NULL && (listSize > 0)){
    void ** array = list->array;
    for(int index =0; index < listSize; index++){
      if(equal(key, (array[index])) ){
        return array[index];
      }
    }
  }
  return NULL;
}

void *binarySearch(const void *key, List *list, size_t listSize, compareTo compare){
  if(list != NULL && (listSize > 0)){
    return bSearchIter(key, list->array, 0, listSize-1, compare);
    //return bSearchRecur(key, list->array, 0, listSize-1, compare);
  }
  return NULL;
}

void insertionSort(List *list, size_t listSize, isLess less){
  if(list!=NULL && (listSize > 0)){
    insSort(list->array, listSize, less);
  }
}
/**************Searching & Sorting -end **************/




/******************** Usage - end *******************/

/************* helper function - start     ********/


static void swap(void **array, int i, int j){
  void *tempPointer = array[i];
  array[i] = array[j];
  array[j] = tempPointer;
}


static void insSort(void **array, size_t listSize, isLess less){
  for(int sortedBoundaryIndex = -1; sortedBoundaryIndex < listSize; sortedBoundaryIndex++){
    /*
      -1 mean sorted pool is yet to form.
       0 mean first element is in sorted pool
    */

    for(int unSortedElementIndex = sortedBoundaryIndex + 1; unSortedElementIndex > 0; unSortedElementIndex--){
      /* Within this loop, sorted pool does not exist, as unsorted new element is being compared*/
      if(less(array[unSortedElementIndex], array[unSortedElementIndex-1])){
        swap(array, unSortedElementIndex, unSortedElementIndex-1);
      }else{
        break; //If the unsorted element is > or ==, no swap, Stable sort
      }
    }
  }

}


static void *bSearchIter(const void *key, void **array, int lowerBound, int upperBound, compareTo compare){

  int mid =0;
  while(lowerBound <= upperBound){

    mid = (lowerBound + upperBound)/2;

    if(compare(key, array[mid]) == 0){

      return array[mid];
    }else if(compare(key, array[mid]) < 0){
      upperBound = mid-1;
    }else if(compare(key, array[mid]) > 0){
      lowerBound = mid + 1;
    }
  }/* end while */

  return NULL;
}

static void *bSearchRecur(const void *key, void **array, int lowerBound, int upperBound, compareTo compare){

  if(lowerBound > upperBound) return NULL;

  int mid = (lowerBound + upperBound)/2;

  if(compare(key, array[mid]) == 0){

    return array[mid];
  }else if(compare(key, array[mid]) < 0){

    return bSearchRecur(key, array, lowerBound, mid-1, compare);
  }else { // compare() > 0

    return bSearchRecur(key, array, mid+1, upperBound, compare);
  }
}



/* resizeList() is not visible to Linker (ld) */

static List *resizeList(List *list, ListResizeOperation opType){

  if(opType == DOUBLE_THE_LIST){

    list->array = realloc(list->array, 2*(list->size)*sizeof(void *));
    if(list->array == NULL){ return NULL; }
    list->lastItemPosition = list->lastItemPosition;;
    list->size = 2*(list->size);
  }else if(opType == HALF_THE_LIST){

    list->array = realloc(list->array, ((list->size)/2)*sizeof(void *));
    if(list->array == NULL){ return NULL; }
    list->lastItemPosition = list->lastItemPosition;
    list->size = (list->size)/2;
  }

  return list;
}

/************* helper function - end     *************/

#endif

---

который выполняет сортировку вставки, но ниже кода пользователя,

/************************* testList.c *****************/
#include"list/list.h"
#include<time.h>
#include<stdlib.h>


bool equal (const void * key, const void *item){
  if( *((int *)key) == *((int *)item) ){
    return true;
  }else{
    return false;
  }
}

bool less (const void * key, const void *item){
  if( *((int *)key) < *((int *)item) ){
    return true;
  }else{
    return false;
  }
}


int compare(const void *key, const void *item){
  if( *((int *)key) == *((int *)item) ){
    return 0;
  }else if((int *)key < (int *)item){
    return -1;
  }else{
    return 1;
  }
}

int main(void){
  // Comments in the below, how do I formally convey to user ?
  List *arrayList = createList();
  int *item = NULL;
  srand(time(NULL));
  for(int input = 10; input > 0; input--){
    item = malloc(sizeof(int));
    *item = rand();
    listInsertItem(arrayList, item);
  }

  item = (int  *)listGetItem(arrayList, 0); // Returns (const void *)
  printf("First item: %d\n", *item);

  printf("\nSize of list: %d\n", listGetSize(arrayList));

  int *item1 = listDeleteItem(arrayList, 3);
  free(item1); // User's responsibility to avoid leak, after calling deleteItem()
  printf("One item deleted \n");

  printf("\nSize of list: %d\n", listGetSize(arrayList));

  printf("Item found after linear search: %d\n",*(int *)(linearSearch(item, arrayList, listGetSize(arrayList), equal)));
  printf("Item found after Binary search: %d\n",*(int *)(binarySearch(item, arrayList, listGetSize(arrayList), compare)));
  insertionSort(arrayList, listGetSize(arrayList), less);

  printf("Sorted array \n");
  for(int index =0; index < listGetSize(arrayList); index++){
    printf("Element: %d \n", *((const int *)listGetItem(arrayList, index)));
  }


  freeList(arrayList);  // User is responsible to free list, before stop using list
}

---

не печатать отсортированный массив.

Скомпилировано успешно, с инструкциями ниже,

> pwd
/home/Personal/../Computing
> `gcc -Wall -g -I. -DARRAY ./list/*.c testList.c -o testList`
./list/arrayImpl.c:240:14: warning: ‘bSearchRecur’ defined but not used [-Wunused-function]
 static void *bSearchRecur(const void *key, void **array, int lowerBound, int upperBound, compareTo compare){

---

но вывод есть,

$ ./testList.exe
First item: 2043943058

Size of list: 10
One item deleted

Size of list: 9
Item found after linear search: 2043943058
Item found after Binary search: 2043943058

Before sorting
Element: 1611124216
Element: 1315139801
Element: 642548661
Element: 1598077511
Element: 792705528
Element: 913581568
Element: 1766294466
Element: 1469344807
Element: 895523447

After sorting
Element: 1611124216
Element: 1315139801
Element: 642548661
Element: 1598077511
Element: 792705528
Element: 913581568
Element: 1766294466
Element: 1469344807
Element: 895523447

Ожидаемый результат после сортировки:

After sorting
Element: 1611124216
Element: 1315139801
Element: 642548661
Element: 1598077511
Element: 792705528
Element: 913581568
Element: 1766294466
Element: 1469344807
Element: 895523447

---

Вопрос:

Элемент не сортируется после вызова insertionSort(arrayList, listGetSize(arrayList), less);,

Как решить эту проблему? Это как-то связано с swap() указатели?

Примечание: Cygwin не помогает с GDB.

Answer 1

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

list_t *insertion_sort(list_t *list) {
    int i, j;

    for (i = 1; i < list->lastItemPosition; i++) {
        for (j = i-1; j >= 0 && int_cmp(list->array[j+1], list->array[j]); j--) {
            swap(&list->array[j], &list->array[j+1]);
        }
    }
    return list;
}

Какой внешний цикл проверяет, если array[0] в array[n-1] имеют действительные значения. Вы также можете установить lastItemPosition в 0, так как имеет смысл начинать здесь, а не -1, Внутренний цикл просто проверяет, если число после j+1 больше текущего числа j и проверяет в диапазоне [i-1,0], а затем меняются оба числа.

Вот некоторые из вспомогательных функций, используемых в этом коде:

/* Just like your function */
int int_cmp(const void *a, const void *b) {
    if(*((int *)a) < *((int *)b) ){
        return 1;
    }
    return 0;
}

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

Как видно это void swap() Вы можете просто сравнить ** значения, вместо интеграции индексов i а также j в ваше сравнение.

Я решил проверить это с некоторым кодом, который я написал, и это выглядит так:

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

#define INITIAL_LIST_SIZE 50

#define MALLOC_MSG "Memory allocation"
#define REALLOC_MSG "Memory reallocation"

typedef struct {
    void **array;
    size_t lastItemPosition;
    size_t currsize;
} list_t;

list_t *create_list(void);
list_t *insert_item(list_t *list, void *item);
list_t *insertion_sort(list_t *list);
void print_array(list_t *list);
void free_list(list_t *list); 
void check_ptr(void *ptr, const char *msg);
int int_cmp(const void *a, const void *b);
void swap(void **a, void **b);

int main(void) {
    list_t *list;
    int i, n, *item;

    list = create_list();

    printf("Enter n: ");
    if (scanf("%d", &n) != 1 || n < 1) {
        printf("Invalid n value.\n");
        exit(EXIT_FAILURE);
    }

    srand(time(NULL));
    for (i = 0; i < n; i++) {
        item = malloc(sizeof(*item));
        check_ptr(item, MALLOC_MSG);
        *item = rand();
        list = insert_item(list, item);
    }

    printf("Before: ");
    print_array(list);

    list = insertion_sort(list);

    printf("After: ");
    print_array(list);

    free_list(list);

    return 0;
}

void print_array(list_t *list) {
    size_t i;

    for (i = 0; i < list->lastItemPosition; i++) {
        printf("%d ", *(int*)list->array[i]);
    }
    printf("\n");
}

list_t *insertion_sort(list_t *list) {
    size_t i;
    int j;

    for (i = 1; i < list->lastItemPosition; i++) {
        for (j = i-1; j >= 0 && int_cmp(list->array[j+1], list->array[j]); j--) {
            swap(&list->array[j], &list->array[j+1]);
        }
    }
    return list;
}

list_t *insert_item(list_t *list, void *item) {
    if (!list) {
        printf("Invalid list requested.\n");
        exit(EXIT_FAILURE);
    }

    if (list->currsize == list->lastItemPosition) {
        list->currsize *=2;
        list->array = realloc(list->array, list->currsize * sizeof(*(list->array)));
        check_ptr(list->array, REALLOC_MSG);
    }

    list->array[list->lastItemPosition++] = item;
    return list;
}

list_t *create_list(void) {
    list_t *list = malloc(sizeof(*list));
    check_ptr(list, MALLOC_MSG);

    list->currsize = INITIAL_LIST_SIZE;

    list->array = malloc(list->currsize * sizeof(*(list->array)));
    check_ptr(list->array, MALLOC_MSG);

    list->lastItemPosition = 0;
    return list;
}

void free_list(list_t *list) {
    size_t i;

    for (i = 0; i < list->lastItemPosition; i++) {
        free(list->array[i]);
        list->array[i] = NULL;
    }
    free(list->array);
    list->array = NULL;

    free(list);
    list = NULL;
}

int int_cmp(const void *a, const void *b) {
    if(*((int *)a) < *((int *)b) ){
        return 1;
    }
    return 0;
}

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

void check_ptr(void *ptr, const char *msg) {
    if (!ptr) {
        printf("Unexpected null pointer found: %s.\n", msg);
        exit(EXIT_FAILURE);
    }
}

Примечание. Этот код, безусловно, можно улучшить, но он показывает, что функция сортировки вставками работает (насколько мне известно).

Кроме того, было бы также лучше использовать qsort, который O(logN) время выполнения в среднем, что лучше, чем вставка сортирует среднее значение O (N ^ 2).

Вот пример вывода:

Enter n: 5
Before: 593517087 518087463 1534155136 922486149 304751363
After: 304751363 518087463 593517087 922486149 1534155136

Answer 2

Внутри insSort функция у вас есть sortedBoundaryIndex типа int (подписано) начинается с -1 тогда вы сравниваете это в for состояние с listSize типа size_t (без подписи). Когда сравниваются два числа, одно со знаком и другое без знака, подписанное число интерпретируется как число без знака (еще хуже, чем меньше будет подписанное число, тем больше будет его интерпретация). Так -1 (поскольку это наименьшее отрицательное число) будет интерпретироваться как максимально возможное значение для unsigned int который 4294967295, Таким образом, цикл никогда не вводится. В любом случае это бессмысленно sortedBoundaryIndex начать с -1 потому что состояние внутреннего цикла потерпит неудачу, так sortedBoundaryIndex должен начинаться с 0,

ПРИМЕЧАНИЕ: состояние внешнего цикла должно быть sortedBoundaryIndex < listSize - 1 и не sortedBoundaryIndex < listSize потому что во внутреннем цикле вы добавляете 1 в sortedBoundaryIndex получить unSortedElementIndex и использовать его как индекс для array, так когда sortedBoundaryIndex достичь listSize - 1 затем unSortedElementIndex будет равен listSize который выходит за пределы и вызовет ошибку выполнения.

Вот моя версия insSort функция (я использовал while вместо for в качестве внутреннего цикла И конечно же, я использовал короткие имена):

static void insSort(void **array, size_t listSize, isLess less){
    for(int sbi = 0; sbi < listSize - 1; sbi++){
        int usei = sbi + 1;
        while(usei > 0 && less(array[usei], array[usei - 1])){
            swap(array, usei, usei - 1);
            usei--;
        }
    }
}