الگوریتم Quick Sort و Merge Sort استاد نصیری

سلام؛

از این پست می تونید کد دو تابع Quick Sort و Merge Sort رو که استاد نصیری در کلاس توضیح دادن رو دریافت کنید.

فقط یه نکته ای هست اونم این که از این به بعد تصمیم گرفتم کدهای برنامه ها رو به صورت مستقیم در سایت قرار بدم و لینک دانلود دیگه نزارم که برای شما هم کمتر مشکل پیش بیاد. ولی بازم اگه کسی از دوستان به فایل CPP این دو تابع نیاز داشت بگه که اونا رو هم آپ کنم.

الگوریتم Quick Sort:

#include<iostream> using namespace std; void quickSort(int arr[], int left, int right) { int i = left, j = right; int tmp; int pivot = arr[abs((left + right) / 2)]; /* partition */ while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } } /* recursion */ if (left < j) quickSort(arr, left, j); if (i< right) quickSort(arr, i, right); } int main(){ int arr[7]= {2,3,8,7,4,9,1}; for(int i=0;i<7;i++) cout<<arr[i]<<" " ; cout<<endl; quickSort(arr,0,6); for(int i=0;i<7;i++) cout<<arr[i]<<" " ; cout<<endl; return 0; }

الگوریتم Merge Sort:

#include<iostream> #include<stdlib.h> #include<time.h> using namespace std; //merges sorted halves into a sorted whole void merge(int A[], int p, int q, int r){ int len1 = q-p+1; //length of subarray A[p..q] int len2 = r-q; //length of subarray A[q+1..r] int left[len1]; //create left subarray int right[len2]; //create right subarray //fill left and right subarrays for(int i=0; i<len1; i++) //A[p..q] left[i] = A[p+i]; for(int j=0; j<len2; j++) //A[q+1..r] right[j] = A[q+1+j]; int i=0, j=0; //left & right subarray indices int k = p; //indice for array A while(k<=r){ //merge two sorted halves back into A, sorted if(i<len1 && j<len2){ //if i==len1 were done with left subarray, if j==len2 were done with right subarray if(left[i]<=right[j]) A[k++] = left[i++]; //merge left element into A else A[k++] = right[j++]; //merge right element into A } else if(i==len1) //were done with left subarray A[k++] = right[j++]; //insert remaining elements of right subarray into A else //were done with right subarray A[k++] = left[i++]; //insert remaining elements of left subarray into A } } //splits array A into smaller pieces void mergeSort(int A[], int p, int r){ if(p<r){ int q=(p+r)/2; //split this portion of array A in half mergeSort(A, p, q); //recursively split left half mergeSort(A, q+1, r); //recursively split right half merge(A, p, q, r); //merge sorted halves } } /*********************************************/ //now lets test merge sort int main(){ int numels=100; int arr[numels]; srand(time(NULL)); //fill arr with numel random numbers for(int i=0; i<numels; i++) arr[i]=rand()%100; //merge sort arr mergeSort(arr, 0, numels-1); //lets see if theyre sorted for(int i=0; i<numels; i++) cout<<arr[i]<<' '; cout<<endl; return(0); }