Answered: Exercise 1: In this problem, we would…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Exercise 1:
In this problem, we would like to implement a variation of the Bubble Sort algorithm. The algorithm differs from a bubble sort in that it sorts in both directions on each pass through the list. The algorithm is illustrated as in the following figure:

For the first step, we perform bubble sort from the index 1 to n (n is the
number of elements in the array).
The next step, we perform a reserved bubble sort from the index n to 1.
The process is repeated until all the array is sorted.

Propose a pseudo-code to complete the Bubble Sort algorithm. Implement and test this algorithm in C/C++. Analyze and compute the complexity of this algorithm in the best, average and worst scenarios.

Exercise 2:
Re-implement Exercise 1 using a linear data structure: List, Stack, Queue. Justify your choice of data structure.

1 99
1 55
1
11
2 55
2|44
2 55
2 44
3 44
3 22
3 44
3 22
4 22
4 66
4 22
0455
5 66
5 88
5 66
5 66
6 88
6 33
6 88
6 33
7 33
711
07 33
07 88
8 11
8 99
8 99
8 99
Input list Pass 1
Pass 2
Pass 3
11
1 11
1 11
1 11
2 44
02 22
2 22
2 22
3 22
3 44
3 33
3 33
4| 55
33
04
44
4 44
5 66
5 55
5 55
5 55
6 33
6 66
6 66
6 66
7 88
7 88
7 88
7 88
8 99
8 99
8 99
8 99
Pass 4
Pass 5
Pass 6
O.
-Q.
O.
40- O..

Expert Solution

Step by step

Solved in 6 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions