Data Structures Efficiency

Linked-List Efficiency
Insertion and deletion at the beginning of a linked list are very fast. They involve
changing only one or two references, which takes O(1) time.
Finding, deleting, or inserting next to a specific item requires searching through, on
the average, half the items in the list. This requires O(N) comparisons. An array is
also O(N) for these operations, but the linked list is nevertheless faster because
nothing needs to be moved when an item is inserted or deleted. The increased efficiency
can be significant, especially if a copy takes much longer than a comparison.

When would you use a linked list as opposed to an array as the implementation of a
stack or queue? One consideration is how accurately you can predict the amount of
data the stack or queue will need to hold. If this isn’t clear, the linked list gives you
more flexibility than an array. Both are fast, so speed is probably not a major
consideration.

Efficiency of Sorted Linked Lists
Insertion and deletion of arbitrary items in the sorted linked list require O(N)
comparisons (N/2 on the average) because the appropriate location must be found by
stepping through the list. However, the minimum value can be found, or deleted, in
O(1) time because it’s at the beginning of the list. If an application frequently
accesses the minimum item, and fast insertion isn’t critical, then a sorted linked list
is an effective choice. A priority queue might be implemented by a sorted linked list,
for example.

Algorithms - Sorting

Bubble Sort:

 public void bubbleSort()

{
int out, in;
for(out=nElems-1; out>1; out--) // outer loop (backward)
for(in=0; inif( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
} // end bubbleSort()

The bubble sort routine works like this: You start at the left end of the line and
compare the two kids in positions 0 and 1. If the one on the left (in 0) is taller, you
swap them. If the one on the right is taller, you don’t do anything. Then you move
over one position and compare the kids in positions 1 and 2. Again, if the one on
the left is taller, you swap them.You continue down the line this way until you reach the

 right end. You have by no means finished sorting the kids, but you do know that the tallest kid is
on the right.This is why it’scalled the bubble sort: As the algorithm progresses, the biggest items “bubble
up” to the top end of the array.

-------------------------------------------------------------------------------------------------
 Selection Sort:

public void selectionSort()
{
int out, in, min;
for(out=0; out{
min = out; // minimum
for(in=out+1; inif(a[in] < a[min] ) // if min greater,
min = in; // we have a new min

swap(out, min); // swap them
} // end for(out)
} // end selectionSort()
//Swap Function
private void swap(int one, int two)
{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}

 What’s involved in the selection sort is making a pass through all the players and
picking (or selecting, hence the name of the sort) the shortest one. This shortest
player is then swapped with the player on the left end of the line, at position 0. Now
the leftmost player is sorted and won’t need to be moved again. Notice that in this
algorithm the sorted players accumulate on the left (lower indices), whereas in the
bubble sort they accumulated on the right.
The next time you pass down the row of players, you start at position 1, and, finding
the minimum, swap with position 1. This process continues until all the players are
sorted.

The selection sort improves on the bubble sort by reducing the number of swaps
necessary from O(N^2) to O(N). Unfortunately, the number of comparisons remains
O(N^2).

---------------------------------------------------------------------------------------------------

Insertion Sort:

public void insertionSort()
{
int in, out;
for(out=1; out{
long temp = a[out]; // remove marked item
in = out; // start shifts at out
while(in>0 && a[in-1] >= temp) // until one is smaller,
{
a[in] = a[in-1]; // shift item right,

--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
} // end insertionSort()