Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Bubble Sort O(N2) O(N2) O(N2)
- void bubbleSort( Comparable[] stuff ){
- for(int i=0; i<stuff.length-1; i++){ //two for loops
- for(int j=0; j<stuff.length-1; j++){
- if(stuff[ j].compareTo(stuff[ j+1]) > 0 ){
- Comparable temp = stuff[ j]; //lots of swaps
- stuff[ j] = stuff [ j+1];
- stuff [ j+1] = temp;
- }
- }
- }
- }
- Selection Sort O(N2) O(N2) O(N2)
- void selectionSort( int[] ray ){
- for(int i=0; i< ray.length-1; i++){
- int min = i;
- for(int j = i+1; j< ray.length; j++)
- {
- if(ray[j] < ray[min])
- min = j; //find location of smallest
- }
- if( min != i) {
- int temp = ray[min];
- ray[min] = ray[i];
- ray[i] = temp; //put smallest in pos i
- }
- }
- }
- Selection Sort with Objects
- public void selSort(Comparable[] stuff){
- for(int i=0;i<stuff.length-1;i++)
- {
- int spot=i;
- for(int j=i;j<stuff.length;j++){
- if(stuff[j].compareTo(stuff[spot])>0)
- spot=j;
- }
- if(spot==i) continue;
- Comparable save=stuff[i];
- stuff[i]=stuff[spot];
- stuff[spot]=save;
- }
- }
- Insertion Sort O(N) (@) O(N2) O(N2)
- void insertionSort( int[] stuff)
- {
- for (int i=1; i< stuff.length; ++i)
- {
- int val = stuff[i];
- int j=i;
- while(j>0&&val<stuff[j-1]){
- stuff[j]=stuff[j-1];
- j--;
- }
- stuff[j]=val;
- }
- }
- Insertion Sort with Objects
- void insertionSort( Comparable[] stuff){
- for (int i=1; i< stuff.length; ++i){
- int bot=0, top=i-1;
- while (bot<=top){
- int mid=(bot+top)/2;
- if (stuff[mid].compareTo(stuff[ i ])<0)
- bot=mid+1;
- else top=mid-1;
- }
- Comparable temp= stuff[i];
- for (int j=i; j>bot; --j)
- stuff[ j]= stuff[ j-1];
- stuff[bot]=temp;
- }
- }
- Quick Sort O(N log2 N ) O(N log2 N ) O(N2) (@)
- void quickSort(Comparable[] stuff, int low, int high)
- {
- if (low < high)
- {
- int spot = partition(stuff, low, high);
- quickSort(stuff, low, spot); // has 2 recursion method calls
- quickSort(stuff, spot+1, high);
- }
- }
- int partition(Comparable[] stuff, int low, int high)
- {
- Comparable pivot = stuff[low];
- int bot = low-1;
- int top = high+1;
- while(bot<top) {
- while (stuff[--top].compareTo(pivot) > 0);
- while (stuff[++bot].compareTo(pivot) < 0);
- if(bot >= top)
- return top;
- Comparable temp = stuff[bot];
- stuff[bot] = stuff[top];
- stuff[top] = temp;
- }
- }
- Merge Sort O(N log2 N ) O(N log2 N ) O(N log2 N )
- void mergeSort(Comparable[] stuff, int front, int back)
- {
- int mid = (front+back)/2;
- if(mid==front) return;
- mergeSort(stuff, front, mid); // has 3 recursive methods
- mergeSort(stuff, mid, back);
- merge(stuff, front, back);
- }
- void merge(Comparable[] stuff, int front, int back)
- {
- Comparable[] temp = new Comparable[back-front];
- int i = front, j = (front+back)/2, k =0, mid =j;
- while( i<mid && j<back) {
- if(stuff[i].compareTo(stuff[j])<0)
- temp[k++]= stuff[i++];
- else
- temp[k++]= stuff[j++];
- }
- while(i<mid)
- temp[k++]= stuff[i++];
- while(j<back)
- temp[k++]= stuff[j++];
- for(i = 0; i<back-front; ++i)
- stuff[front+i]=temp[i];
- }
- Binary Search O(1) O( log2 N ) O( log2 N )
- int binarySearch (int [] stuff, int val )
- {
- int bot= 0, top = stuff.length-1;
- while(bot<=top)
- {
- int middle = (bot + top) / 2;
- if (stuff[middle] == val) return middle;
- else
- if (stuff[middle] > val)
- top = middle-1;
- else
- bot = middle+1;
- }
- return -1;
- }
- Linear/Sequential Search O(1) O(N) O(N)
- Binary Search O(1) O( log2 N ) O( log2 N )
- Selection Sort O(N2) O(N2) O(N2)
- Bubble Sort O(N2) O(N2) O(N2)
- Insertion Sort O(N) (@) O(N2) O(N2)
- Merge Sort O(N log2 N ) O(N log2 N ) O(N log2 N )
- QuickSort O(N log2 N ) O(N log2 N ) O(N2) (@)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement