Bubble Short

Q. Bubble sorts the following numbers in an array:
32, 51, 27, 85, 66, 23, 13, 57.
Ans:
Pass 1: 32 51 27 85 66 23 13 57
32 51 27 85 66 23 13 57
32 27 51 85 66 23 13 57
32 27 51 85 66 23 13 57
32 27 51 66 85 23 13 57
32 27 51 66 23 85 13 57
32 27 51 66 23 13 85 57
32 27 51 66 23 13 57 85
Pass 2: 32 27 51 66 23 13 57 85
27 32 51 66 23 13 57 85
27 32 51 66 23 13 57 85
27 32 51 66 23 13 57 85
27 32 51 23 66 13 57 85
27 32 51 23 13 66 57 85
27 32 51 23 13 57 66 85

Pass 3: 27 32 51 23 13 57 66 85
27 32 51 23 13 57 66 85
27 32 51 23 13 57 66 85
27 32 23 51 13 57 66 85
27 32 23 13 51 57 66 85
27 32 23 13 51 57 66 85


Pass 4: 27 32 23 13 51 57 66 85
27 32 23 13 51 57 66 85
27 23 32 13 51 57 66 85
27 23 13 32 51 57 66 85
27 23 13 32 51 57 66 85

Pass 5: 27 23 13 32 51 57 66 85
23 27 13 32 51 57 66 85
23 13 27 32 51 57 66 85
23 13 27 32 51 57 66 85

Pass 6: 23 13 27 32 51 57 66 85
13 23 27 32 51 57 66 85
13 23 27 32 51 57 66 85

Pass 7: 13 23 27 32 51 57 66 85
13 23 27 32 51 57 66 85


So the sorted list is - 13 23 27 32 51 57 66 85.
The computer computes the address LOC (A [J, K]) of A [J, K] using the formula –
(Column major order) LOC (A [J, K]) = Base (A) + w [M (K – 1) + (J – 1)]
(Row major order) LOC (A [J, K]) = Base (A) + w [N (J – 1) + (K – 1)]
Where, M = number of row
N = number of column
w = number of words per memory location for the array (int, char etc).
Example: - Base (SCORE) = 200
w = 4
J = 12
K = 3
M = 25
N = 4
Row – major order.
LOC (SCORE [12, 3]) = 200 + 4[4(12 – 1) + (3 – 1)]
= 200 + 4[(4 × 11) + 2]
= 200 + 4[44 + 2]
= 200 + (4×46)
= 200 + 184
= 384
Q. What do you mean by record?
Ans: Record: A record is a collection of related data items, each of which is called a field or attribute, and a file is a collection of similar records. Each data item itself may be a group item composed of sub-items.
Although a record may be a collection of data items, it differs from a linear array in the following ways –
• A record may be a collection of nonhomogeneous data.
• The data items in a record are indexed by attribute names, so there may not be a natural ordering of its elements.
Example: - A hospital keeps records of new born baby may be organized as follows:
1. New born.
(a) Name
(b) Sex
(c) Birthday
i. Month
ii. Day
iii. Year
(d) Father
i. Name
ii. Age
(e) Mother
i. Name
ii. Age
Q. Describe the representation of linear arrays in memory.

Ans: Representation of linear arrays in memory: Let, LA be a linear array in the memory of the computer. The memory of the computer is simply a sequence of addressed locations as pictured below and the notation –
LOC (LA [K]) = address of the element LA [K] of the array LA.
The elements of LA are stored in successive memory cells. Using address Base (LA), the computer calculates the address of any element of LA by the following formula:
LOC (LA [K]) = Base (LA) + w (K – lower bound).
Where w is the number of words per memory cell for the array LA.
Q. What is linear array? How length of array can calculate? Write array notation.
Ans: Linear array: A linear array is a list of a finite number n of homogeneous data elements such that:
a. The elements of the array are referenced respectively by an index set consisting of n consecutive numbers.
b. The elements of the array are stored respectively in successive memory locations.
Length of array: The length or the number of data elements of the array can be obtained from the index set by formula –
Length = UB – LB + 1.
Where, UB is the largest index, called the upper bound, and
LB is the smallest index, called the lower bound, of the array.
Array notation: The elements of an array A may be denoted by the subscript notation –
A1, A2, A3, … … …, An.
Or, by the parentheses notation –
A (1), A (2), A (3), … … … , A (N).
Or, by the bracket notation –
A [1], A [2], A [3], … … … , A [N].
Usually the subscript notation or the bracket notation is used.
Q. What are two dimensional arrays? Describe the representation of two dimensional arrays.
Ans: Two dimensional arrays: Two dimensional arrays are called matrices in mathematics and tables in business applications. Two dimensional arrays are sometimes called matrix arrays.
Let, A is a two dimensional m×n array where j is the first subscript and k is the second subscript. This two dimensional array is denoted by –
AJ.K or, A [J, K]
Length of two dimensional arrays: The length of two dimensional arrays can be obtained from the formula –
Length = upper bound – lower bound + 1.
Representation of two dimensional arrays in memory: Let A be a two – dimensional m×n array where m is rows and n is columns. The array will be represented in memory by a block of m.n sequential memory locations in following ways –
1. column by column, is called column – major order.
2. row by row, is called row – major order.
The following figure shows these two ways when A is a two – dimensional 3×4 array.