Question

Describe what are sorting and searching, and why are they essential in a computer science field. Give two examples when sorting and searching are necessary in designing software applications. Describe three different types of existing sorting algorithms and two types of searching algorithms. Justify, compare and contrast your choice of sorting and searching algorithms. Include one example of sorting or searching program. You may use a program you discover on the Internet as an example. Please make sure to give credits to the author of the program and cite the website where you found it.

Answer 1

Describe what are sorting and searching, and why are they essential in a computer science field.

SORTING - Arrangement in a certain order

In Computer Science, when data is in some random fashion, making it to an arranged way, will assist in improving the readability, understanding and working with the data.

SEARCHING - Check if a particular element is present in a group of elements

In Computer Science, when we have a bunch of values, we may need to check the existence of a particular value and respond accordingly.

Give two examples when sorting and searching are necessary in designing software applications.

1. For analysing students' results like finding topper among a set of students (marks must be sorted in ascending/descending order to determine the topper ), to find those who have failed in one particular subject but not another specific subject (find the students failed in particular subject, search for the same student's result in another subject to compare)

2. In library management system, the details of the books are added whenever a new book is purchased. It must be sorted in some order (like arranging according to the title of the book). When a reader requests a book, it must searched for among the list of available books.

Describe three different types of existing sorting algorithms and two types of searching algorithms.

Selection Sort:
Selection sort to arrange in ascending order finds the first minimum element and puts it in the first position, finds the second minimum element in the group and puts in the second position, finds the third minimum element and puts in the third position and so on.

Insertion Sort:
Insertion Sort works in the fashion like inserting a new card in a deck of already sorted cards. Initially, consider one value as sorted group, rest as unsorted. Then move a value from unsorted group to the sorted group. When moving check the value and place it in appropriate position. Repeat until all values are moved to the sorted group.

Merge Sort:
Merge Sort works on the idea of Dividing and Conquering. Keep dividing the entire group into two groups until each group contains only one value. Then start merging two groups into one by comparing and arranging the values during the merge.

Linear Search:
Linear Search searches in a linear fashion- sequentially one after another from the beginning to the end until the element is found. If the entire list is checked, but no match is found, it means there is no such value present.
It can search in a group of unsorted values.

Binary Search:

Binary Search searches in a group of sorted values by dividing into two. For any element in the group, when sorted in ascending order, the elements to the left are less and the elements to the right are larger. So, using this logic the search is restricted to one half by comparing with the value of search element.

Justify, compare and contrast your choice of sorting and searching algorithms.

SORTING ALGORITHM

In Selection Sort and Insertion Sort, the maximum number of comparisons made include N*N

In Merge Sort, the maximum number of comparisons include N log N independent of how the data is distributed.

So, choosing merge sort would be an ideal choice

SEARCH ALGORITHM

Linear Search is used when the elements are unsorted and binary search is used when the elements are sorted.

For Linear Search, when element is not found, a maximum of n checks are made.

For Binary Search, when element is not found, a maximum of n/2 checks are made.

Include one example of sorting or searching program.

EXAMPLE: LINEAR SEARCH

Get the values and the number to check. For every number starting from the first value, search if that is the search element. If found, print the index and position. Else, if the entire list is traversed, print element not found

-PYTHON PROGRAM

# Get the list of numbers
number=[int(i) for i in input("Enter the values").split(",")]
# Get the number to search for
num_to_check=int(input("Enter the number to check:"))
# Starting from beginning, check if that is the search element
for j in range(0,len(number)):
        # If found, print the index and position
        if(num_to_check==number[j]):
                print("Number found at index",j,"and position", j+1)
                break
#If the entire list is traversed and no match is found, print number not found
else:
        print("Number not found")

SCREENSHOT OF PROGRAM TO ASSIST IN INDENTATION

OUTPUT (SCREENSHOT)

In this example, the element is found at third check. First check made is 5 with 7, then 3 with 7 and then 7 with 7.