A C Sort example:
1.1 Bubble sort
Advantage
of bubble sort is that the ability to
detect that the sorted list is efficiently built into the algorithm.
Bubble
sort is one of the simplest sorting
algorithms to understand and implement. Complexity means that its
efficiency decreases dramatically on lists of more than a small number of
elements. Due to its simplicity, bubble sort is often used to introduce the
concept of an algorithm, or a sorting algorithm.
In
computer graphics it is popular for its capability
to detect a very small error (like swap of just two elements) in
almost-sorted arrays and fix it with just linear complexity.
Step-by-step
example
(
from wikipedia)
Let
us take the array of numbers "5 1 4 2 8", and sort the array from
lowest number to greatest number using bubble sort. In each step, elements
written in bold are being compared. Three passes will be required.
First
Pass:
(
5 1 4 2 8 ) ( 1 5 4 2 8 ), Here,
algorithm compares the first two elements, and swaps them.
(
1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5
> 4
(
1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5
> 2
(
1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since
these elements are already in order (8 > 5), algorithm does not swap them.
Second
Pass:
(
1 4 2 5 8 ) ( 1 4 2 5 8 )
(
1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4
> 2
(
1 2 4 5 8 ) ( 1 2 4 5 8 )
(
1 2 4 5 8 ) ( 1 2 4 5 8 )
Now,
the array is already sorted, but our algorithm does not know if it is
completed. The algorithm needs one whole pass without any swap to know it is
sorted.
Third
Pass:
(
1 2 4 5 8 ) ( 1 2 4 5 8 )
(
1 2 4 5 8 ) ( 1 2 4 5 8 )
(
1 2 4 5 8 ) ( 1 2 4 5 8 )
(
1 2 4 5 8 ) ( 1 2 4 5 8 )
Pseudocode
implementation
The
algorithm can be expressed as (0-based array):
procedure
bubbleSort( A : list of sortable items )
The
bubble sort algorithm can be easily optimized by observing that the n-th pass
finds the n-th largest element and puts it into its final place. So, the inner
loop can avoid looking at the last n-1 items when running for the n-th time:
More
generally, it can happen that more than one element is placed in their final
position on a single pass. In particular, after every pass, all elements after
the last swap are sorted, and do not need to be checked again. This allows us
to skip over a lot of the elements, resulting in about a worst case 50%
improvement in comparison count (though no improvement in swap counts), and
adds very little complexity because the new code subsumes the
"swapped" variable:
To
accomplish this in pseudocode we write the following:
1.2
Insertion sort
Insertion
sort is a simple sorting algorithm that builds the final sorted array (or list)
one item at a time.
Advantages: Simple
implementation, Efficient for
small data sets; Stable, does not change the relative order of elements with equal
keys; In-place, only requires a constant amount of additional
memory space.
Compiling C :
Preprocessor
The preprocessor
provides the ability for the inclusion of header files, macro expansions,
conditional compilation, and line control. More times will need to give special
instructions to compiler. This is done by inserting preprocessor directives
into code. When begin compiling code, a special program called the preprocessor
scans the source code and performs simple substitution of tokenized strings for
others according to predefined rules.
The preprocessor
is not a part of the C language.
In C language,
all preprocessor directives begin with the pound character (#).
Example:
#include <stdio.h>
This directive
causes the header to be included into program. The language of preprocessor
directives is agnostic to the grammar of C, so the C preprocessor can also be
used independently to process other kinds of text files.
[edit]Syntax
Checking
This step
ensures that the code is valid and will sequence into an executable program.
Under most compilers, messages or warnings indicating potential issues with
program may get (such as a statement
always being true or false, etc.)When an error is detected in the program, the
compiler will normally report the file name and line that is preventing
compilation.
[edit]Object
Code
The compiler
produces a machine code equivalent of the source code that can then be linked
into the final program. The code itself can't be executed yet, as it has to
complete the linking stage. It's important to note after discussing the basics
that compilation is a "one way street". That is, compiling a C source
file into machine code is easy, but "decompiling" (turning machine
code into the C source that creates it) is not. Decompilers for C do exist, but
they rarely create useful code.
[edit]Linking
Linking combines
the separate object codes into one complete program by integrating libraries
and the code and producing either an executable program or a library. Linking
is performed by a linker, which is often part of a compiler.
Common errors
during this stage are either missing functions, or duplicate functions.
[edit]Automation
For large C
projects, many programmers choose to automate compilation, both in order to
reduce user interaction requirements and to speed up the process by only
recompiling modified files. Most integrated development environments have some
kind of project management, which makes such automation very easy. On UNIX-like
systems, make and Makefiles are often used to accomplish the same.
C
track: compiling C programs.
It is important
to understand that while some computer languages (e.g. Scheme or Basic) are
normally used with an interactive interpreter (where you type in commands that
are immediately executed), C doesn't work that way. C source code files are
always compiled into binary code by a program called a "compiler" and
then executed. This is actually a multi-step process which we describe in some
detail here.
The different
kinds of file:
Regular
source code files: contain function definitions, and have names which
end in ".c" by convention.
Header
files:
contain function declarations (also known as function prototypes) and various
preprocessor statements. To allow source code files to access externally-defined
functions. Header files end in ".h" by convention.
Object
files:
produced as the output of the compiler. Consist of function definitions in
binary form, but they are not executable by themselves. Object files end in
".o" by convention, although on some operating systems (e.g. Windows,
MS-DOS), they often end in ".obj".
Binary
executables: produced as the
output of a program called a "linker". The linker links together a
number of object files to produce a binary file which can be directly executed.
Binary executables have no special suffix on Unix operating systems, although
they generally end in ".exe" on Windows.
There are other
kinds of files as well, notably libraries (".a" files) and shared
libraries (".so" files), but normally no need to deal directly.
The
preprocessor
Before the C
compiler starts compiling a source code file, the file is processed by a
preprocessor. This is in reality a separate program (normally called
"cpp", for "C preprocessor"), but it is invoked
automatically by the compiler before compilation proper begins. The
preprocessor convert the source code file that have been write into another
source code file (as a "modified" or "expanded" source code
file). That modified file may exist as a real file in the file system, or it
may only be stored in memory for a short time before being sent to the
compiler.
Preprocessor
commands start with the pound sign ("#"). Two of the most
important preprocessor command:
• #define.
This is mainly used to define constants.
#define BIGNUM 1000000
specifies that
wherever the character string BIGNUM is found in the rest of the program,
1000000 should be substituted for it.
int a = BIGNUM;
int a = 1000000;
#define is used
in this way so as to avoid having to explicitly write out some constant value
in many different places in a source code file. This is important in case the
constant value need to change later on; it's much less bug-prone to change it
once, in the #define, than to have to change it in multiple places scattered
all over the code.
• #include.
This is used to access function definitions defined outside of a source code
file.
#include <stdio.h>
causes the
preprocessor to paste the contents of <stdio.h> into the source code file
at the location of the #include statement before it gets compiled. #include is
almost always used to include header files, which are files which mainly
contain function declarations and #define statements. In this case, we use
#include in order to be able to use functions such as printf and scanf, whose
declarations are located in the file stdio.h. C compilers do not allow a
function to be use unless it has previously been declared or defined in that
file; #include statements are thus the way to re-use previously-written code in
C programs.
The
compiler
After the C
preprocessor has included all the header files and expanded out all the #define
and #include statements (as well as any other preprocessor commands that may be
in the original file), the compiler can compile the program. It does this by
turning the C source code into an object code file, which is a file ending in
".o" which contains the binary version of the source code. Object
code is not directly executable, though. In order to make an executable, have
to add code for all of the library functions that were #included into the file
(this is not the same as including the declarations, which is what #include
does). This is the job of the linker
Written by,
Ng Swee Yan A/P Suresh Kumar
B031210103
No comments:
Post a Comment