c - recursive quicksort, count swap and comparison issue -


i want compare how many swaps , comparisons (<, >, ==, !=) took bubblesort vs. quicksort function sort array of unique numbers. problem quicksort function use recursive , bit unsure how keep track of swaps comparisons. tried use pointers keep track of count unsuccessful. me?

my bubblesort:

void bubble_sort(int arr[], int max) {     int i=0, j, temp, flag;     int swap=0, comp=0;     while(1)     {         flag = 0;         (j = 0 && comp++;  j < max - - 1; j++)         {             comp++;             if (arr[j] > arr[j+1])             {                 swap++;                 /* swapping */                  temp     = arr[j];                 arr[j]   = arr[j+1];                 arr[j+1] = temp;                 flag=1;             }         }         i++;         comp++;         if (flag == 0)         {             printf("number of swaps: %d\n",swap);             printf("number of comparisons: %d \n\n",comp);             break;         }     } } 

my quicksort:

void quicksort(int arr[],int first,int last) {     int pivot,j,temp,i;      if(first<last)     {         pivot=first;         i=first;         j=last;          while(i<j)         {             while(arr[i]<=arr[pivot]&&i<last)                 i++;             while(arr[j]>arr[pivot])                 j--;             if(i<j)             {                 temp=arr[i];                 arr[i]=arr[j];                 arr[j]=temp;             }         }          temp=arr[pivot];         arr[pivot]=arr[j];         arr[j]=temp;         quicksort(arr,first,j-1);         quicksort(arr,j+1,last);      } } 

solution:

void quick_sort(int arr[],int first,int last, int *swap, int *comp) {     int pivot,j,temp,i;     if(++(*comp) && first<last)     {         pivot=first;         i=first;         j=last;          while(++(*comp) && i<j)         {             while(++(*comp) && arr[i]<=arr[pivot]&&i<last)                 i++;             while(++(*comp) && arr[j]>arr[pivot])                 j--;             if(++(*comp) && i<j)             {                 ++(*swap);                 temp=arr[i];                 arr[i]=arr[j];                 arr[j]=temp;             }         }         ++(*swap);         temp=arr[pivot];         arr[pivot]=arr[j];         arr[j]=temp;         quick_sort(arr,first,j-1, swap, comp);         quick_sort(arr,j+1,last, swap, comp);      } } 

either use global variable suggested in comments :

int _swapcount = 0; void quicksort(int arr[],int first,int last) {    ...    //whenever swap    _swapcount++; 

or take pointer int parameter:

void quicksort(int arr[],int first,int last, int* swapcount) {    ...    //whenever swap    (*swapcount)++;    //recursion    quicksort(arr,first,j-1, swapcount);    ... 

and output swapcount once top level quicksort has completed.

edit : mis-read tag c#;


Comments

Popular posts from this blog

php - failed to open stream: HTTP request failed! HTTP/1.0 400 Bad Request -

java - How to filter a backspace keyboard input -

java - Show Soft Keyboard when EditText Appears -