Hockerill IB Computer Science: Arrays

You need to be able to cope with exam questions about arrays

An array is an indexed set of elements. Unless specifically defined in the question, the index of the first element in an array is 0. The first element in the array NAMES is:

The following array is defined

NAMES = ["aaron","bethany","cynthia","david","ewan","fay"]

You might might notice the array element are alphabeticallty in order An algorithm to check if an array is in order might be

IN_ORDER = True
i = 1
loop while i < length(NAMES)
   if NAMES[i-1] > NAMES[i] then
      IN_ORDER = False
   end if
   i=i+1
end loop
if IN_ORDER then
   output("Array is in order")
else
   output("Array is out of order")
end if

Various algorithms can be devised to sort an array. You are expected to know the characteristics of bubble sort and selection sort.

Select the type of sort algorithm matching the descriptions

Note that an iteration is an execution of the code inside a loop. On the first loop all adjacent elements are compared and swapped if required .
On the first loop the smallest element is found and swaps it to the beginning .
After the first loop the first element is in its correct place .
After the first loop the last element is in its correct place .
As the list become sorted iterations continue on the unsorted remainder of the list .
Has the advantage that if programmed correctly iterations stop once the array is ordered .
Has the advantage that only one swap takes place per iteration of the outer loop .
Time taken to do sort is proportional to array size .

Flowchart for a selection sort (adapted from http://www.c-programming-simple-steps.com/selection-sort.html)

In the flowchart N is the size of the array. The variable name for the array is

The selection sort algorithm uses two counter variables for the two loops In this example the variable names are which are standard variable names for counters

The outer loop involves the i counter which starts at

The inner loop involves the j counter which starts at i and continues while j<

At the start of the inner loop the algorithm sets minindex to j and min to Arr[j]. It resets these values during the loop if At the loop end the element at position i is swapped with this smallest element. The portion of the algorithm makes use of the temp namespace.

i is then increased because the arrays element up to i have been “selected”. The algorithm completes when .

Flowchart for a bubble sort (adapted from http://www.c-programming-simple-steps.com/bubble-sort.html)

In the flowchart the variable name for the array is

The bubble sort algorithm uses two counter variables for the two loops In this example the variable names are

For each iteration (the outer loop) the array is scanned from j=0 to j<N-2-iterations (inner loop). The inner loop scan can stop one place earlier each scan because the largest element will “bubble” to the end each scan. Adjacent elements array[j] and array are compared and swapped if required.

The portion of the algorithm makes use of the temp namespace.

The outer loop is continued while iterations<N AND go is True. go begins each inner loop as and will be if any array elements have been swapped.

Using the go flag enables this bubble sort to be efficient on arrays that are .

Y13 Interactive Examples of IBCS Pseudocode and Flowchart

Arrays