Проблемы с сортировкой сортировки

Question

Это может быть не обычным делом quicksort.my. Сначала попробуйте на нем. Номера не отсортированы так, как они должны быть. Я попытался отсортировать случайный список чисел. Однако я не могу идентифицировать логические ошибки даже после строгой проверки.

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

int n; 
int *expivot; 
int *arr; 
void quicksort(); 
void display(); 
int check(); 

main() 
{ 
    int i; 
    printf("to continue press 'a' always\n"); 
    while(getch()=='a') 
    { 
     printf("Enter the length of list\n"); 
     scanf("%d",&n); 
     time_t start,end; 
     double t; 
     start=clock(); 
     arr=(int *)calloc(n,sizeof(int)); 
     expivot=(int *)calloc(n,sizeof(int)); 
     srand(time(NULL)); 
     for(i=0;i<n;i++) 
      arr[i]=rand()%RAND_MAX + 1; 
     printf("\nelements inputted are:"); 
     display(); 
     quicksort(); 
     end=clock(); 
     t=(double)(end-start)/CLOCKS_PER_SEC; 
     printf("\n\nelements sorted are:"); 
     display(); 
     printf("\ntime take is %.15lf",t); 
     free(arr); 
     free(expivot); 
    } 
} 
void quicksort() 
{ 
    int low,high,temp; 
    int pivot=rand()%n;//generate random pivot 
    int store=pivot; 
    /*location of pivot might change due to swapping,so using store to store pivot  location so as to add this to expivot list after running quickort once*/ 
    int flag=1; 
    if(expivot[pivot]==1) // checks if it's an already used pivot 
     flag=0; 
    if(flag==1) //if the pivot is unused 
    { 
     low=pivot; 
     high=pivot; 
     while(low>0 && expivot[low]==0) 
      low--; 
     if(expivot[low]==1)//i 
      low++; 
     /*decrements low to a location where a value has been set permanently and then increase by 1,if nothing is set then decrements low to zero*/ 
     /*increments high to a location where a value has been set permanently and then decrease by 1,if nothing is set then increments high to last index*/ 
     while(high<n-1 && expivot[high]==0) 
      high++; 
     if(expivot[high]==1) 
      high--; 
     while(low<high) 
     { 
      if(arr[low]>=arr[pivot] && arr[high]<=arr[pivot])//checks swap possibilty 
      { 
       if(low==pivot) //if pivot is to be swapped store new location of pivot 
        store=high; 
       else if(high==pivot) 
        store=low; 
       temp=arr[low]; 
       arr[low]=arr[high]; 
       arr[high]=temp; 
       low++; 
       high--; 
      } 
      else 
      { 
       if(arr[low]<arr[pivot]) 
        low++; 
       else if(arr[high]>arr[pivot]) 
        high--; 
      } 
     } 
     expivot[store]=1; 
     /*final location of pivot,stores info that this location has a permanent value now 
     and cannot be used as a pivot*/ 
    } 
    if(check()==1) 
     quicksort(); 
} 


int check() //checks if there are any unused pivots 
{ 
    int i; 
    for(i=0;i<n;i++) 
    { 
     if(expivot[i]==0) 
      return 1; 
    } 
    return 0; 
} 

void display() 
{ 
    int i; 
    for(i=0;i<n;i++) 
     printf("%d ",arr[i]); 
} 

Answer 1

Ваш метод:

1. Произвольно выбрать стержень из всего массива;
2. От поворота, распространите диапазон в оба направления, этот диапазон будет разделен на ось;
3. Все опорные точки будут кэшироваться в другом массиве (пункт 5);
4. Диапазон, упомянутый в пункте 2 выше, должен начинаться настолько большим, насколько это возможно, но: 1) не должен превышать диапазон целого массива; 2) не должен содержать другой стержень, если он это делает, останавливать и сжимать одну единицу;
5. Разделите диапазон на шарнир, из которого он распространяется, затем кешируйте этот стержень;
6. Если весь блок в массиве выбран как ось поворота, выполняется сортировка. Если нет, повторите, как указано выше, снова и снова.

Есть три проблемы в вашем коде:

1- "checd()" функция должна быть:

int check() //checks if there are any unused pivots 
{ 
    int flag = 0; 
    int i; 
    for(i=0;i<n;i++) 
    { 
     if(expivot[i]==0) 
      flag = 1; 
    } 
    return flag; 
} 

Вы должны проверить все члены, увидеть, если они ВСЕ удовлетворить ваши состояние, но не один из них удовлетворяют вашему состоянию.

2- При усадке диапазона убедитесь, что стержень находится между «высоким» и «низким» (ровно хорошо). Продолжайте отслеживать индекс и значение точки поворота. Петля в то время как должно быть:

//"store" is not needed, change it to "pivot", even after this code block. 
    while(low<high) 
    { 
     if(arr[low]>=arr[pivot] && arr[high]<=arr[pivot])//checks swap possibilty 
     { 
      if(low==pivot) //if pivot is to be swapped store new location of pivot 
       pivot=high; 
      else if(high==pivot) 
       pivot=low; 
      temp=arr[low]; 
      arr[low]=arr[high]; 
      arr[high]=temp; 

      ///////////////////// 
      if (low < pivot) 
       low++; 
      if (high > pivot) 
       high--; 
      ///////////////////// 
     } 
     else 
     { 
      if(arr[low]<arr[pivot]) 
       low++; 
      else if(arr[high]>arr[pivot]) 
       high--; 
     } 
    } 

3- Наконец, как только вы получите память от calloc или таНос, проверьте, если это NULL.

================================= Кроме того, вы должны убедиться, что весь блок в массиве могут быть выбраны, поскольку случайное число на компьютере в основном является псевдослучайным числом. Таким образом, возможно, на определенную длину определенную единицу нельзя выбрать навсегда.

Answer 2

Quicksort - это алгоритм Divide и Conquer. Вы не можете выполнить его без использования стеков или рекурсии.

Редактировать: функция использует рекурсию (oops!). Но это не quicksort. Если вы меняете метод стандартного алгоритма сортировки, то это не более того алгоритм.