Section 5: Sorting/searching (NOT from book!)

(book covers sorts in 12.3, but uses classes, so may be confusing…)

-Sorting is fundamental to working with arrays

-Many kinds of sorts, all end up with the array sorted, but some work more efficiently

-Analysis of algorithms involves determining the "Big O" value, which you'll learn more in data structures (roughly it's the number of operations per N data elements)
-For now, understand that big O can be judged in the type of function: parabolic, linear, logarithmic (from bad to best): O(log2 N) is much better than O(N2)
-Even w/sorts of same big O, some are better at certain types of data than others
-We'll stick with simple to understand sorts, which are mostly O(N2)

Bubble

-a 'baby' sort - EASY to understand/write, but never really used in RW

-but a good teaching tool to understand the concept of sorts

-is good for nearly sorted data

Algorithm:

LAST = INDEX OF LAST ELEMENT

DO

SWAPPED = FALSE

FOR (I=1 [YES, ONE!], I <= LAST, I++)

IF ARRAY[I] < ARRAY[I-1]

SWAP(ARRAY[I],ARRAY[I-1])

SWAPPED = TRUE

LAST= LAST -1

WHILE SWAPPED

-Note that we work on "shorter and shorter" array, because after 1st pass, last element is in order, after 2nd pass, last two elements are in order, etc. and we don't keep checking those elements

-The for loop controls each "pass" through the array looking for swaps

-The do-while controls when to stop - once nothing is swapped in a pass

Hand trace:

42

19

27

31

52

12

19

42

(1st swap)


27

42

(2nd swap)



31

42

(3rd swap)




(no swap)




12

52

(4th swap)

19

27

31

42

12

52

(end of 1st pass)

19

27

31

42

12

52

(no swap)
(no swap)


(no swap)



12

42

(stop)

19

27

31

12

42

52

(end of 2nd pass)

19

27

31

12

42

52

(no swap)
(no swap)


12

31

(stop)

19

27

12

31

42

52

(end of 3rd pass)

19

27

12

31

42

52

(no swap)
12

27

(stop)

19

12

27

31

42

52

(end of 4th pass)

19

12

27

31

42

52

12

19

(stop)

12

19

27

31

42

52

(end of 5th pass)

12

19

27

31

42

52

(no swap)

(stop)

(end of 6th pass)

-NOTE that once array is sorted, it takes on pass to discover that nothing swapped

Selection

-O(N2) again, but works reasonably well on shorter lists

-Not particularly good for nearly sorted data - still does lots of compares

-works by making multiple passes on the list, finding the smallest element and placing it in correct position
-ie:
-starting at 1st position, find smallest value and put it in 1st position
-starting at 2nd position, find 2nd smallest value and put it in 2nd position
-starting at 3rd position, find 3rd smallest value and put it in 3rd position
-etc.

eg:

23 14 42 63 15 8 //start at 1st place, find the 8 and swap with 23

8 14 42 63 15 23 //start at 2nd place, find the 14 and swap with 14

8 14 42 63 15 23 //start at 3rd place, find the 15 and swap with 42
8 14 15 63 42 23 //start at 4th place, find the 23 and swap with 63

8 14 15 23 42 63 //start at 5th place, find the 42 and swap with 42

8 14 15 23 42 63 //start at 6th place, find the 63 and swap with 63

-note that it keeps comparing, even tho sorted (that's why it's not so good for nearly sorted data)

-note that each pass is working on shorter list (and in each pass, we are searching for the smallest value in the remainder of the list)

-so we need to understand how to search an array and find the index of the smallest (or largest):

-for an array of N elements, subscripted from 0 to N-1:
MinIndex = 0; //default to smallest being in 1st position
for (j=1; j < N; j++) //note starting at 2nd position - index #1
if (Array[j] < Array[MinIndex])
MinIndex = j;

-when we're done, MinIndex holds the index of the smallest element in the array

-we can make a generic function to search an array from any position to any position:

int IndexOfMin(int FirstIndex, int LastIndex, const SOMETYPE Array)

{
int MinIndex = FirstIndex;
for (j=FirstIndex+1; j<=LastIndex; j++)

if (Array[j] < Array[MinIndex])
MinIndex = j;
return MinIndex;

}

-so we can use this function in selection sort:

for (j=0; j<length; j++)

{
MinPos = IndexOfMin(j, length-1, Array);

Swap(Array[j], Array[MinPos];

}

Insertion (building from empty/sorting filled)

-building from empty:

-this is like being dealt a hand of cards, and picking them up one at a time and placing them into your hand in order as you pick them up

-O(N2) - not good for large data types, due to shifting of data when value inserted

eg:

-data to be inserted into array: 18 13 16 4 20

contents of array:

1st pass: 18

2nd pass: 13 18 (18 is shifted right)

3rd pass: 13 16 18 (18 is shifted right)

4th pass: 4 13 16 18 (13,16,18 are shifted right)

5th pass: 4 13 16 18 20 (no shift)

-note that after each pass, the array is in sorted order, for the contents so far

-as insertion progresses, keep track of length, so that when done, we know how big array is

-pseudocode:

length = 0

while not end of data:

READ val
array[length] = val //put into end of array temporarily
searcher = 0
while array[searcher] < val //find index where val should go
searcher++
for shifter=length-1,shifter>=searcher,shifter-- //shift contents
array[shifter+1] = array[shifter]
array[searcher] = val

length++

-note when done, length is size of array (length-1 is index of last element)

-insertion sort on already filled array:

-given an array of length N (ie, N elements, subscripted from 0 to N-1), this sort will apply insertion algorithm

requires short-circuit evaluation!!

THIS CODE IS CORRECT! (THE TRACE WAS WRONG…..)

void Insert(int TheList[], int N)

{

int

Temp, //holds value to insert

Searcher, //moves thru array

Shifter; //used to shift array elements

for(Searcher=1; Searcher<N; Searcher++) //start at 2nd element!

if (TheList[Searcher-1] > TheList[Searcher])

{

Temp = TheList[Searcher]; //smaller element saved in temp

//start shifting elements until you find the spot for temp:

Shifter = Searcher - 1;

while (Shifter > -1 && TheList[Shifter] > Temp)

{

TheList[Shifter+1] = TheList[Shifter]; //shift right

Shifter--;

}//end while

TheList[Shifter+1] = Temp; //insert temp in position

}//end if

}//end function

-Note the condition of the while - must use short circuit evaluation, or could access array at index of -1!!

-sample (CORRECTED 2/6/97):

83 13 42 51 17 //original

13 83 42 51 17 //after 1st pass

13 42 83 51 17 //after 2nd pass

13 42 51 83 17 //after 3rd pass

13 17 42 51 83 //after 4th pass

-searching

-once an array is sorted, searching for a particular value can be made more efficient

-if array is unsorted, must do a linear search (BigO(N)):

x=0;

while (x < N && array[x] != Target) //s.s. evaluation

x++;

if (x==n)

return -1; //not found - "fell off" array

else

return x;

-this isn't so good for large values of N!!

-with a sorted array of size N, we can use a binary search algorithm:

first = 0;

last = N-1;

found = 0;

while (first <= last && !found)

{

middle = (first+last)/2;

if (target < List[middle])

last = middle-1;

else

if (target > List[middle])

first = middle+1;

else

found = 1;

}//end while

if (found)

return middle;

else

return -1;

-sample hand traces:

1. array contents:20 35 37 40 45 50 51 55 67

target: 35

found: 0

first: 0 last: 8 middle: 4

last: 3

middle: 1


found: 1


2. array contents:20 35 37 40 45 50 51 55 67

target: 57

found: 0

first: 0 last: 8 middle: 4

first: 5

middle: 6

first: 7

middle: 7

first: 8

middle: 8

last: 7

DONE! LAST < FIRST!

NOT FOUND

-How about doing this with an array of strings? Why not??!! works just the same!! Only the array data type is different- here is a place where overloading the function name (pp.376-379) can come in handy!