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(log_{2}
N) is much better than O(N^{2})
-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(N^{2})
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 1^{st} pass, last element is in order, after 2^{nd} 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 (1^{st} swap) | 27 42 (2^{nd} swap) | 31 42 (3^{rd} swap) | (no swap) | 12 52 (4^{th} swap) | 19
27 31 42 12 52 (end of 1^{st} pass) |
19
27 31 42 12 52 | (no swap) | (no swap) | (no swap) | 12 42 (stop) | 19
27 31 12 42 52 (end of 2^{nd} pass) |
19
27 31 12 42 52 | (no swap) | (no swap) | 12 31 (stop) | 19
27 12 31 42 52 (end of 3^{rd} pass) |
19
27 12 31 42 52 | (no swap) | 12 27 (stop) | 19
12 27 31 42 52 (end of 4^{th} pass) |
19
12 27 31 42 52 | 12
19 (stop) | 12
19 27 31 42 52 (end of 5^{th} pass) |
12
19 27 31 42 52 | (no swap)
(stop) (end of 6^{th} pass) |
-NOTE that once array is sorted, it takes
on pass to discover that nothing swapped
Selection
-O(N^{2}) 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 1^{st} position, find smallest value and
put it in 1^{st} position
-starting at 2^{nd} position, find 2^{nd} smallest
value and put it in 2^{nd} position
-starting at 3^{rd} position, find 3^{rd} smallest
value and put it in 3^{rd} position
-etc.
eg:
23 14 42 63 15 8 //start at 1^{st} place, find the 8 and swap with 23
8 14 42 63 15 23 //start at 2^{nd} place, find the 14 and swap with 14
8 14 42 63 15 23 //start at 3^{rd}
place, find the 15 and swap with 42
8 14 15 63 42 23 //start at 4^{th}
place, find the 23 and swap with 63
8 14 15 23 42 63 //start at 5^{th} place, find the 42 and swap with 42
8 14 15 23 42 63 //start at 6^{th}
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 1^{st}
position
for (j=1; j < N; j++) //note
starting at 2^{nd} 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(N^{2}) - 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:
1^{st} pass: 18
2^{nd} pass: 13 18 (18 is shifted right)
3^{rd} pass: 13 16 18 (18 is shifted right)
4^{th} pass: 4 13 16 18 (13,16,18 are shifted right)
5^{th} 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 2^{nd} 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 1^{st} pass
13 42 83 51 17 //after 2^{nd} pass
13 42 51 83 17 //after 3^{rd} pass
13 17 42 51 83 //after 4^{th}
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!