Сегментация C quicksort

Question

Я хочу написать код быстрой сортировки на языке c, компилятор жалуется на «Ошибка сегментации (сброшено ядро)», когда я пытаюсь запустить этот код.Я не могу найти, где проблема.Может ли кто-нибудь помочь мне найти проблему?Спасибо.

#include <stdio.h>

void swap(int *m,int *n)
{
  int t;
  t = *m;
  *m = *n;
  *n = t;
}

int partition(int *a,int lo,int hi)
{
  int pivot = a[hi];
  int i = lo;
  for(int j = lo;j < hi;j++)
    {
      if(a[j] < pivot)
    {
      //swap(&a[i],&a[j]);
      int t = a[i];
      a[i] = a[j];
      a[j] = t;
      i++;
    }
    }
  // swap(&a[i],&a[hi]);
  int t = a[hi];
  a[hi] = a[i];
  a[i] = t;
  return i;
}

void quicksort(int *a,int lo,int hi)
{
  if(lo < hi)
    {
      int p = partition(a,lo,hi);
      quicksort(a,lo,p);
      quicksort(a,p+1,hi);
    }
}

int main(void)
{
  int a[10] = {3,4,6,7,5,8,9,2,1,0};
  quicksort(a,0,9);
  for(int i = 0;i < 10;i++)
    printf("%d ",a[i]);
  return 0;
}

Answer 1

Ну, похоже, вы сделали простую ошибку, понимая быструю сортировку.

Дело в том, что вы помещаете элемент pivot в правильную позицию внутри массива при вызове partition().

Что я имею в видусказать, рассматривать элементы изначально внутри массива как

[3, 4, 6, 7, 5, 8, 9, 2, 1, 4 ]

Теперьпосле вызова partition() массив должен выглядеть следующим образом (учтите, что вы выбрали последний элемент в качестве основного элемента, отмеченного жирным шрифтом выше)

[3, 2, 1, 4 , 5, 8, 9, 4, 6, 7]

Теперь массив нужно разделить на три части

[3, 2, 1] [ 4 ][5, 8, 9, 4, 6, 7]

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

То, что вы сделали, считается только двумя частями после partition()

[3, 2, 1, 4 ] [5, 8, 9, 4, 6, 7]

Теперь для [3, 2, 1, 4 ], когда вы звоните quicksort(), он падает в бесконечной рекурсии.

Я изменил часть ниже, надеюсь, это поможет

void quicksort(int *a,int lo,int hi)
{
  if(lo < hi)
    {
      int p = partition(a,lo,hi);
      quicksort(a,lo,p-1);
      quicksort(a,p+1,hi);
    }
}