Questions on various Topics of Data Structures(Randomly Mixed) Set 5

Write an algorithm for bubble sort.

1. Set pass=1
2. Repeat step 3 varying j from 0 to (n - 1 - pass).
3. If the element at index j is greater than the element at index j+1, swap the two elements.
4. Increment pass by 1.
5. If (pass <= n="" -="" 1)="" go="" to="" step="">

What is worst case and average case of bubble sort algorithm?

Worst case = O(n²) and average case = O(n²).

How do we define bubble sort?

Write an algorithm to search for an employee ID in an array(Hint: use linear search)

1. Read the employee ID to be searched
2. Set i=0
3. Repeat step d until i>n or arr[i]=employee ID
4. Increment i by 1
5. If i>n : Display "Not found"
   Else Display "Found"

Write an algorithm fo deleting a node between two nodes in the doubly-linked list.

The algorithm to delete a node between two nodes in the list is as follows:

1. Make the node to be deleted as current and its predecessor as previous. To locate previous and current, execute the following steps:
   1. Make previous point to NULL.
   2. Make current point to the first node in the linked list.
   3. Repeat steps d and e until either the node is found or current becomes NULL.
   4. Make previous point to current.
   5. Make current point to the next node in sequence.
2. Make the next field of previous point to the successor of current
3. Make the prev field of the successor of current point to previous
4. Release the memory of the node marked as current.

Write an algorithm to delete a node from the end of the circular -linked list.

The algorithm to delete a node from the end of the circular -linked list:

1. Make current point to LAST.
2. mark the predecessor of LAST as previous. To locate the predecessor of LAST execute the following steps:
   1. Make previous point to the successor of LAST.
   2. Repeat step c until the successor of previous becomes LAST.
   3. Make previous point to the next node in sequence.
3. Make the next field of previous point to successor of LAST.
4. Mark previous as LAST.
5. Release the memory of node marked as current.

What is best case performance of bubble sort algorithm?

The best case performance of bubble sort algorithm is O(n).

Write an algorithm to insert a node between two nodes in the list, when the list is not empty.

If the list is not empty, the following algorithm is used to insert a node between two nodes in the linked list.

1. Identify the nodes between which th new node is to be inserted. Mark them as previous and current. To locate previous and current, execute the following steps:
   1. Make current point to the first node.
   2. Make previous point to NULL.
   3. Repeat step d and e until current.info>newnode.info or previous=LAST
   4. Make previous point to current.
   5. Make current point to the next node in sequence.
2. Allocate a memory fo new node.
3. Assign a value to the data field of the new node.
4. Make the next field of new node point to current.
5. Make the next field of previous point to the new node.

Write Code for bubble sort in java

public void bubbleSort(int[] arr)
{

    boolean swapped = true;

    int j = 0;

    int tmp;

    while (swapped)
    {

        swapped = false;

        j++;

        for (int i = 0; i < arr.length - j; i++)
        {

            if (arr[i] > arr[i + 1])
            {

                tmp = arr[i];

                arr[i] = arr[i + 1];

                arr[i + 1] = tmp;

                swapped = true;

            }

        }

    }

}

Draw the structure of a linked list.

first part represent data and second part represent address of next node