Lista ordinata con quicksort

di
ale89
il
4 risposte
A
ale89
Pochi posts
Iscritto da
ago, 2011
Messaggi:
3

Lista ordinata con quicksort

Sto cercando di modificare il quicksort per fargli ordinare i numeri contenuti in una lista doppiamente collegata...qualcuno sa dirmi come modificare il seguente codice in tal senso?
Scusatemi se ho scritto qualche corbelleria.
Grazie 

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

struct node 
{
       int value;
       struct node * prev_ptr;
       struct node * next_ptr;
};

struct list 
{
       struct node * head;
       struct node * tail;
};

void swap_elements( struct node  **ptr1, struct node **ptr2 );
struct list *quicksort_r( struct list *ptr );
struct node *partition( struct list *ptr );


int main(  )
{  
 struct node *ptr3, *ptrptr ;
 struct list *ptr;
 
int i;
int n;
    printf("\nSpecifica il numero di elementi : ");
    scanf("%d",&n);
 if(n==0)
  ptr3=NULL;
 else
{
ptr3=(struct node *)malloc(sizeof(struct node));
printf( "\nInserisci il 1o elemento : ");
scanf("%d",&ptr3->value);
ptrptr=ptr3;
ptr3->prev_ptr=NULL;
for(i=2;i<=n;i++)
   {
   ptrptr->next_ptr=(struct node *)malloc(sizeof(struct node));
   ptrptr->next_ptr->prev_ptr=ptrptr;
   ptrptr=ptrptr->next_ptr;
   printf("\nInserisci il %do elemento : ",i);
   scanf("%d", &ptrptr->value);
   }; 
ptrptr->next_ptr=NULL;
};
  
  ptr->head=ptr3;
  ptr->tail=ptrptr;  
  
  quicksort_r( ptr );
  
  printf( "\nLista ordinata :  " );
 while(ptr->head!=NULL){
  printf( "%d ",ptr->head->value );
  ptr->head=ptr->head->next_ptr;
  }
  printf("\n\n");
  
  system( "PAUSE" );	
  return 0;
}

struct list *quicksort_r( struct list * ptr ) 

{
    struct node *tmp_ptr , *x , *y ;
         tmp_ptr = partition( ptr );
         x=tmp_ptr->prev_ptr;
         y=tmp_ptr->next_ptr;
        {while (x->value<=tmp_ptr->value && x->prev_ptr != NULL){
               x=x->prev_ptr;
               ptr->head=x;};
         ptr->tail=tmp_ptr->prev_ptr;
         quicksort_r( ptr );}
        {while (y->value>tmp_ptr->value && y->next_ptr != NULL){
               y=y->next_ptr;
               ptr->tail=y;};
         ptr->head=tmp_ptr->next_ptr;
         quicksort_r( ptr );}
    return (ptr);
}

struct node *partition( struct list *ptr  ) 

{
    int pivot;
    struct node **ptr1;
    struct node  **ptr2;

    pivot = ptr->head->value;
    *ptr1=ptr->head;
    *ptr2=ptr->tail;
    

    while ( *ptr1!=*ptr2 ) 
          {
           while ( (*ptr2)->value > pivot && *ptr1!=*ptr2 ) 
                 {
                 (*ptr2)=(*ptr2)->prev_ptr;
                 } 
           if    ( *ptr1!=*ptr2 ) 
                 {
                    do 
                       {
                       *ptr1=(*ptr1)->next_ptr;
                       
                       }
                    while ( (*ptr1)->value <= pivot && *ptr1!=*ptr2);
                    swap_elements(ptr1 , ptr2);
                 }
          }

    *ptr1=ptr->head;
    swap_elements(ptr1,ptr2);
    return (*ptr1);
}


void swap_elements( struct node  **ptr1, struct node **ptr2 ) 

{
     int tmp;
     tmp = (*ptr1)->value;
     (*ptr1)->value = (*ptr2)->value;
     (*ptr2)->value = tmp;
}

4 Risposte

  • I
    ixamit
    Molto attivo
    Iscritto da
    ott, 2009
    Messaggi:
    1027

    Re: Lista ordinata con quicksort

    Perchè una scelta divide et impera invece di un sort più consono alle liste quale un bubble o un insertion sort?
  • A
    ale89
    Pochi posts
    Iscritto da
    ago, 2011
    Messaggi:
    3

    Re: Lista ordinata con quicksort

    Sto preparando un esame universitario di C e per far ciò svolgo gli esercizi contenuti nei precedenti esami. Mi sono bloccato su questo e vorrei capire dove sbaglio. Grazie.
  • I
    ixamit
    Molto attivo
    Iscritto da
    ott, 2009
    Messaggi:
    1027

    Re: Lista ordinata con quicksort

    
void _quicksort(struct node *left, struct node *right)
{
  struct node *start,*current,*sav_current; 
  int value;

  if (left==right)  return;

  start=left;
  current=start->next;
  for (;;)
  {
    if (start->value < current->value)
    {
      value=current->value;
      current->value=start->value;
      start->value=value;
    }   
    if (current==right)    break;
    current=current->next;
  }

  value=left->value;
  left->value=current->value;
  current->value=value;

  sav_current = current;
  current=current->prev;
  if (current)
  {
    if ((left->prev != current) && (current->next != left))
      _quicksort(left, current);
  }
  current = sav_current;
  current = current->next;
  if (current != NULL)
  {
    if ((current->prev != right) && (right->next != current))
      _quicksort(current, right);
  }
}
    http://www.iprogrammatori.it/forum-programmazione/cplusplus/lettura-file-con-allocazione-una-lista-t11458.html#p8471298
    troppo incomprensibile la tua scrittura sry.
  • A
    ale89
    Pochi posts
    Iscritto da
    ago, 2011
    Messaggi:
    3

    Re: Lista ordinata con quicksort

    Grazie. Così il programma funziona. Il problema è che l'esercizio richiede di usare pure una funzione partition che prende in ingresso un puntatore di tipo struct list e restituisce la posizione del pivot; inoltre viene richiesto di utilizzare la funzione swap tra due doppi puntatori di tipo struct node.
    struct list
    {
    struct node *head
    struct node *tail
    }
    Grazie per eventuali chiarimenti e/o modifiche.
Devi accedere o registrarti per scrivere nel forum
4 risposte