mergesort

void mergesort( int arr[], int len)
{
  int low, mid, high, last;
  for(int i =2; i<len; i*=2){
    low =0; high =i-1;
    mid = (low+high)/2;
    while(high<len){
      merge(arr,low, mid, high);
      low += i;
      high += i;
      mid = (low+high)/2;
    }
    if( high != len-1){
    low -= i;
    mid = high-i;
    high = len-1;
    merge(arr, low, mid, high);
    }
  }

}

merge

int* mergeTwo(int arr1[], int arr2[], int len1, int len2)
{
  int j=0, k=0;
  int* newArr = malloc((len1+len2)*sizeof(int));
  int newLen = len1+len2;
  for(int i=0; i<newLen; i++){
    if(j<len1 && k<len2){
    if (arr1[j] <= arr2[k]){
              newArr[i] = arr1[j];
              j++;
    }else{
        newArr[i] = arr2[k];
        k++;
    }
    }else if(j>=len1){
      newArr[i]=arr2[k];
      k++;
    }else{
    newArr[i]=arr1[j];
    j++;
    }
  }
  return newArr;
}

stack overflow

question 2:

 #include<stdlib.h>
#include<stdio.h>
#include<assert.h>

void overflow(int n)
{
  if(n == INT_MAX){
    return;
  }
  printf("%d\n",n);
  overflow(n+1);
}


void foo(int n)
{
    int* arr = malloc(100*sizeof(int));
    assert(arr);
    for(int i=0; i<100; i++){
        arr[i] = i+n;
    }
    printf("%d\n", arr[99]);
    foo(n+1);
}

void bar(int n)
{
    int arr[100];
    for(int i=0; i<100;i++){
        arr[i] = i+n;
    }
    printf("%d\n",arr[99]);
    bar(n+1);
}

int main()
{
  bar(1);
  return 0;
}


b)

c)
using foo:

using bar:

stackoverflow

#include<limits.h>
#include<stdio.h>

void overflow(int n)
{
  if(n == INT_MAX){
    return;
  }
  printf("%d",n);
  n= overflow(n+1);
}

int main()
{
  overflow(1);
  return 0;
}

125-2-5

#include<stdio.h>

int main()
{
    int arr[] = {9,2,4,10,7,9,11,6,4,8,11,3};
    int n = 12;
  // copy the input string
  int nCpy[n],k=0, count;
    for(int i =0; i<n; i++){
        nCpy[i] = arr[i];
    }

  //creates a new array with 0s in each index
  int newArr[n];
  for(int i = 0; i<n; i++){
    newArr[i] =0;
  }

  // records the frequency of each number
  for(int i =0; i<n; i++){
    newArr[arr[i]]++;
  }

  // finds the last index before the first index with a value other than 0
  while(newArr[k]== 0){
    k++;
  }
  // records the indexes:
  for(int i =0; i<n; i++){
    if(newArr[i] != 0){
      if(i == k){
        count = 0;
    newArr[i] = count;
      } else{
        newArr[i] += count;
    count = newArr[i];
      }
    }
  }

  // arr is sorted
  for(int i=0; i<n; i++){
    arr[newArr[nCpy[i]]] = nCpy[i];
    newArr[nCpy[i]]--;
  }


  for(int i =0; i<n; i++){
    printf("%d", arr[i]);
  }
}

cmpt 125 assn 2 q2

#include<stdio.h>

void swap (int arr[], int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void ssort_down(int arr[], int n)
{
    int temp;
    for(int i=n-1; i>0; i--){
        int largest =i;
        for(int j=i-1; j>=0; j--){
            if(arr[j] > arr[largest]){
                largest =j;
            }
        }
    temp = arr[i];
    arr[i]=arr[largest];
    arr[largest]=temp;
    }
}

int max(int arr[], int start, int end)
{
    int largest;
    if(start == end){
        return end;
    }
    largest = max(arr, start+1, end);
    if(arr[start] > arr[largest]){
        largest = start;
    }
    return largest;
}

void rec_ssort(int arr[], int n)
{
    if(n==0){
        return;
    }

    int biggest = max(arr, 0, n-1);
    swap(arr,n-1, biggest);
    rec_ssort(arr, n-1);
}

int main (void)
{
    int arr[6] = {3,11,2,8,9,10};
    ssort_down(arr, 6);
//    for(int i=0; i<6; i++){
//        printf("%d", arr[i]);
//    }
    printf("%d", largest);
    return 0;
}

cmpt 125; assn 2; q2

#include<stdio.h>

void swap (int arr[], int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void ssort_down(int arr[], int n)
{
    int temp;
    for(int i=n-1; i>0; i--){
        int largest =i;
        for(int j=i-1; j>=0; j--){
            if(arr[j] > arr[largest]){
                largest =j;
            }
        }
    temp = arr[i];
    arr[i]=arr[largest];
    arr[largest]=temp;
    }
}

int max(int arr[], int start, int end)
{
    int largest;
    if(start == end){
        return end;
    }
    largest = max(arr, start+1, end);
    if(arr[start] > arr[largest]){
        largest = start;
    }
    return largest;
}

void rec_ssort(int arr[], int n)
{
    if(n==0){
        return arr[0];
    }
    largest = rec_ssort(arr,n-1);
    max(arr, 0, n)//wtf????

}

int main (void)
{
    int arr[6] = {3,11,2,8,9,10};
    int largest = max(arr,1,5);
    /*for(int i=0; i<5; i++){
        printf("%d", arr[i]);
    }*/
    printf("%d", largest);
    return 0;
}

cmpt 125 assn 2 q1

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void sorted( int arr[], int len)
{
    for(int i =0; i<len; i++){
        arr[i] = i;
    }
}

void reversed (int arr[], int len)
{
    int element = len-1;
    // numbers go backwards
    for(int i =0; i<len; i++){
        arr[i] = element;
        element--;
    }
}

void rando (int arr[], int len)
{
    srand(time(0));
    for(int i=0; i<len; i++){
        arr[i] = rand();
    }
}

void selectionSort( int arr[], int len )
{
        int temp;
        for( int i =0; i<len-1; i++){
                int smallest = i;
                for( int k=i+1; k<len; k++){
                        if(arr[k]< arr[smallest]){
                                smallest = k;
                        }
                }
                temp = arr[i];
                arr[i] = arr[smallest];
                arr[smallest] = temp;
        }
}

void insertionSort( int arr[], int len)
{
        int temp;
        for( int i=0; i<len; i++){
                temp = arr[i];
                int pos = i;
                while( pos >0 && arr[pos-1] > temp){
                        arr[pos] = arr[pos-1];
                        pos--;
                }
                arr[pos] = temp;
        }
}

int main (void)
{
    int array[80000];
    reversed(array, 80000); //insert array here
//    clock_t begin = clock(); //starts timing the sort
    selectionSort(array, 80000); //array to sort
//    clock_t end = clock();
//    double duration = (double)(end-begin)/CLOCKS_PER_SEC;
//    printf("%f", duration);
    return 0;
}