На основе вашего кода функция qsort отлично подходит даже для раздела, который немного сложно понять! Я думаю, ваша проблема связана с функцией обмена! Вот рабочий код, который использует простую для понимания реализации функции распределения:
void swap(int *a, int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
/* the aim of the partition is to return the subscript of the exact */
/* position of the pivot when it is sorted */
// the low variable is used to point to the position of the next lowest element
int partition(int arr[], int first, int last)
{
int pivot = arr[last]; // changed the pivot
int low = first;
int i = first; // changed
while(i <= last-1){// or you can do for(i=first;i<last;i++)
if(arr[i] < pivot){
swap(&arr[i], &arr[low]);
low++;
}
i++;
}
swap(&arr[last], &arr[low]);
// after finishing putting all the lower element than the pivot
// It's time to put the pivot into its place and return its position
return low;
}
void quick_sort(int arr[], int first, int last)
{
int pivot_pos;
if(first < last){
pivot_pos = partition(arr, first, last);
quick_sort(arr, first, pivot_pos-1);
quick_sort(arr, pivot_pos+1, last);
}
}
Чтобы протестировать программу, которую вы можете использовать основную функцию ниже
int main(int argc, char *argv[])
{
int tab[]={4,53,5,6,7,1};
quick_sort(tab,0,5);
int i=0;
for (i=0;i<6;i++)
{
printf(" %d ",tab[i]);
}
printf("\n");
return 0;
}
он будет генерировать отсортированный массив
1 4 5 6 7 53
Если вы хотите увидеть, что произошло именно здесь полный код :)
#include <stdio.h>
void affiche(int *p,int size);
void swap(int *p, int a, int b)
{
int temp=p[a];
p[a]=p[b];
p[b]=temp;
}
int partition(int *p, int start, int end)
{
int pindex=start;
int pivot=p[end];
int i=0;
for (i=start;i<=end-1;i++)
{
if (p[i]<pivot)
{
printf("swap p[%d] and p[%d] pivot %d\n",i,pindex,pivot);
swap(p,i,pindex);
affiche(p,7);
pindex++;
}
}
printf("==>swap p[%d] and p[%d] pivot %d\n",pindex,end,pivot);
swap(p,pindex,end);
return pindex;
}
void quicksort(int *p,int a,int b)
{
if (a<b)
{
affiche(p,7);
int pindex=partition(p,a,b);
quicksort(p,a,pindex-1);
quicksort(p,pindex+1,b);
}
}
void affiche(int *p,int size)
{
int i=0;
for (i=0;i<size;i++)
{
printf(" %d ",p[i]);
}
printf("\n");
}
int main(int argc, char *argv[])
{
int tab[]={7,2,4,8,4,0,4};
affiche(tab,7);
quicksort(tab,0,6);
affiche(tab,7);
return 0;
}
Опишите свою проблему четко. Не отправляйте код и ожидайте, что люди исправит его для вас. – ale64bit
почему вы отметили как c, так и C++? btw я могу скомпилировать его! – chouaib
Возможно, вы захотите просмотреть [Quicksort: Выбор стержня] (http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot/164183#164183), хотя вы можете обнаружить, что немного до сложного (или сложнее, чем вам нужно). Какую диагностическую печать вы сделали? Вы проверили значения элемента раздела и последнего и первого и т. Д.? Вы не указали код для 'swap()'; вы знаете, работает ли это правильно? –