Selection Sort

SELECTION SORT IN C

We start Selection Sort by scanning the entire given list to find its smallest element and exchange it with the first element, putting the smallest element in its final position in the sorted list. Then we scan the list, starting with the second element, to find the smallest among the last n - 1 elements and exchange it with the second element, putting the second smallest element in its final position. Generally, on the ith pass through the list, which we number from 0 to n - 2, the algorithm searches for the smallest item among the last n - i elements and swaps it with A[i].

Consider the following element that is to be sorted using selection sort :  89, 45, 68, 90, 29, 34, 17.
The analysis of selection sort is straightforward. The input's size is given by the number of elements 'n' and the algorithm's basic operation is the key comparison A[j] < A[min]. The number of times it is executed depends only on the array's size.

 Selection Sort In C : Showing how elements are sorted

The above figure shows how given elements 89, 45, 68, 90, 29, 34, 17 are sorted according to selection sort. Each line corresponds to one iteration of the algorithm i.e. a pass through the list tail to the right of the vertical bar. An element in bold indicates the smallest element found. Elements to the left of the vertical bar are in their final positions and are not considered in this and subsequent iterations.

SELECTION SORT ALGORITHM

```SelectionSort(int a[],int n)
```
`   for i=0 to n-2`
`     min=i`
```
```
`     for j=i+1 to n-1`
`        if a[min] > a[j]`
`           min = j`
`   `
`     swap a[i] with a[min]`
```
```

SELECTION SORT PROGRAM IN C

```// Selection sort program in c

#include<stdio.h>

void SelectionSort(int [],int);

int main()
{
int a[20],i,n;
printf("Enter number of elements in array : ");
scanf("%d",&n);

// Inputting elements
for(i=0;i<n;i++)
{
printf("Enter number %d: ",i+1);
scanf("%d",&a[i]);
}

// Displaying Elements before selection sort
printf("Items in the array are : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}

//Applying selection sort
SelectionSort(a,n);

// Displaying elements after selection sort
printf("\nElements after selection sort : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}

void SelectionSort(int a[],int n)
{
int i,loc,j,min,temp;
for(i=0;i<=n-2;i++)
{
min = i;

for(j=i+1;j<=n-1;j++)
{
// Finding minimum element
if(a[min] >a[j])
{
min=j;
}
}

//Swapping a[i] with a[min]
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
```

BUBBLE SORT IN C

Back To Bubble Sort

Bubble Sort is a popular but inefficient sorting algorithm.  Bubble Sort is another brute-force application to the sorting problem that compares adjacent elements of the list and exchange them if they are out of order. By doing it repeatedly, we end up "bubbling up" the largest element to the last position on the list. The next pass bubbles up the second largest element, and so on until, after n - 1 passes, the list is sorted. Pass i (0 <= i <= n - 2) of bubble sort can be represented by the following diagram:

Consider element to be sorted are : 89, 45, 68, 90, 29, 34, 17

 Quick Sort In C : Showing how elements are sorted

First two passes of bubble sort on the given list 89, 45, 68, 90, 29, 34, 17 is shown in above figure.  A new line is shown after a swap of two elements is done. The elements to the right of the vertical bar are in their final positions and are not considered in  subsequent iterations of the algorithm.

BUBBLE SORT ALGORITHM

`// Algorithm for Bubble Sort`
`BubbleSort(int a[],int n)`
```  for i=0 to n-2
```
`    for j=0 to n-2-i`
`      if a[j] > a[j+1]`
`        swap a[j] with a[j+1]`

BUBBLE SORT PROGRAM IN C

```// Bubble sort program in c

#include<stdio.h>

void bubblesort(int a[],int n);

int main()
{
int a[20],i,n;
printf("Enter number of elements in array : ");
scanf("%d",&n);

// Inputting elements
for(i=0;i<n;i++)
{
printf("Enter number %d: ",i+1);
scanf("%d",&a[i]);
}

// Displaying Elements before bubble sort
printf("Items in the array are : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}

//Applying bubble sort
bubblesort(a,n);

// Displaying elements after bubble sort
printf("\nElements after bubble sort : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}

void bubblesort(int a[],int n)
{
int i,j;
for(i=0; i<=n-2; i++)
{
for(j=0;j<=n-i-2;j++)
{
// Swapping elements
if(a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}

```

GOOD PROGRAMMING PRACTICES - FUNDAMENTALS

• Every function should be preceded by a comment describing the purpose of the function.
• Add a comment to the line containing the right brace, } that close every function, including the main(). This helps in determining that the function is ended.
• Indent the entire body of each function. This indentation emphasizes the functional structure of a program and helps make program easier to read.
• Set a convention for the size of indent you prefer and then uniformly apply that convention.
• Choosing meaningful variable name helps make a program self-documenting i.e fewer comments are needed.
• Multiple-word variable names can help make a program more readable.Separate the words with underscore eg : comp_psyche or good_programming_practices.
• Place a space after each comma to make a program more readable.
• Place spaces on either side of binary operator. This makes the operator stand out and makes the program more readable.
• Although it is allowed that we can have multiple statement in a single line but to make program more readable there should be only one statement per line in a program.

GOOD PROGRAMMING PRACTICES - CONTROL STRUCTURES

• Indent both body statement of an if...else statement.
• If there are several level of indentation, each level should be indented with same additional amount of space.
• When performing division by an expression whose value could be zero, explicitly test this case and handle it appropriately in your program ( such as printing an error message ) rather than allowing the fatal error to occur.
• In a sentinel-controlled loop, the prompts requesting data entry should explicitly remind the user what the sentinel value is.
• Too many levels of nesting can make a program difficult to understand. As a rule, try to avoid using more than three levels of nesting.
• Limit the size of the control statement headers to a single line if possible.
• Although the case clauses and the default case clause in a switch statement can occur in any order but its advisable to place the default clause at last.
• In a switch statement when the default clause is last then the break statement is not required.

GOOD PROGRAMMING PRACTICES - FUNCTION

• Familiarize yourself with rich collection of functions in C standard library.
• Although It is not incorrect to do so but do not use the same names for a function's arguments and the corresponding parameters in function definition. This helps avoid ambiguity.
• Choosing meaningful function names and meaningful parameter names makes program more readable and helps avoid excessive use of comments.
• Parameter names are sometimes included in function prototype for documentation purposes. The compiler ignore these names.
• Use only uppercase letters in the names of enumeration constants to make these constants stand out in a program and to indicate that enumeration constants are not variable.

GOOD PROGRAMMING PRACTICES - ARRAY

• Defining the size of each array as a symbolic constant make program more readable.
• Use only uppercase letter for symbolic constant names. This makes these constants stand out in a program and reminds you that symbolic constants are not variable.
• In multi-word symbolic constant names, separate the words with underscores for readability.
• Strive for program clarity. Sometimes it may be worthwhile to trade off the most efficient use of memory or processor time in favor of writing clearer programs.
• When passing an array to a function, also pass the size of the array. This helps make function reusable in many programs.

GOOD PROGRAMMING PRACTICES - STRING

• When storing a string of characters in a character array be sure that the array is large enough to hold the largest string that will be stored.
• Familiarize yourself with the various predefined string function. This helps in achieving task easily.
• When using functions from the string-handling library, include the <string.h> header.

GOOD PROGRAMMING PRACTICES - POINTERS

• Its preferable to include the letters Ptr in pointer variable names to make it clear that these variables are pointer and thus need to be handled appropriately.
• Initialize pointer to prevent unexpected result.
• If a variable does not change in the body of a function to which it is passed, the variable should be declared const to ensure that it is not accidentally modified.
• Pass large objects such as structures using pointers to constant data to obtain the performance benefits of pass-by-reference.

GOOD PROGRAMMING PRACTICES - STRUCTURE AND UNION

• Always provide a structure tag name when creating structure type. The structure type name is convenient for declaring new variables of the structure type later in the program.
• Do not use spaces around  '->' and '.' operators. Omitting spaces helps emphasize that the expressions the operators are contained in are essentially single variable names.
• Passing structure by reference is more efficient than passing structure by value.
• Use typedef to help make a program more protable.
• Capitalize the first letter of the typedef names to emphasize that they are synonyms for other types names.
• Using typedef can help make a program more readable and maintainable.

C Programming In Linux

C Programming in Linux : In this tutorial we are going to study how to write, compile and run c program in Linux. Linux Wall command and make command  is also explained.

HOW TO WRITE C PROGRAM IN LINUX

Back to content

A c program is written in a text editor and is saved with ".c" extension. ".c" helps Unix or Linux OS(operating system) to identify that it is a C program.
I am assuming that all of you can have an access to a text editor and you know how to write in it and save it.

Lets write our first c program :

#include<stdio.h>
int main()
{
printf("Yepeeeeeee this is my first C program\n"); // Displays the string as output
return 0; // tell the OS that the program exited without errors
}

Type the above code in any editor and save it with ".c" extension say "firstprogram.c"

Explanation :

The execution of a C program starts with main() function.

// ( Double slash ) is a single line comment and is ignored by the compiler. It is used by the programmer to explain the working of the programs. so that other programmer who reads the program written by him would understand what the program is exactly doing.

/*

Written anything
.......

*/

The above syntax is for multiline comment i.e any text written in between is ignored by the compiler.

Now what does first line #include<stdio.h> mean :

The first line may be confusing, but it’s just a C syntax that tells the compiler to include headers for a standard input/output (I/O) library named "stdio.h". This header file is added to the program when it is compiled. It is located at /usr/include/stdio.h and it defines several constants and function prototypes for corresponding functions in the standard I/O library. Since the main() function uses the printf() function from the standard I/O library, a function prototype is needed for printf() before it can be used. This function prototype (along with many others) is included in the "stdio.h" header file. A lot of the power of C comes from its extensibility and libraries.

In  printf("Yepeeeeeee this is my first C program\n") we have used "\n" this is nothing but a escape sequence and is known as newline character and it causes the cursor to move to the start of the next line.

HOW TO COMPILE C PROGRAM IN LINUX

Back to content

Linux has a compiler named CC ( The C Compiler ) for compiling the C programs written in a text editor. Most unix or linux version also contain The GNU Compiler Collection (GCC) which is a free C compiler that translates C into machine language that a processor can understand.A compiler converts a high-level language into machine language.

How to compile  C program in Linux:

Note : The followed command should be issued carefully in terminal and keep in mind of the directory in which you are working. i.e if you have saved your file in media directory then in terminal you should type cd /media to go to that directory and then issue the following command. If you launch terminal from your taskbar or menu then the working directory is by default /home/username. It would be a better idea to open your terminal from the same directory in which your file is saved.

For compiling a C program you can simply type :

cc firstprogram.c or
gcc firstprogram.c

Now what does the above two statement does :

This will try to compile firstprogram.c and if successful will produce a runnable file called "a.out" which is a default name. If you want to give the runnable file a better name you can type :

cc firstprogram.c -o firstprogram ( or cc firstprogram.c -o testprog.out )
gcc firstprogram.c -o firstprogram ( or gcc firstprogram.c -o firstprogram.out )

This will compile firstprogram.c and  create a  runnable file firstprogram
If you notice we have excluded the extension ".out" but not to worry with extension or without extension your runnable or executable file will work.

LINUX MAKE COMMAND

Back to content

UNIX or Linux also includes a very useful program called "make". Make allows very complicated programs to be compiled quickly, by reference to a configuration file (usually called Makefile). If your C program is a single file, you can usually use "make" by simply typing :

make firstprogram

This will compile firstprogram.c and put the executable code in firstprogram
"make" does the same task what cc firstprogram.c -o firstprogram or gcc firstprogram.c -o firstprogram does.

LINUX WALL COMMAND

Back to content

The -Wall option causes the compiler to warn you about legal but dubious code constructs, and will help you catch a lot of bugs very early. To use -Wall option you can type :

gcc -Wall -c firstprogram.c or
cc -Wall -c firstprogram.c

If you want to be even more specific you can type :

gcc -Wall -Wstrict-prototypes -ansi -pedantic -c firstprogram.c or
cc -Wall -Wstrict-prototypes -ansi -pedantic -c firstprogram.c

The -Wstrict-prototypes option means that the compiler will warn you if you haven't written correct prototypes for all your functions. The -ansi and -pedantic options cause the compiler to warn about any non-portable construct (i.e  constructs that may be legal in gcc but not in other standard C compilers. We should try to avoid such features).

Note - Running the commands :

gcc -Wall -c firstprogram.c or
cc -Wall -c firstprogram.c

gcc -Wall -Wstrict-prototypes -ansi -pedantic -c firstprogram.c or
cc -Wall -Wstrict-prototypes -ansi -pedantic -c firstprogram.c

produces object file named firstprogram.o

So the next step is to make a runnable or executable file from the object file. To make an runnable or executale file type :

gcc firstprogram.o -o firstprogram or
cc firstprogram.o -o firstprogram

This produces an executable file named firstprogram

To create an executable file directly without producing an object file. You can type :

gcc -g -Wall -o firstprogram firstprogram.c or
cc -g -Wall -o firstprogram firstprogram.c

This produces an executable file named firstprogram without producing an object file firstprogram.o

HOW TO RUN C PROGRAM IN LINUX

Back to content

Now that we are done with writing and compiling our code. Lets run it. You can run your code by simply typing the runnable or executable file name i.e type :

firstprogram

If in case the above command show error and does not execute your runnable file then you can type :

./firstprogram

This tells the compiler that the executable file is in the current working directory.

HOW DO YOU FEEL

Back to content

Now that you have executed your first C program. Tell us how do you feel by simply dropping a comment in the comment box.