Sorting Algorithms

ramthegreatcv Thu Jun 04, 2009 4:00 am

Running Codes of all popular sorting algorithms

ramthegreatcv Thu Jun 04, 2009 4:01 am

Code:: #include<stdio.h> #include<stdlib.h> int partition(int b[],int x,int y) { int i=x-1,j,tmp,temp; int pivot=b[y]; for(j=x;j<y;++j) { if(b[j] <= pivot) { i++; temp=b[i];b[i]=b[j];b[j]=temp; } } i++; tmp=b[i];b[i]=b[y];b[y]=tmp; return(i); } void quicksort(int a[],int p,int r) { int q; if(p < r) { q=partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); } } main() { int arr[10],i,i1,k,beg=0,end=9; printf("\nenter the elements--"); for(i=0;i<10;i++) scanf("%d",&arr[i]); //printf("scanf successsful\n"); printf("\nthe elements are--\n"); for(i1=0;i1<10;i1++) printf("%d\t",arr[i1]); printf("print ho gya\n"); quicksort(arr,beg,end); printf("\nthe sorted array is---\n"); for(k=0;k<10;k++) printf("%d\t",arr[k]); return 0; }

ramthegreatcv Fri Jun 05, 2009 1:54 am

Code:: #include<iostream> #include<algorithm> #include<stdio.h> #define LEFT(x) (2*(x)) #define PARENT(x) ((x)/2) #define RIGHT(x) ((2*(x))+1) using namespace std; void swap(int &a,int &b){ int t; t=a;a=b;b=t; } void maxHeapify(int arr[],int i,int heapsize){ int l = LEFT(i); int r = RIGHT(i); int largest; if(l<=heapsize && arr[l]>arr[i]) largest = l; else largest = i; if(r<=heapsize && arr[r]>arr[largest]) largest = r; if(largest != i){ swap(arr[i],arr[largest]); maxHeapify(arr,largest,heapsize); } } void buildMaxHeap(int arr[],int heapsize){ for(int i=heapsize/2;i>=1;i--) maxHeapify(arr,i,heapsize); } void heapSort(int arr[],int end){ int heapsize = end; buildMaxHeap(arr,heapsize); for(int i=end;i>=2;i--){ //cout<<arr[1]; swap(arr[1],arr[i]); heapsize--; maxHeapify(arr,1,heapsize); } } int main() { int arr[11]={0,0,2,3,4,5,9,8,7,6,1},i,i1,k; int beg=0,end=10; arr[0] = 0;//dummy entry printf("\nthe elements are--\n"); for(i1=1;i1<=10;i1++) printf("%d\t",arr[i1]); heapSort(arr,end); printf("\nthe sorted array is---\n"); for(k=1;k<=10;k++) printf("%d\t",arr[k]); return 0; }

Admin Mon Jun 22, 2009 7:16 pm

how will u sort a stack without an auxiliary stack ?
HINTS:
recursion is allowed
very similar to the code for reversing the stack

Answer at:
https://mockers.forumotion.com/ds-f2/stacks-the-ignored-datastructure-t101.htm#416

ramthegreatcv Wed Aug 05, 2009 9:24 pm

merge sort is the best method to sort linked list.
here is an implementation:

Code:: #include<iostream> #include<list> using namespace std; list<int> L; void print(){ list<int>::iterator i = L.begin(); while(i != L.end()){ cout<<*i; i++; } cout<<endl; } list<int> merge(list<int> left,list<int> right){ list<int> result; list<int>::iterator lItr = left.begin(); list<int>::iterator rItr = right.begin(); while (lItr != left.end() && rItr != right.end()){ if (*lItr < *rItr){ result.push_back(*lItr); lItr ++; } else{ result.push_back(*rItr); rItr ++; } } if (lItr != left.end()){ while(lItr != left.end()){ result.push_back(*lItr); lItr++; } } else { while(rItr != right.end()){ result.push_back(*rItr); rItr++; } } return result; } list<int> mergeSort(list<int> m){ list<int> left, right, result; list<int>::iterator itr = m.begin();; if (m.size() <= 1) return m; int middle = m.size() / 2; /*for each x in m up to middle add x to left */ while(middle-- != 0){ left.push_back(*itr); itr++; } /*for each x in m after middle add x to right */ while(itr != m.end()){ right.push_back(*itr); itr++; } left = mergeSort(left); right = mergeSort(right); result = merge(left, right); return result; } int main(){ L.push_back(4); L.push_back(1); L.push_back(3); L.push_back(4); L.push_back(1); L.push_back(3); L.push_back(2); L.push_back(2); print(); L = mergeSort(L); print(); }

Sponsored content

QuickSort