1.2 Tutorial 11

intro-to-computer-science-gtiit-tutorial-11-2024.pdf

1. Define a function

   int binary_search(int seq[], int size, int elem)
   

   that performs a binary search of elem​ in an ordered integer array seq​. The result value of this function should be a value i​ where elem == seq[i]​ or -1​ if elem​ doesn’t belong to seq​.

   ‍#include <stdio.h>
   
   int bin_search(int seq[], int start, int end, int elem) {
       if (start > end) {
           return -1;
       }
       int mid = (start + end) / 2;
       if (seq[mid] == elem) {
           return mid;
       } else if (seq[mid] > elem) {
           return bin_search(seq, start, mid-1, elem);
       } else {
           return bin_search(seq, mid+1, end, elem);
       }
   }
   
   int binary_search(int seq[], int size, int elem) {
       return bin_search(seq, 0, size-1, elem);
   }
   

   #include <stdio.h>
   
   int binary_search(int seq[], int size, int element) {
       int start = 0;
       int end = size;
       int position = -1;
       int mid = (start + end) / 2;
       while(position == -1 && start <= end) {
           if(element == seq[mid]) {
               position = mid;
               return position;
           }
           if(element < seq[mid])
               end = mid - 1;
           if(element > seq[mid])
               start = mid + 1;
           mid = (start + end) / 2;
       }
       return position;
   }
   
   int main() {
       int seq[5]={0,1,2,3,4};
       printf("%d", binary_search(seq, 5, 2));
   }
   

2. Define a function

   void insertion_sort(int seq[], int size)
   

   that orders seq​ in increasing order using the insertion sort algorithm.

   ‍void swap(int *a, int *b) {
       int temp = *a;
       *a = *b;
       *b = temp;
   }
   
   void insert(int seq[], int size,int *elem) {
       for(int i = 0; i < size; i++) {
           if(seq[i] > *elem) {
               swap(&seq[i], elem);
           }
       }
   }
   
   void insertion_sort(int seq[], int size) {
       for(int i = 0; i < size - 1; i++) {
           insert(seq,i,&seq[i + 1]);
       }
   }
   

3. Define a function

   void selection_sort(int seq[], int size)
   

   This function should use the selection sort algorithm to sort seq​ in increasing order.

   #include <stdio.h>
   
   void swap(int* a, int* b) {
       int temp = *a;
       *a = *b;
       *b = temp;
   }
   
   void select(int seq[], int size, int start_position) {
       int min_position = start_position;
       for(int i = start_position + 1; i < size; i++) {
           if(seq[i] < seq[min_position])
               min_position = i;
       }
       swap(&seq[min_position], &seq[start_position]);
   }
   
   void select_sort(int seq[], int size) {
       for(int i = 0; i < size - 1; i++) {
           select(seq, size, i);
       }
   }
   
   void print(int seq[], int size) {
       for(int i = 0; i < size; i++) {
           printf("%d\n", seq[i]);
       }
   }
   
   int main() {
       int seq[9] = {24,12,64,7,4,12,56,876,432};
       select_sort(seq, 9);
       print(seq, 9);
   }
   

4. How can you modify the functions insertion_sort​ and selection_sort​ to make them order in decreasing order?

   change the condition if(seq[i] > *elem) {​ to if(seq[i] < *elem) {​

5. Implement a function

   void merge(int seq1[], int size_seq1, int seq2[], int size_seq2, int merged[])
   

   That given two increasingly ordered sequences (seq1​ and seq2​), merges them into a single increasingly ordered sequence and stores that sequence in merged​.

   void merge(int s1[], int s2[], int size_s1, int size_s2, int result[]) {
       int i_s1 = 0;
       int i_s2 = 0;
       int i_result = 0;
       while (i_s1 < size_s1 && i_s2 < size_s2) {
           if (s1[i_s1] < s2[i_s2]) {
               result[i_result] = s1[i_s1];
               i_s1++;
           } else {
               result[i_result] = s2[i_s2];
               i_s2++;
           }
           i_result++;
       }
   
       for (int i = i_s1; i < size_s1; i++) {
           result[i_result] = s1[i];
           i_result++;
       }
   
       for (int i = i_s2; i < size_s2; i++) {
           result[i_result] = s2[i];
           i_result++;
       }
   }
   

6. How can you use the merge​ function to sort a sequence?

   split half and half again