Question

Please Use your keyboard (Don't use handwriting)

CS141

I need new and unique answers, please. (Use your own words, don't copy and paste)

Q1:

Show all the steps of the following data set when it being sorted with Insertion, Selection, and Merge Sort Algorithms. Then, calculate the performance of each one of them.(Big –O Notation)

18

4

26

9

21

15

20

10

Q2:

Write a program using LinkedList and ListIterator to obtain the following statements:

1. Create a linked list named "list" with these elements: "one", "four" "three", and “five.

2. Create a List Iterator named "iter1" related to "list".

3. Add the new element "two" after the element "one"

4. Remove the element "four" and “five”

5 Display all element of the list

6. Create a new List Iterator named "iter2" related to "list", to add new elements in the second, fourth and sixth positions and to create each new element you must use the value of the current element concatenated to " and a half". The new obtained list is: [one, one and a half, two, two and a half, three, three and a half]

Output sample:

[one, four, three, five]

[one, two, three]

[one, one and a half, two, two and a half, three, three and a half]

Q3:

a) Write the java code for doing a Linear Search on the array given below.

{24,2,45,20,56,75,2,56,99,53,12}

b) What would your search method return if we asked to search for the number 2 and return it’s index position?

Answer 1

Q1:

Insertion Sort:

Step 1:

4 18 26 9 21 15 20 10 //swapping 4 from 18

Step 2:

4 18 26 9 21 15 20 10 //remaining the same as 18 is smaller than 26

Step 3:

4 9 18 26 21 15 20 10 //bringing 9 to the front of 18

Step 4:

4 9 18 21 26 15 20 10 //bringing 21 to the front of 26

Step 5:

4 9 15 18 21 26 20 10 //bringing 15 to the front of 18

Step 6:

4 9 15 18 20 21 26 10 //bringing 20 to the front of 21

Step 7:

4 9 10 15 18 20 21 26 //bringing 10 to the front of 15

Thus it takes 7 steps to sort the given list using insertion sort.

Selection Sort:

Step 1:

4 18 26 9 21 15 20 10 //reading the smallest element 4 and placing it ahead of the unsorted list

Step 2:

4 9 26 18 21 15 20 10 //reading the smallest element 9 and placing it ahead of the unsorted list

Step 3:

4 9 10 18 21 15 20 26 //reading the smallest element 10 and placing it ahead of the unsorted list

Step 4:

4 9 10 15 18 26 21 20 //reading the smallest element 15 and placing it ahead of the unsorted list

Step 5:

4 9 10 15 18 26 21 20 //reading the smallest element 18 and placing it ahead of the unsorted list

Step 6:

4 9 10 15 18 20 21 26 //reading the smallest element 20 and placing it ahead of the unsorted list

Thus it takes 6 steps to sort the given list using selection sort.

Merge Sort:

Step 1:

18|4       26|9       21|15       20|10   //Dividing the list

Step 2:

18   4   26   9   21   15   20   10   //Dividing the list more further so that each element is separate

Step 3:

4|18       9|26       15|21   10|20   //Merging and sorting the array using 2 elements at a time

Step 4:

   4|9|18|26           10|15|20|21       //Merging and sorting the array using 4 elements at a time

Step 5:

           4|9|10|15|18|20|21|26           //Merging and sorting the array using all the 8 elements at a time  

Thus it takes 5 steps to sort the given list using merge sort.

Performance:

Insertion Sort:
The performace on the given list of 8 elements is 56.

Selection Sort:
The performace on the given list of 8 elements is 28.

Merge Sort:
The performace on the given list of 8 elements is 15.22.

Q2:

import java.io.*;
import java.util.LinkedList;
import java.util.ListIterator;
  
public class LinkedListDemo {
public static void main(String args[])
{
// Creating an empty LinkedList
LinkedList<String> list = new LinkedList<String>();
  
// Use add() method to add elements in the list
list.add("one");
list.add("four");
list.add("three");
list.add("five");
  
// Displaying the linkedlist
System.out.println("LinkedList:" + list);
  
// Setting the ListIterator iter1
ListIterator<String> iter1 = list.listIterator();

   // Adding new Element at 5th Position
   list.add(1, "two");

   // Remove the head using remove()
list.remove("four");
list.remove("five");

   // Displaying the linkedlist
System.out.println("LinkedList:" + list);

   // Setting the ListIterator iter1
ListIterator<String> iter2 = list.listIterator(0);

   //add one and a half to the second element
   list.add(1, iter2.next() + " and a half");
  
   //move the iterator to the 3 position
   iter2.next();
   list.add(3, iter2.next() + " and a half");

   //move the iterator to the 5 position
   iter2.next();
   list.add(3, iter2.next() + " and a half");
          
  
// Iterating through the created list from the position
System.out.println("The list is as follows:");
while(list_Iter.hasNext()){
System.out.print(list_Iter.next());
System.out.print(" , ");
}
}
}

Q3:

a)

public class LinearSearch {
public static void main(String args[]){
int array[] = {24,2,45,20,56,75,2,56,99,53,12};
int size = array.length;
int value = 2;

for (int i=0 ;i< size-1; i++){
if(array[i]==value){
System.out.println("Element found index is :"+ i);
}else{
System.out.println("Element not found");
}
}
}
}

b) If the number 2 is searched the index of this element will be 1 and 6 as there the number 2 occurs two times in the list. However if you want only one index to be shown that can also be done with the help of a flag variable.