/* Input a number between 1-4: 1)Linear search 2)Binary search 3)Bubble sort 4)Selection sort */ //include necessary libraries #include #include #include #include //define functions void print_arr(int len, int arr[]); int linear_search(int len, int arr[], int num); int binary_search(int len, int arr[], int num); int bubble_sort(int len, int arr[]); int selection_sort(int len, int arr[]); int main(void) { srand(time(0)); //random seed //initialize array int len = 10; int arr[len]; //add random numbers for (int i = 0; i < len; i++) { arr[i] = rand() % 20; } int algo = 0; printf("Algorithms: \n1)Linear search\n2)Binary search\n3)Bubble sort\n4)Selection sort\nType in a number from 1-4: "); scanf("%i", &algo); if (algo < 1 || algo > 4) //invalid input { printf("Invalid input, using 4 as input...\n"); algo = 4; } print_arr(len, arr); if (algo <= 2) //if user wants to see searching algorithm { int search = rand() % 20; //search for random number printf("Searching for %i...\n\n", search); if (algo == 1) { linear_search(len, arr, search); return 0; } selection_sort(len, arr); binary_search(len, arr, search); } else if (algo == 3) { bubble_sort(len, arr); } else { selection_sort(len, arr); } return 0; } //function to print array void print_arr(int len, int arr[]) { printf("\n"); for (int i = 0; i < len; i++) { printf("[%i]", arr[i]); } printf("\n"); } //function to check if array is already sorted(for binary search) int sorted(int len, int arr[]) { for (int i = 1; i < len; i++) //notice that it starts at 1 { if (arr[i - 1] > arr[i]) //if number before is smaller than current numbers { return 0; } } return 1; } //linear search int linear_search(int len, int arr[], int num) { for (int i = 0; i < len; i++) //looping through whole array { print_arr(len, arr); printf("On position %i. Current number is %i.\n\n", i, arr[i]); if (arr[i] == num) { printf("Found %i at position %i.\n", num, i); return 1; } } printf("Done searching. %i isn't in this array.\n", num); return 0; } //binary search int binary_search(int len, int arr[], int num) { if (!(sorted(len, arr))) //if array isn't sorted yet { print_arr(len, arr); printf("Array is not sorted.\n"); return 1; } int min = 0; int max = len - 1; while (min <= max) //while we haven't searched all the numbers that are necessary { int i = ceil((max + min) / 2); //get the middle index of arr print_arr(len, arr); printf("On position %i. Current number is %i.\n", i, arr[i]); if (arr[i] == num) { printf("\nFound %i at position %i.\n", num, i); return 1; } else if (arr[i] < num) { printf("%i is smaller than %i.\n", arr[i], num); min = i + 1; //set minimum index to one greater than i } else if (arr[i] > num) { printf("%i is greater than %i.\n", arr[i], num); max = i - 1; //set maximum index to one less than i } } printf("\n\nDone searching. %i isn't in this array.\n", num); return 0; } //bubble sort int bubble_sort(int len, int arr[]) { for (int i = 0; i < len; i++) { for (int j = 0; j < len - 1; j++) { if (arr[j] > arr[j + 1]) //if number to right is smaller { int temp = arr[j]; //temporary storage printf("Swapping %i and %i...", temp, arr[j + 1]); //swap arr[j] = arr[j + 1]; arr[j + 1] = temp; print_arr(len, arr); printf("\n"); } } } printf("Done. Final array:"); print_arr(len, arr); return 1; } //selection sort int selection_sort(int len, int arr[]) { for (int i = 0; i < len; i++) { //temporary storage for number that's smaller than arr[i] int min = arr[i]; int pos = i; for (int j = i; j < len; j++) { if (arr[j] < min) //if number is smaller { //store in memory min = arr[j]; pos = j; } } printf("Swapping %i at position %i with %i at position %i...", arr[i], i, min, pos); //swap arr[pos] = arr[i]; arr[i] = min; print_arr(len, arr); printf("\n"); } printf("Done. Final array: "); print_arr(len, arr); return 1; }