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
Post a Comment