Write a Program Insertion Sort using C .

• Insertion sort is also a simple sorting technique and is best suited for small data sets. But it is not suitable for large data sets. 
• but it is a better sorting technique than bubble sort and selection sort because the complexity of insertion sort is less than both.

• Time Complexity  
• Best  [ Ω(n) ]
• Average  [ θ(n^2) ]
• Worst  [ O(n^2) ]

Insertion Sort Algorithm

insertionSort(arr)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort

EXAMPLE :-

#include<stdio.h>

void Array(int arr[], int size)

{

for(int i=0; i<size; i++)

{

printf("%d ",arr[i]);

}

printf("\n");

}

void insertionSort(int arr[], int size)

{

for(int step=1; step<size; step++)

{

int key = arr[step];

int j=step-1;

while(key<arr[j] && j>=0)

{

arr[j+1] = arr[j];

--j;

}

arr[j+1]=key;

}

}

int main(){

int data[] = {90, 50, 14, 24, 20};

int size = sizeof(data)/sizeof(data[0]);

insertionSort(data, size);

printf("Sorted array in Asending order :\n");

            printf("***********************************\n");

Array(data, size);

}

OUTPUT

Sorted array in Asending order : *********************************** 14 20 24 50 90

Write a Program Simple Soring in C.

Simple Soring in C

• Sorting all the data of a data structure in a systematic order is called sorting. These are of two types, in ascending order or descending order. 
• The lowest value in ascending order is the store at the beginning of the Data List and the highest value at the end of the Data List, while the descending order has the opposite action. 
• That is, the data of the highest value is the first and the data of the lowest value is the next store in the list.

EXAMPLE :-

#include <stdio.h>

int main()

{

int num[5], i ,j ,temp;

for (i = 0; i < 5; i++)

{

printf("Enter the Number :: %d : ", (i+1));

scanf("%d", &num[i]);

}

for (i = 0; i < 5; ++i)

{

for (j = i + 1; j < 5; ++j)

{

if (num[i] > num[j])

{

temp = num[i];

num[i] = num[j];

num[j] = temp;

}

}

}

printf("Sorting Order Array : \n");

printf("****************************\n");

for (i = 0; i < 5; ++i)

printf("%d\n", num[i]);

return 0;

}

OUTPUT

Enter the Number :: 1 : 90 Enter the Number :: 2 : 85 Enter the Number :: 3 : 45 Enter the Number :: 4 : 25 Enter the Number :: 5 : 77 Sorting Order Array : **************************** 25 45 77 85 90

Write a Program of Bubble sort in C.

• This is the most common technique used in extreme use. In this, compare the first value of any Array to the second value of Array. 
• If the second value of Array is greater than the first value, then the second data is placed in the first place and the first place's data in the second place to be arranged in ascending order. 
• Then compare the second value of Array to the third value and if the third value is larger than the second value, then the third value is replaced by the second value and the third value instead of the second value.
• If the second value is not greater than the third value then no change is made in the location of the second and third values ​​of the Array.

Bubble Sort Algorithm

bubbleSort(arr)
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
end bubbleSort

Optimized Bubble Sort

bubbleSort(array)
  swapped <- false
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
      swapped <- true
end bubbleSort

EXAMPLE :-

#include <stdio.h>

void swap(int *p1, int *p2)

{

int temp = *p1;

*p1 = *p2;

*p2 = temp;

}

void bubbleSort(int arr[], int n)

{

int i, j;

for (i = 0; i < n-1; i++)

for (j = 0; j < n-i-1; j++)

if (arr[j] > arr[j+1])

swap(&arr[j], &arr[j+1]);

}

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", arr[i]);

printf("n");

}

int main()

{

int arr[] = {65, 35, 25, 50, 12, 61, 70};

int n = sizeof(arr)/sizeof(arr[0]);

bubbleSort(arr, n);

printf("Sorted array..... \n");

printArray(arr, n);

return 0;

}

OUTPUT

Sorted array..... 12 25 35 50 61 65 70

9.3.4 Switch Statement

Switch Statement in C.

• The switch statement is similar to if statement but case check is done instead of checking the condition. 
• When you come to a particular case, you write the statements that you want to execute inside the case. 
• Case is matched to an integer variable. 
• The same case goes to the execute case which matches the integer variable

Syntax :-

int caseNumber = n;

switch(caseNumber)

{

case 1:

/* Statements to be executed if caseNumber is 1 */

break;

case 2:

/* Statements to be executed if caseNumber is 2 */

break;

default:

/* Statements to be executed if caseNumber is not 1 & 2 */

break;

}

• When you set the caseNumber variable with an integer value and pass it in the switch statement, the same number that matches this number will be executed.
• For example, if you have passed 2 in case number then the case of second number will execute and all statements before the break will be executed.
• If a case does not match then the default case is execute. 
• If after each case the break statement is used then all the cases will be executed.
• You can also define the case with alphabets.

EXAMPLE :-

// Switch Statement in C.

#include <stdio.h>

void main()

{

int caseNumber;

printf("Enter a number : ");

scanf("%d",&caseNumber);

/* Passing the case number to switch to execute desired case */

switch(caseNumber)

{

case 1:

printf("\n First Switch Case executed..");

break;

case 2:

printf("\n Second Switch Case executed..");

break;

case 3:

printf("\n Third Switch Case executed..");

break;

case 4:

printf("\n Fourth Switch Case executed..");

break;

default:

printf("\n You can only enter 1,2,3 and 4");

break;

     }

}

OUTPUT

Third Switch Case executed..

9.3.3 else if

• If you want to put another condition between if and else, then you can do it by defining another if block.

Syntax

if(expression)

{

//execute your code

}

else if(expression n)

{

//execute your code

}

else

{

//execute your code

}

EXAMPLE :-

if(sudoAge > bkAge)

{

printf("Sudo is elder");

}

/* one more condition checked using else if */

else if(bkAge > sudoAge)

{

printf("Bk is elder");

}

else

{

printf("Both are equal");

}

9.3.2 If-Else Statement

• If else statement is considered as part of an if statement. 
• But else block and add to it. 
• The statement given in Else block is executed when the condition of if is false.

if(condition)

{

/* Statements to be executed when condition is true */

}

else

{

/* Statements to be executed when condition is false */

}

• As you know if the statements in if block are executed on if the condition is true. 
• But you can also decide what to do if the condition is false. 
• For this you use else block. This block always comes after the if block. 
• These statements are written in this block, which will be executed if the condition is false. 
• If if else statement is used in the above example then you can write it like this.

#include <stdio.h>

void main()

{

int sudoAge = 25;

int bkAge = 30;

/* Taking decision using if else statements */

if(sudoAge > bkAge)

{

printf("Sudo is elder:");

}

else

{

printf("Bk is elder:");

}

}

OUTPUT

Bk is elder:

9.3.1 If Statement

• If statement define a block by curly braces {}. 
• When the condition is true then the statement given in this block is executed.

if(condition)

{

/* Statements to be executed if condition is true */

}

• If the condition is false then skip the entire block to the compiler. 
• If the if statement is used in the above example, then the program can be written as

#include <stdio.h>

int main()

{

int sudoAge = 22;

int bkAge = 21;

/* Taking decision which variable holds bigger value using if statement */

if(sudoAge > bkAge)

{

printf("sudo is elder\n");

}

return 0;

}

• In the above example, a condition is used while using conditional operator. 
• If the age of Sudo is greater than Bk then the printf () statement given in the if statement will execute. 
• But if not, then this statement will not be executed.

sudo is elder

9.3 Introduction to C Decision Making

• You can decide which statements you want to execute in your program and which statements you want to skip. 
• This is called decision making. 
• Most decisions are done on a condition basis. 
• When a particular condition arrives, you can execute the statements you want. 
• For this, you use some built in statements. 
• Because these statements work with the conditions, they are also called conditional statements. 
• And because they control execution in the statement program, they are also called control statements. 
• Suppose you want to print the name of any of the two students whose age is over.
• How can you do this? See the program below.

#include <stdio.h>

int main()

{

sudoAge = 22;

bkAge = 21;

}

• In the above example, 2 students have been stored in age 2 variables. 
• But you only have to print the age of the student whose age is the highest. 
• In this situation you need to take a decision. 
• You can do this by any decision making statement (If, If-else, Switch).

9.2.1 Special C Operators

These are special operators in C Language.

• The Comma Operator
• Type cast Operator
• Reference operator or Address Operater ("&")
• Dereference operator ("*") or Pointer Operater
• Double Pointer operator ("**")
• sizeof operator

Below are the some important special operators in c language

Operators	Description
sizeof (var_name)	This operator returns the size of the variables in memory.
&	This returns the memory address of operator variables.
*	This operator returns the pointer of the variable.

EXAMPLE :-

// Special operators in C.

#include <stdio.h>

int main()

{

int p;

float q;

double r;

char s;

printf("Size of int=%lu bytes\n",sizeof(p));

printf("Size of float=%lu bytes\n",sizeof(q));

printf("Size of double=%lu bytes\n",sizeof(r));

printf("Size of char=%lu byte\n",sizeof(s));

return 0;

}

OUTPUT

Size of int = 4 bytes Size of float = 4 bytes Size of double = 8 bytes Size of char = 1 byte

9.1.9 Conditional (?:) Operator

• Conditional operator is also called ternary operator. 
• This is a short form of if-else statement.
• Its general structure is like this.

contion ? stmnt1 : stmnt 2;

If condition is true then the statement will return one or the statement will return 2. An

example of this is being given below.

5>3 ? true : false;

EXAMPLE :-

// Conditional (?:) operators in C.

#include <stdio.h>

int main()

{

int x=2, y ;

y = ( x ==2 ? 3 : 1 ) ;

printf("X value is : %d\n", x);

printf("Y value is : %d", y);

}

OUTPUT

X value is : 2 Y value is : 3

9.1.8 Increment/Decrements operators

• You can use increment / decrements operators to increase or decrease the value of any variable instantly by a number. 
• These are being given below.

Operators	Description
++ (increment)	This is a unary operator.  It increases the value of the operand by a number. When it seems before the operand, the value is increment first and is used later. When this operator operates after operand, the increment after the value of the operand is used.
--(decrements)	This is also a unary operator. This decreases the value of the operand by one number. When it is used before the operand, the value decreases before the value is used. When it is used after the variable, the value is first used and later decreases.

EXAMPLE :-

// Increment and Decrement operators in C.

#include <stdio.h>

int main()

{

int p = 20, q = 50;

float r = 20.5, s = 50.5;

printf("++p is = %d \n", ++p);

printf("--q is = %d \n", --q);

printf("++r is = %f \n", ++r);

printf("--s is = %f \n", --s);

return 0;

}

OUTPUT

++p is = 21 --q is = 49 ++r is = 21.500000 --s is = 49.500000