Quick Sort with no of camparison and swap
On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
code in C:#include<stdio.h> int comparisons=0,exchanges=0; // is x < y ? int less(int x, int y) { comparisons++; return (x < y); } // exchange a[i] and a[j] void exch(int a[] , int i, int j) { exchanges++; int swap = a[i]; a[i] = a[j]; a[j] = swap; } void quicksort(int a[] , int left, int right) { if (left <= right) { int i = left - 1; int j = right; // right is pivot element while (1) { while (less(a[++i], a[right])); // find item on left to swap while (less(a[right], a[--j])) // find item on right to swap if (j == left) break; // don't go out-of-bounds if (i >= j) break; // check if pointers cross exch(a, i, j); // swap two elements into place } exch(a, i, right); // swap with partition element quicksort(a, left, i-1); quicksort(a, i+1, right); } } int main() { int a[100],size,i; printf("Enter number of elements: "); scanf("%d",&size); printf("Enter number: \n"); for(i=0;i<size;i++) scanf("%d",&a[i]); quicksort(a, 0, size- 1); printf("Sorted list in ascending order:"); for(i=0;i<size;i++) printf(" %d",a[i]); printf("\n\n no of comparisons: %d",comparisons); printf("\n no of exchanges: %d",exchanges); return 0; }output:-
Enter number of elements: 5 Enter number: 29 21 64 20 56 Sorted list in ascending order: 20 21 29 56 64 no of comparisons: 16 no of exchanges: 6 --------------------------------
0 comments: