Using arrays for sorting
Arrays are useful "vessels" for holding values being sorted. You can load an array with values you want to sort, then sort them in place within the array using the bubble sort algorithm. This assignment is for the purpose of practicing array handling-- creating arrays, writing values into their elements, reading values back, measuring arrays' length, adding new elements to them, etc. The bubble sort algorithm is secondary, so it's spelled out below in the instructions.
The exercise to perform:
Write a script that will accept the name of a file on the command line, load the file's words into an array, sort them with the bubble sort algorithm, and output the sorted result. Put all the logic into a function. Have the main program do nothing but receive from the command line, as arguments, the items to be sorted; then call the function, passing those items to it. The function will load them into an array and then proceed to sort.
Remember the bubble sort algorithm? In sorting a list of items it compares adjacent list items and sorts them as a pair. That is, if they are already in order (first is "lesser" than second) nothing happens, but if out of order (first is "greater" than second) it swaps or transposes them (they exchange places). It goes through the list from beginning to end, swapping wherever necessary as it goes. At that point, whatever element in the list is greatest will be at the end of the list. It performs another pass, but this time doesn't treat all the pairs in the list; it omits the last pair since it's already right. On the third pass it omits the last two pairs. On the nth pass it omits the last n-1 pairs.
Algorithm
In the main program:
- call the function, giving a list of arguments on its command line which are the words found in the file
In the function:
- assign the incoming arguments to an array, so each argument individually gets its own array element
- determine the number of elements (i.e., the length of the array). The number of element pairs is one less than the number of elements.
- run an outer loop a fixed number of iterations, that number being the number of pairs. Run this loop's counter downward, from number-of-pairs through zero.
- within it run another loop, also with a fixed number of iterations. That number should be the outer loop's counter value. Run the inner loop counter upward, from zero through one less than the current outer-loop-counter.
- within the inner loop, test the array element that has current inner-loop-counter as index against its "upward" neighbor, the one whose index is one greater than the current inner-loop-counter. The test is whether it's greater. If it is, swap them.
- after the looping is done, at the bottom of your function, output the array. It will be sorted.
This worked for me. You might depart from it in some details as long as you
are effecting a bubble sort.
Submit your finished program to me and I will try it on a couple of my files. Please name it "sorter-bubble" and place it in your assignments directory on the class server.
------------------------
Excerpts about handling arrays from bash man page:
In the context where an assignment statement is assigning a value to
a shell variable or array index, the += operator can be used to
append to or add to the variable's previous value.... When += is
applied to an array variable using compound assignment (see Arrays
below), the variable's value is not unset (as it is when using =),
and new values are appended to the array beginning at one greater
than the array's maximum index (for indexed arrays) or added as
additional key-value pairs in an associative array. ...
Arrays
Bash provides one-dimensional indexed and associative array vari-
ables. Any variable may be used as an indexed array; the declare
builtin will explicitly declare an array. There is no maximum limit
on the size of an array, nor any requirement that members be indexed
or assigned contiguously. Indexed arrays are referenced using inte-
gers (including arithmetic expressions) and are zero-based; asso-
ciative arrays are referenced using arbitrary strings.
An indexed array is created automatically if any variable is
assigned to using the syntax name[subscript]=value. The subscript
is treated as an arithmetic expression that must evaluate to a num-
ber. If subscript evaluates to a number less than zero, it is used
as an offset from one greater than the array's maximum index (so a
subcript of -1 refers to the last element of the array). To explic-
itly declare an indexed array, use declare -a name (see SHELL
BUILTIN COMMANDS below). declare -a name[subscript] is also
accepted; the subscript is ignored.
Associative arrays are created using declare -A name.
Attributes may be specified for an array variable using the declare
and readonly builtins. Each attribute applies to all members of an
array.
Arrays are assigned to using compound assignments of the form
name=(value1 ... valuen), where each value is of the form [sub-
script]=string. Indexed array assignments do not require the
bracket and subscript. When assigning to indexed arrays, if the
optional brackets and subscript are supplied, that index is assigned
to; otherwise the index of the element assigned is the last index
assigned to by the statement plus one. Indexing starts at zero.
When assigning to an associative array, the subscript is required.
This syntax is also accepted by the declare builtin. Individual
array elements may be assigned to using the name[subscript]=value
syntax introduced above.
Any element of an array may be referenced using ${name[subscript]}.
The braces are required to avoid conflicts with pathname expansion.
If subscript is @ or *, the word expands to all members of name.
These subscripts differ only when the word appears within double
quotes. If the word is double-quoted, ${name[*]} expands to a sin-
gle word with the value of each array member separated by the first
character of the IFS special variable, and ${name[@]} expands each
element of name to a separate word. When there are no array mem-
bers, ${name[@]} expands to nothing. If the double-quoted expansion
occurs within a word, the expansion of the first parameter is joined
with the beginning part of the original word, and the expansion of
the last parameter is joined with the last part of the original
word. This is analogous to the expansion of the special parameters
* and @ (see Special Parameters above). ${#name[subscript]} expands
to the length of ${name[subscript]}. If subscript is * or @, the
expansion is the number of elements in the array. Referencing an
array variable without a subscript is equivalent to referencing the
array with a subscript of 0.
An array variable is considered set if a subscript has been assigned
a value. The null string is a valid value.
The unset builtin is used to destroy arrays. unset name[subscript]
destroys the array element at index subscript. Care must be taken
to avoid unwanted side effects caused by pathname expansion. unset
name, where name is an array, or unset name[subscript], where sub-
script is * or @, removes the entire array.
The declare, local, and readonly builtins each accept a -a option to
specify an indexed array and a -A option to specify an associative
array. If both options are supplied, -A takes precedence. The read
builtin accepts a -a option to assign a list of words read from the
standard input to an array. The set and declare builtins display
array values in a way that allows them to be reused as assignments.