# Sorting and Searching Algorithms

Email
 Submitted on: 1/4/2015 3:49:00 PM By: Matt Fowler (from psc cd) Level: Advanced User Rating: By 4 Users Compatibility: C++ (general), Borland C++ Views: 1816

This code contains all the common sorting/searching algorithms, all with comments. The program fills an array of user specified size with random numbers, then the program times the sorting and searching algorithms (picked at the user's discretion).

### INCLUDE files:

Can't Copy and Paste this?
 ```//************************************** //INCLUDE files for :Sorting and Searching Algorithms //************************************** #include #include #include #include ```
code:
Can't Copy and Paste this?
 ``` //************************************** // Name: Sorting and Searching Algorithms // Description:This code contains all the common sorting/searching algorithms, all with comments. The program fills an array of user specified size with random numbers, then the program times the sorting and searching algorithms (picked at the user's discretion). // By: Matt Fowler (from psc cd) //************************************** #include #include #include #include /***************************************/ /* Sorting and Searching Algorighms*/ /* By Matt Fowler */ /* E-mail: philosopher150@yahoo.com*/ /*Use this code freely */ /***************************************/ void fillArray(int *a); void resizeArray(int nSize, int *a); int round(float toround); /* sorting algorithms */ void QuickSort(int *a, int left, int right); int Partition(int *a, int l, int r); void MergeSort(int *a, int l, int r); void merge(int *a, int l, int m, int r); void ShellSort(int *a); void SelectionSort(int *a); void InsertionSort(int *a); void BubbleSort(int *a); /* searching algorithms */ /* All return index of element containing key */ /* Else return -1 */ int binary(int *a, int key); int interpolate(int *a, int key); int linear(int *a, int key); int ternary(int *a, int key); int ARR_MAX, passes; int main() { int *arr, choice, foundAt, searchFor; time_t start, end; float dif; cout<<"Common Searching/Sorting Algorithms"<>ARR_MAX; arr = new int[ARR_MAX]; cout<<"Program is now generating random elements from 0 to 1000."<>choice; cout<>choice; cout<>searchFor; if((choice>1000) || (choice <0)) cout<<"Enter a valid number!"< -1) cout<<"Found at element "< -1) cout<<"Found at element "< -1) cout<<"Found at element "< -1) cout<<"Found at element "<= j) break; temp = a[i]; a[i] = a[j]; a[j] = temp; } temp = a[i]; a[i] = a[r]; a[r] = temp; return i; } /* Merge sort is a very efficent algorithm. It works by splitting the array into many parts (recursively), sorting those parts, and then joining them all back together (merging). This algorithm has a run time efficency of O(N log N). */ void MergeSort(int *a, int l, int r) { if(r<=l) return; int m = (r+l)/2; MergeSort(a, l , m); MergeSort(a, m+1, r); merge(a, l, m, r); } void merge(int *a, int l, int m, int r) { int i, j; static int *copy = new int[ARR_MAX]; for(i = m+1; i > l; i--) copy[i-1] = a[i-1]; for(j = m; j < r; j++) copy[r+m-j] = a[j+1]; for(int k = l; k <= r; k++) if(copy[j] < copy[i]) a[k] = copy[j--]; else a[k] = copy[i++]; } /* The problem with insertion sort is that it checks data elements that are right next to each other. This is what mainly slows down thw algorithm. Shell sort solves this. It uses an increment sequence to check elements of the array that are in different parts. Then preforms a standard insertion sort. The run time efficency of shellsort is unknown, but it is theorized to be along the lines of O(N(log N)^2). But no one is able to say for sure */ void ShellSort(int *a) { int z, l = 0, r = ARR_MAX-1; /* set up increment sequence reccomended by Donald Knuth */ /* 1 4 13 40 121 364 ... */ for(z = 1; z <= (r+1)/9; z = 3*z+1); for(; z>0; z/=3) for(int i = l+z; i<=r; i++) { int j = i; int v = a[i]; while(j>=l+z && v < a[j-z]) { a[j] = a[j-z]; j-=z; } a[j] = v; } } /* Selection sort works by finding the smallest number in the array and then swapping it with the number in the next position. It is very slow, and shouldn't be used with large lists. It has a run time efficency of O(N^2) */ void SelectionSort(int *a) { int len = ARR_MAX-1; int cs, cp, temp, il; for(cp = 0; cp<=len; cp++) { cs = cp; for(il = cp; il<=len; il++) { if(a[il] 0; i--) { if(a[i]a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } /* Search Algorithms. These will only work on SORTED data (exc linear) */ /* binary works by splitting the array in two. If the number in the middle is less than the key, it redividies up the right, then it continues the search in the same fashion. Otherwise, it redivides up the left. This is a fast algorithm and has a run time efficency of O(lg N) */ int binary(int *a, int key) { int midval, left, right; left = 0; right = ARR_MAX-1; passes = 0; while(left<=right) { passes++; midval = (left+right)/2; if(a[midval] == key) return midval; else if(a[midval]key) right = thirds - 1; if(a[twothirds]== key) return twothirds; else if(a[twothirds]key) right = twothirds - 1; } return -1; } /* linear is the brute force approach. It starts from the begenning, checking every element of the array. Its the slowest search, however, its the only search that can be used on random data. But if you've ordered data, it dosen't make sense to use this. It has a runtime efficency of O(N) */ int linear(int *a, int key) { int len = ARR_MAX+1; resizeArray(len, a); a[len-1] = key; /* insert key in the end, for efficency */ int i = 0; while(a[i]!=key) /* with key in end while loop does less comparisions*/ i++; /* saving a bit of time */ if(i == len-1) return -1; else return i; } /* Rounding. To solve some integer math problems in interpolation */ int round(float toround) { int nondec = toround; float test = toround - nondec; if(test < .5) return floor(toround); else return ceil(toround); } /* Somewhat like a binary search, except instead of dividing the array in two, the function solves a proportion to determine where the data should be. Kinda like figuring out the data's equation. This is a VERY fast algorithm, but it can be clunky. If the data isn't randomly distributed things can get screwy, also, things can mess up if the key is near the end. Run time efficency is about O(log N) (but with a VERY small base) */ int interpolate(int *a, int key) { float middle, tostart; int left = 0, right = ARR_MAX-1; int start; passes = 0; while(left<= right) { passes++; tostart = left+((key - a[left])*(right-left))/(a[right]-a[left]); start = round(tostart); if(a[start] == key) return tostart; else if(a[start]

Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

What do you think of this code (in the Advanced category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)