I need a C master to roll his wisdom and skill into my skull so i can
pass this very difficult online course : )
assignment:
Add a binary search to the implementation of QuickSort that we have
been working on. The code is in Code/Quick_Sort. Your finished product
should generate an array of random integers (first command line arg is
the number of integers to be generated) and sort them using QuickSort
and then search the array for any number of integers that are entered
on the command line, writing an appropriate message to standard output
for each.
EXAMPLE:
a command line like this...
Quick 100 8 31 59
should give output like this...
8 is not in the list
31 is not in the list
59 is in the list
Have fun!
------------more assignment notes
The functions
In the directory Code/Quick_Sort there are several source files and
some other files yo need to look at and/or use. They are, in no
particular order,:
* makefile - The makefile for the existing version of the code
* makefile.binsearch - The makefile you will use after writing
your binary search function
* Partition.c - The function that does the partition (no kidding!)
* Sort.c - The function that calls Partition( ) and then makes the
recursive calls to itself
* swap.c - switches 2 items in the list
* Quick.c - This is actually a sort of "dummy" function. This
layer allowed me to interchange sorting algorithms using the same
code.
* main.c - driver that generates a random list of ints and then
calls the sort function
* timming - table of data showing how different sorting algorithms
compare
Please make sure you look carefully at all this code. It is only a
total of about 30 lines of code, but it is packed. Just be sure you
understand each line and even each character! I'm going to show the
Partition( ) and Sort( ) functions here, because I need to make a few
points, but the rest is pretty simple and I leave it up to you to ask
if there is anything you aren't clear on.
The source code
The source for Partition( ) which picks a pivot item and splits the
list:
int Partition(int *l,int low,int high)
{
void swap(int,int,int*);
int i,pivotloc;
int pivotkey;
swap(low,(low+high)/2,l);
pivotkey = l[low];
pivotloc = low;
for (i=low+1;i<=high;i++)
if (l[i] < pivotkey) swap(++pivotloc,i,l);
swap(low,pivotloc,l);
return (pivotloc);
}
First, you call swap( ) to get the pivot item from the middle of the
list. Then we initialize "pivotkey" to the value of the pivot item and
"pivotloc" to the index in the list where the pivot item is. You will
notice that each time we find an item that belongs before the
pivotkey, we swap it to the location pointed to by pivotloc. Each time
this switch happens we incrament pivotloc so that pivotloc always
points to the first item that does not go before the pivotkey. Then
after the for loop ends, we swap the pivot item back to the middle of
the list, at pivotloc, so that that item is where it belongs and the
list has been split in two. You can see this in detail in the "walk
through" in the next section.
The source for Sort( ) which calls partition and then calls itself to
sort the 2 parts of the list that Partition( ) creates:
void Sort(int *l,int low,int high)
{
int Partition(int*,int,int);
int pivotloc;
if (low < high) {
pivotloc = Partition(l,low,high);
Sort(l,low,pivotloc-1);
Sort(l,pivotloc+1,high);
}
}
Notice that this function is really very simple, conceptually. All it
does is get the pivot location from Partition( ) and then call itself
to sort each half of the list. Aside from the whole recursive thing,
there really is nothing to it.
QuickSort algorithim "walk through"
You need to do most of the "walk through" yourself. All of the code is
very straight forward, even the Sort( ) function with the recursive
call, except for the Partition( ) function. We are going to take a
list with 10 items and walk through the first call to Partition( ).
Once you see one pass of Partition( ) you can apply it yourself to the
rest of the run of the program.
the Partition( ) function
Lets use an array called "data". In the code the array is called
"l"(ell), but the "l"(ell) looks too much like a "1"(one), so I'm
going with "data". :) Suppose the array is filled as follows:
begin walk through
we have low = 0 and high = 9 so then middle = 4 and after swapping the
middle item with the first item we get:
swap partition to beginning
Now the for loop will start "i" at 1 and go through 9 and if data[i]
is less than pivotkey, we make the swap. Now with i = 1 and data[i] =
54 and pivotkey = 55 data[i] is less than pivotkey so we make the
swap.
first swap in partition
Notice the list looks the same? That is because we incrament pivotloc
before we do the swap, and in this case pivotloc = 1 and so does "i"
so we "swapped" the 54 with itself. Now we have i = 2 and data[i] = 60
and pivotkey = 55 so data[i] is not less than pivotkey so we don’t
swap.
Now we have i = 3 and data[i] = 62 and pivotkey = 55 so data[i] is not
less than pivotkey so we don’t swap.
Now we have i = 4 and data[i] = 58 and pivotkey = 55 so data[i] is not
less than pivotkey so we don’t swap.
Continuing, we have i = 5 and data[i] = 51 and pivotkey = 55 so
data[i] is less than pivotkey so we make the swap.
another swap in partition
Notice that pivotloc was incramented to 2 before we made the swap so
that data[i] was swapped with a value that is larger than pivotkey.
This is important, because we know that we do not have to check that
item to see if it is less than pivotkey, because we already checked
it. Now we have i = 6 and data[i] = 47 and pivotkey = 55 so data[i] is
less than pivotkey so we incrament pivotloc to 3 and make the swap.
another swap in partition
For i = 7 and i = 8 we don't need to swap, but for i = 9 we have
data[i] = 53 and pivotkey = 55 so data[i] is less than pivotkey so we
incrament pivotloc to 4 and make the swap.
another swap in partition
Now we have to put the pivotkey in the place where it belongs.
pivotloc is 4, which is the last location occupied by a value less
than the pivotkey, so since all the values after that one are greater
than the pivotkey we make one last swap, swapping data[low] with
data[pivotloc].
last swap in partition
Now Partition( ) returns pivotloc so that Sort( ) can call itself for
the 2 "halfs" of the list, like this:
Sort(low,pivotloc-1,data);
Sort(pivotloc+1,high,data);
Do a complete walk through!
Make your own list of about 10 items (or use the one I have here) and
do a complete walk through. You should make a picture like the one
from the "QuickSort algorithim" section in these notes, except yours
will have numbers in it. Don't worry if several of the pivot items
that get picked are not in the middle of the list, with a short list,
you could get several "bad" ones. The point is to walk through the
code and try to keep track of where you are with calls to Sort( ). The
best thing to do is to get a pile of scrap paper and each time you
call Sort( ) in your walk through, make a new sheet of paper with all
the variable values on it. Your "stack" of Sort( ) calls will mimic
the actual stack on the system. Each time you finish an instance of
Sort( ) simply take it off the pile. The paper now on top is the
instance of Sort( ) that you should be in. Good luck and email me
questions or problems.
program given w/ assignment;
[root@win186821wks out]# more *
::::::::::::::
binary_search.c
::::::::::::::
#define MAX 11
main()
{
int top,bottom,middle,i,key;
int data[]={31,45,57,88,143,201,204,327,328,414,499};
printf("sorted list:\n");
for (i=0;i<MAX;i++) printf("%d\n",data[i]);
printf("Enter search key: ");
scanf("%d",&key);
top=0;
bottom=MAX-1;
middle=(top+bottom)/2;
do{
if (data[middle]<key)
top=middle+1;
else
bottom=middle;
middle=(top+bottom)/2;
}while(top<bottom);
if (data[middle]==key)
printf("%d was found at location %d\n",key,middle);
else
printf("%d was not found\n",key);
}
::::::::::::::
main.c
::::::::::::::
/*************************************************/
/* main driver for Quick-Sort implementation */
/* This program will create an array of ints */
/* using a random number generator, then print */
/* the array, then sort it with a Quick-Sort */
/* algorithm, then print it again. */
/*************************************************/
#include <math.h>
main(int c,char **v)
{
void Quick(int,int*);
int *list;
int count,i;
if (c==1) {printf("Usage: Quick list_size\n");exit();}
/* use the first command line argument as the number
of elements to create and sort */
count=atoi(v[1]);
/* allocate space for the array */
list=(int *)malloc(count*sizeof(int));
/* generate the array of random ints... use %count so
that each number is the remainder when you divide
by count. Thus the biggest number you can get in
your array is count-1 */
for(i=0;i<count;i++) list[i]=random(i)%count;
/* print - sort - print */
for(i=0;i<count;i++) printf("%d\n",list[i]);
Quick(count,list);
for(i=0;i<count;i++) printf("%d\n",list[i]);
}
::::::::::::::
makefile
::::::::::::::
Quick: Quick.o main.o Partition.o Sort.o swap.o
cc Quick.o main.o Partition.o Sort.o swap.o -o Quick -lm
Quick.o: Quick.c
cc -c Quick.c
main.o: main.c
cc -c main.c
Partition.o: Partition.c
cc -c Partition.c
Sort.o: Sort.c
cc -c Sort.c
swap.o: swap.c
cc -c swap.c
::::::::::::::
makefile.binsearch
::::::::::::::
Quick: Quick.o main.o Partition.o Sort.o swap.o binsearch.o
cc Quick.o main.o Partition.o Sort.o swap.o binsearch.o -o
Quick -lm
Quick.o: Quick.c
cc -c Quick.c
main.o: main.c
cc -c main.c
Partition.o: Partition.c
cc -c Partition.c
Sort.o: Sort.c
cc -c Sort.c
swap.o: swap.c
cc -c swap.c
binsearch.o: binsearch.c
cc -c binsearch.c
::::::::::::::
Partition.c
::::::::::::::
int Partition(int *l,int low,int high)
{
void swap(int,int,int*);
int i,pivotloc;
int pivotkey;
swap(low,(low+high)/2,l);
pivotkey = l[low];
pivotloc = low;
for (i=low+1;i<=high;i++)
if (l[i] < pivotkey) swap(++pivotloc,i,l);
swap(low,pivotloc,l);
return (pivotloc);
}
::::::::::::::
Quick.c
::::::::::::::
void Quick(int n,int *list)
{
void Sort(int*,int,int);
Sort(list,0,n-1);
}
::::::::::::::
Sort.c
::::::::::::::
void Sort(int *l,int low,int high)
{
int Partition(int*,int,int);
int pivotloc;
if (low < high) {
pivotloc = Partition(l,low,high);
Sort(l,low,pivotloc-1);
Sort(l,pivotloc+1,high);
}
}
::::::::::::::
swap.c
::::::::::::::
void swap(int i,int j,int *l)
{
int tmp;
tmp = l[i];
l[i] = l[j];
l[j] = tmp;
}
::::::::::::::
timming
::::::::::::::
n selection insertion shell quick
--------------------------------------------------
1000 1.9 1.5 1.0 1.0
2000 5.0 4.1 2.1 2.0
3000 10.1 7.8 3.1 3.1
5000 26.9 19.0 5.4 5.2
10000 110.5 73.8 10.9 10.4
50000 ----- 1647.7 54.1 52.7
--------------------------------------------------
1647.7 seconds is approx 27.5 minutes |
