basic sort

Objectives:

• Study three basic sequential sorting methods (bubble, selection, and insertion)

• Understanding the complexity and pros-n-cons of each approach

• Focus now is on array, suggest that you revisit again for linked list

Array sorting

Sorting is a common way of organizing data. AFAIK, sorting is not the final objective. It is a means to make searching easier. There are many sorting methods. We will use our stock portfolio as example. The portfolio class has a static array of stocks. What we're adding is a "sort" function to the portfolio class.

Note that the sort member function does not need any parameter, because it is applied to a portfolio object which already has the entire array of stocks. This may be quite different from many coding examples which take array as parameter. Give it some thought, is it similar to the "global function" versus "member function"?

An example usage:

portT frank;

..... read in frank's portofolio

frank.sort();

Bubble sort

// sort from small to large

void sort() {

for (int target=0; target <size; target++) { // sort every target object from 0 to the end

for (int i=size-1; i>target; i--)

if (stk[i] < stk[i-1]) swap(stk[i], stk[i-1]); // bubble up from the end to target

}

}

Discussion:

• 1. The above routine sort from top to bottom of the array. Can you do one that sort from bottom to top?

  2. Does it matter that we overload operator < or operator > ?

  3. Two nested for loops through n, so the complexity is O(n**2)

Selection sort

// sort from small to large

void sort() {

for (int target=0; target <size; target++) { // sort every target object from 0 to the end

stockT minstk=stk[target]; // assume target one is the minimum

int m=target // remember who is current min

for (int i=target; i<size; i++) if (stk[i] < minstk) m=i; // new min is in m

swap(stk[target], stk[m]);

}

}

Discussion:

• 1. Inner loop initializations are used to find the minimum stk

  2. Two nested for loops through n, so the complexity is O(n**2)