Scribd
Upload
59 views

Prog Tutorial5 PDF

This document provides details for Tutorial 5 assignments on searching, hashing, and sorting algorithms: 1. Write a program to compare the efficiency of binary search, sequential search, and random search algorithms on arrays of varying sizes. 2. Implement a random search algorithm on an array and compare its efficiency to binary and sequential search. Ensure each random location is unique. 3. Write a program to test mergesort on a linked list sorted first by gender then name. 4. Write a program demonstrating quicksort on a linked list that allows the user to choose sorting by name or metric number. 5. Implement an integer sorting algorithm that inserts elements into arrays based on their value and concatenates the

Uploaded by

Mazen Jamal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
59 views

Prog Tutorial5 PDF

This document provides details for Tutorial 5 assignments on searching, hashing, and sorting algorithms: 1. Write a program to compare the efficiency of binary search, sequential search, and random search algorithms on arrays of varying sizes. 2. Implement a random search algorithm on an array and compare its efficiency to binary and sequential search. Ensure each random location is unique. 3. Write a program to test mergesort on a linked list sorted first by gender then name. 4. Write a program demonstrating quicksort on a linked list that allows the user to choose sorting by name or metric number. 5. Implement an integer sorting algorithm that inserts elements into arrays based on their value and concatenates the

Uploaded by

Mazen Jamal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

KIE1008 (Programming Tutorial) Session 2016/2017 (Semester 2)

Tutorial 5: Searching, Hashing and Sorting Algorithms

1. Write a program to find the number of comparisons using binary search and sequential search
algorithms as follows:
Suppose the list contains 100 elements:
a. Use a random number generator to fill the list for number from 1 to 200 without
duplication.
b. Use any sorting algorithm to sort the list.
c. Print out the number of comparisons required to find (or not find) every element from 1 to
200.
d. Calculate the average number of searches for each algorithm.
e. Repeat (a) to (d) 20 times to obtain the average of the average.
2. Write a program to implement a type of searching algorithm called random searching. Consider
an array of size N, at each search, a random location in the array is chosen and compared with the
‘key’, if it is found, the program will report that the element is found. Otherwise, another random
location is then chosen to compare. This is done until the element is found, or the stopping criteria
is fulfilled. What is the stopping criteria? Also, it is important to ensure that each random location
chosen has not been chosen previously. Write a main to demonstrate the code.
Compare the efficiency of this search algorithm with sequential and binary search.
3. Write a program to test mergesort for a linked list of object class Person, which contains data
member string name, and char gender. The sorting is first according to gender (F then
M) then name (A to Z).
4. Write a program to demonstrate quicksort for a linked list object class Student, which contains
data member string name and string metric. Allow the user to choose to sort according
to name or metric number (metric).
5. Write a program to implement the following sorting algorithm for integers:
sortX(arr1[], n)
1) Create n empty arrays, arr2[].
2) For every element in arr1, insert arr1[i] into
arr2[n*arr1[i]]
3) Sort every arr2 using insertion sort.
4) Concatenate all sorted arr2.

The diagram shows how this algorithm works.


---END---

You might also like