DATA STRACTURE'S
¢ Stacks: Stack's is a Lenoir Data structure. stacks are
- Extensively used in computer application's as a system soft
-ware (such as complier's o.s)
" LIFO-Last In First Out
For eg: when one function called anther function and presses some parameters, these parameters are passed using the stack.
A stack is called Last In First Out [LIFO] because the item that entered the stack last is the first one to get out.
" In these stack's there are two operation's is their
1. PUSH (write) operation
2. POP (read) operation
A stack is the best eg: is "LIBRARY". We assume that in shyly the stack is empty the bellow operation is shows who to read and write in a stack
OPERATION AFTER THE OPERATION
PUSH(A) A
PUSH(B) A,B
POP(B) A
PUSH(C) A,C
PUSH(D) A,C,D
PUSH(E) A,C,D,E
POP(E) A,C,D
POP(D) A,C
POP(C) A
POP(A) EMPTY
¢ Application's of stack
1. It can be used in function cells'
2. It can be used in implement a clacqulater, by sorting the
Apperans&operators
3. A stack is useful in writing recursive calls
4. A stack is useful for the compilers (or) o.s
Sravan cse 2nd batch
¢ Queue's : A queue is a linear data structure .it is a linear sequential
-list of items that are accessed in the order of First in First out [LIFO]
-that is, the first item inserted in a queue in all so the first item is accessed, the second item inserted in queue is all so second one to be accessed, and the last one to be inserted is also the last one to be accessed. We can't store (or) access the items in a queue is arbitrarily (or) in any random fashion.
For eg: a queue is used in Train reservation counters, Bank's, Bus counters
These are two operation's is in queue
1. Write operation
2. Read operation
The write operation adds a new item to the queue, whereas the read item reads one item from the queue. The bellow figure shows how the queue operation is going.
OPERATION AFTER THE OPERATION
Write (a) a
Write (b) a,b
Write (c) a,b,c
Read(a) b,c
Write (d) b,c,d
Read(b) c,d
Read(c) d
Write (e) d,e
Read(d) e
Read(e) Empty
In order to implement the write and read operation of a queue, two pointers that are started and end operation are required. One pointer [start] points at the current start of the queue. The other pointer [end] point at the current end of the queue.
¢ Circular list/queue:
A list/queue can also be Circular it is called as Circular list/queue in queue the items from a queue get deleted, the space for that item is reused that is it is not reused. Those queues positions are continue to be empty. This problem is salved by a Circular linked list. The items in a Circular list are arranged to form a Circular shape. That is why a Circular list doesn't have a beginning or end. The logical representation of a Circular queue is shown bellow
Sravan cse 2nd batch
Library functions:
The "c language" is a number of library functions that performs various task the ANSI-the ANSI commit has standardized header file which contain these functions
1. <Math.h> mathematical functions.
2. <Stdio.h> standard I/O library function.
3. <Stdlib.h> standard library function.
4. <String.h> string manipulation function.
5. <Time.h> time manipulation function.
Weite some dynamic memory allocation functions?
Process of allocation memory during rentime is called dynamic memory allocation
The following functions are used in "c"
1.malloc ()
2.calloc ()
3.free ()
4.realloc ()
Alloc family of functions are declared in followeing header file i.e; stdlib.h and alloc.h
Sravan cse 2nd batch
HANDLING STRING'S
String:
A string is an any array of characters any group characters defined between double quotation marks is a constant string.
Eg: "well done"
Character strings are offen used to build mining full redable programs the common operations per famed on character strings are
1.reading and writing strings
2.combinigstring together
3.copying one string to another
4.comparing strings
Declaration and insulation of string variables: -
A string variable is any valed c variable main and is always declared as an array.
Syntax: char string_name [size];
Eg: char city [10]:
1.reading strings: -
The input function scan can be used with personage of % format specification to read in a string of char's
Eg: char address [15];
Scan ["%s ", address];
Writing strings: -
We have used extensively the printf function with %s format to print strings to the screen, the format %s can be used to display an array of chars that is terminated by the null chars.
Eg: printf ("%s", name)
2. Combinigstring together: -
We can't assign one string to another string directly; we can't join two strings together by the simple arithmetic addition
Eg: string3=string1+string2;
The parses of combining two strings together is called concatenation OR putting string together
3. Copying one string to another: -
1.when the field with is less than the length of the string, the entair string is printed
2.the inter value on the right side of the decimal point specifies the no of char's to be
- Printed Sravan cse 2nd batch
3.when the no of char's to be printed is specified as zero [0], nothing is
- Printed
4.the mines sign in the specification causes the string to be printed left
- Justified
4.comparition two strings: -
"C" doesn't permit the comparison of two strings directly that is the
Statement such as
If (name1==name2)
Are not permeated it is necessary to comparison of two strings to be tested,
Character-by-character.
Sravan cse 2nd batch
STRING HANDLING FUNCTION'S
"C" support's a large number of string handling function that can be used to carry out many of the string manipulations.
FUNCTION ACTION
Str cat () Combining two strings
Str cmp () Compares two strings
Str cpy () Copy one string to another
Str Len () Finds length of a string
1.String concatenation: -
The strcat function joints two strings toghather
FOR E.g.
: Syntax:
Strcat (str1, str2);
2.Strcmp function: -
String comparison compares two string identified by the arguments and has a value zero if they rent between the no matching characters in the strings
For E.g.:
Strcmp (name,"C.S.E.");
Syntax:
Strcmp (str1, str2);
String1&string2 may be string variables or string constants.
3.strcpy function: -
The strcpy function works almost like a string assignment operator
For E.g.:
Strcpy (city,"HYD");
: Syntax:
Strcpy (str1, str2):
4.strlen function: -
These function countess and returns the number of character in a string
For E.g.:
N=strlen ("GJC");
: Syntax:
N=strlen (string);
Sravan cse 2nd batch
STRACTURES
A stricture is a collection of data items or data variables. a stricture defines any where in the programme
: Syntax: -
Struct tag_name;
{
Type1 data 1;
Type2 data 2;
Type3 data 3;
.
.
.
.
Typen data n;
}
For E.g.:
Struct student:
{
Int reg_no;
Char name;
Float avg;
}
They are 4 types of strictures variables is there
1.Declaration of stricture variables
2.comparision of structures variables
3.array of structures
4.stracture with in stricture
Sravan cse 2nd batch
1.Declaration of stricture variables: -
Stricture is user defined data type we can declare strictures variables using the tag name or structure name any where in the programme
Syntax:
Struct tag_name variable list; [data type]
E.g.
Struct emp
{
Int emp_code;
Char name [20];
Float salary;
};
2.comparision of structures variables: -
OPERATION MENINING
Person1=person2 Assign person2 to person1
Person1==person2 Compare all members of person1 and person2, return if they are equal, other wise "0" [zero]
Person1! =Person2 Returen1 if they are not equal, other wise "0" [zero]
3.array of structures: -
We use structures to describe the format of a no' of related variables analizeining the marks obtained by a class of students, we use to describe student name marks may declare on array of student and each element of the array representing a structure variable
Syntax:
Struct marks
{
Int sub 1;
Int sub2;
Int sub3;
};
Main ()
{
Stract struct marks student [3]={{45,68,81},{75,53,69},{57,36,71}};
Sravan cse 2nd batch
4.stracture with in stricture: -
Structure with in a structure means nesting of structure's .a structure member it self may be a structure i.e; making structure as member of another structure, then these can be accessed by writing variable member, sub member.
Syntax: -
Struct salary
{
Char name [10];
Char dept [10];
int basic_ pay;
int dearness_allowance;
int house_rent_allowence;
int city_allowence;
}
Employee;
Sravan cse 2nd batch
RECURSION
When a called function in turn calls another function a praises of 'changing' accurse. Recursion is a special case of these process, where a function calls it self
A very simple ex recursion is shown bellow
Main ()
{
Printf ("this is an example of recursion \n");
Main ()
}
When excuted, these programme will produce an output something like these.
This is an example of recursion
Executed is terminated abruptly, otherwise the execution will continue definitely
Sravan cse 2nd batch
SORTING AND SEARCHING TECNIQUES
Sorting: -
Sorting means rearranging in a pree defined the sequence.
Sorting tequncs have a great significance in computer applications.for instance, concedar the flowering requirements. Those require the use of sorting techniques.
(a) arrange the list of students in the descending order of average marks obtained
(b) sort the recorder in the employee file in the order of employee names
(c) sort the array sales persons in the increasing order of their sales figures
a number of sorting algorithms are available. There are 4 types of sorting techniques are there
1.exchange sort.
2.selaction sort.
3.quict sort.
4.tree sort.
1.exchange sort: - exchange sort is called as a bubble sort
Bubble sort is an Eg. Of exchange sort techniques .the name bubble sort presents an interesting analogy consider purring water in tank water is purred, bubble a emerge each bubble selfless down at some place, after a shart time.
Bubble sort is the simplest to understand but is very slow in perfume trams. The bubble sort algorithm always performs the same number of steps regardless.
To sort n value bubble sort always requires [n*(n-1)/2] steps
[10,000*(10,000-1)/2]
I.e.; 49,995,000 steps
Sravan cse 2nd batch
2.selaction sort.
To understand how it was imagine that n items list .the items is compared with the remaining (n-1) items, and which ever of all these is lower is put in the first option then the second item is taken and compare with the remaining (n-2) if an item with a value less than that of the second item his found in the (n-2) items, it is swapped with the second item of the list, and so on.
It is also requires a total of [n*(n-1)/2] steps/compressions.
Selection sort work faster has compared to exchange sort
3.quict sort.
Quick sort is the most efficient sorting technique, given a list of n elements which is to be sorted quick sort identifies an item (say k) in the list. A value less than (<) k to the left of k. and all the items that have a value greater than (>) to the right of the k.
We now have two sub list say list1 and list2 in the main list with K standing between list1 and list2,we identify new K list1 as well as list2.list1 and list2 each will be partied for the in to two sub list and so Ont.'s continues until the entire list is exhausted(executed) K can bay where in the list,but is generally most efficient to have it in the middle of the list
Imaging a list of numbers as fallow
43 33 11 55 77 90 40 60 99 22 88 65
Step 1: - find out the final position of one of the number in the list.it can be any number in the list.we start with the first number i.e. 43 sorting with the last number that is 65 scan the list from right to left comparing each number with 43 and stopping at the first number that is less that 43. We can "C" this number is 22 so swap 43 with 23
The list now looks as follows
22 33 11 55 77 90 40 60 99 43 88 65
Step2: - the number 88 and 65 to the right of 43 are greater than 43.starting with 22 scan the list in to the opposite direction (left to right) comparing each number 43 and swapping at the first number.which is greater than 43.this number is 55
The new list looks as follows.
22 33 11 43 77 90 40 60 99 55 88 65
Step3: - the number 22,33 and 22 are all to the left of 43 and are less than 43.starting with 55 scan the list in the original direction (right to left) stopping at the first number i.e. ; less than 43 it is 40,so swap 43 and 40
The new list now looks are as follows
22 33 11 40 77 90 43 60 99 55 88 65
Step4: - the number to the right of 43 are greater than 43.starting 40 scan the list left to right.staping at the first number which is greater than 43 .it is 77 so swap 77 and 43.
The new list looks as follows
22 33 11 40 43 90 77 60 99 55 88 65
Sravan cse 2nd batch
The number to the left of 43 are less than 43 and all the number to the right of 43 are greater than 43.over original number 43 is at it's correct started position.we now split the list in to halves one containing the items that are to the left of 43 and other containing the are to the right of 43.
4.tree sort: - the tree sort is based on the mechanism of sorting a binary tree in to its proper order.it is related to placing a value in it's appropriate position os the tree binary tree as a root at the top and elements down the tree. In tree sorting we organize in althea elements in such a position that they are sorted from left to right.
Q:- write the time and space complexicite,time complexicite for all sorting techniques
sorting techniques case Time complexicite Space complexicite
1.selection sort average 0 (n2) 0
Worest 0 (n2) 0
2.Bubble sort Average 0 (n2) 0
Worest 0 (n2) 0
3.insertion sort Average 0 (n2) 0
Worest 0 (n2) 0
4.merge sort Average 0 (n log n) 0 (n)
Worest 0 (n log n) 0 (n)
5.Quick sort Average 0 (n log n) 0 (n)
Worest 0 (n log n) 0 (n)
Sravan cse 2nd batch
SEARCHING TEACHNIQUES
SEARCHING TEACHNIQUES: - searching for information is a very common and widely used in computer applications.there are numerous occasions when information needs to be searched for
Eg:
a. Find out the list of employee who earns more than rs.10, 000 for month.
b. List all the customers who were serviced by a particular sales person in the last month
There are two searching methods is available
1.secuentiol search (al so called as linear search)
2.Binary search
1.sequentiol search: - sequential search in the traditional mechanism of searching for information .it is very simple under stands, but can be very poor in performance some times.as the name says, the process of searching for information in a sequential search is sequential (or one ofter the other) given a list so items, to find if a particular item exist (or does not exist) in the list.the following sequential algorithm can be used
Sequential algorithm: -
1.start with a number I=1
2.if there are still more items in the list. Compare the 1th element in the list with the item to be searched
else
Item is not found in the list. Stop
3.if a match is found
The item is found in the list. Stop
else
odd one 1 to I,and go back to step 1.
The important point in this algorithm is that we strat with the first item in the list, and go up to the end of the list, or until the item to be searched is found which ever is earlier.
The number times this algorithm is likely it be executed, depending on the best average and worst possible case. We assume that the list contains "N"items
case Meaning Number of interation
Best The item to be searched is the first item in the list 1
Average The item to be searched is found some were close to be middle of the list N/2
Worst The item to be searched is the last item in the list it or a does not existent at all N
Sravan cse 2nd batch
If we have 10,000 items in a listen an average it would required 10,000/2.i.e; 5,000 interation. Consider an array named arr, containing 1,000 integers. We can use the following function to search for a specific item (say item) in that array.
Syntax: -
Sequentiol_search (int item)
{
Int I;
For (I=0;I<1000;I++)
{
if (arr[I]==item)
{
Printf ("item found at the position %d in the arr \n",I+1);
return;
}
}
Printf ("item not found in the arr \n");
}
The function is quite simple to under stands.it basically scans through all the elements of the array one by one. Starting with the first element of the array.
Binary search: - Binary is a vast improvement over the sequential search. It can't always be used for binary search the item in the list must be in stored order
(Either ascending or descending) This is a pre-requisite for binary search. It the list to be searched for a specific item is not stored, binary search fails
Binary search is called as divided-and-conquer method. Assume that a list contains 1,000 elements. Which are stored in an ascending order of their values. An item "x" is to be searched in the list. Then the approach used by the binary search algorithm is as follows
Steps 1: - devoid the original list into two equals sized logical values. Let us call then of half1 and half 2. In this case the original1, 000 elements list will be split into two values. Each containing 500 elements
Step 2: - compare x with the last (I.e.; 500th ) elements of half1. There are 3 possibilities.
a. The value of 'x' matches with that of the 500 element of half1,the search is successful their four display an appropriate message and stop processing.
b. The value of 'x' is greater than that of the 500 element of . note that over list was originally sorted in the ascending order thus if the values of 'x' is greater than the last elements of half1,it means that 'x' is definitely not one of the first 500 elements in the 10,000 elements array.
c. The values of 'x' is less than that of the 500 elements of half1.note that over list was originally stored in the ascending order. Thus if the values of 'x' is less than the last elements of half1,it means that if 'x' is in the list . it must definitely be one of the first 500 elements in the 1,000 elements array.
Sravan cse 2nd batch
Out come Next action
a.x=last element of haif1 1.stop processing
b.x>last element of half1 2.search of x with in half2
c.x<last elements of half1 3.search of x half2
Int binary_search (int arr [], int item)
{
Int low=0,heigh=999,mid;
While (low<=high)
{
Mid = (low+high)/2;
If (item<arr [mid])
High=mid-1;
else
if(item>arr[mid])
low=mid+1;
else
Return_mid;
}
Return-1;
}
Sravan cse 2nd batch
¢ Stacks: Stack's is a Lenoir Data structure. stacks are
- Extensively used in computer application's as a system soft
-ware (such as complier's o.s)
" LIFO-Last In First Out
For eg: when one function called anther function and presses some parameters, these parameters are passed using the stack.
A stack is called Last In First Out [LIFO] because the item that entered the stack last is the first one to get out.
" In these stack's there are two operation's is their
1. PUSH (write) operation
2. POP (read) operation
A stack is the best eg: is "LIBRARY". We assume that in shyly the stack is empty the bellow operation is shows who to read and write in a stack
OPERATION AFTER THE OPERATION
PUSH(A) A
PUSH(B) A,B
POP(B) A
PUSH(C) A,C
PUSH(D) A,C,D
PUSH(E) A,C,D,E
POP(E) A,C,D
POP(D) A,C
POP(C) A
POP(A) EMPTY
¢ Application's of stack
1. It can be used in function cells'
2. It can be used in implement a clacqulater, by sorting the
Apperans&operators
3. A stack is useful in writing recursive calls
4. A stack is useful for the compilers (or) o.s
Sravan cse 2nd batch
¢ Queue's : A queue is a linear data structure .it is a linear sequential
-list of items that are accessed in the order of First in First out [LIFO]
-that is, the first item inserted in a queue in all so the first item is accessed, the second item inserted in queue is all so second one to be accessed, and the last one to be inserted is also the last one to be accessed. We can't store (or) access the items in a queue is arbitrarily (or) in any random fashion.
For eg: a queue is used in Train reservation counters, Bank's, Bus counters
These are two operation's is in queue
1. Write operation
2. Read operation
The write operation adds a new item to the queue, whereas the read item reads one item from the queue. The bellow figure shows how the queue operation is going.
OPERATION AFTER THE OPERATION
Write (a) a
Write (b) a,b
Write (c) a,b,c
Read(a) b,c
Write (d) b,c,d
Read(b) c,d
Read(c) d
Write (e) d,e
Read(d) e
Read(e) Empty
In order to implement the write and read operation of a queue, two pointers that are started and end operation are required. One pointer [start] points at the current start of the queue. The other pointer [end] point at the current end of the queue.
¢ Circular list/queue:
A list/queue can also be Circular it is called as Circular list/queue in queue the items from a queue get deleted, the space for that item is reused that is it is not reused. Those queues positions are continue to be empty. This problem is salved by a Circular linked list. The items in a Circular list are arranged to form a Circular shape. That is why a Circular list doesn't have a beginning or end. The logical representation of a Circular queue is shown bellow
Sravan cse 2nd batch
Library functions:
The "c language" is a number of library functions that performs various task the ANSI-the ANSI commit has standardized header file which contain these functions
1. <Math.h> mathematical functions.
2. <Stdio.h> standard I/O library function.
3. <Stdlib.h> standard library function.
4. <String.h> string manipulation function.
5. <Time.h> time manipulation function.
Weite some dynamic memory allocation functions?
Process of allocation memory during rentime is called dynamic memory allocation
The following functions are used in "c"
1.malloc ()
2.calloc ()
3.free ()
4.realloc ()
Alloc family of functions are declared in followeing header file i.e; stdlib.h and alloc.h
Sravan cse 2nd batch
HANDLING STRING'S
String:
A string is an any array of characters any group characters defined between double quotation marks is a constant string.
Eg: "well done"
Character strings are offen used to build mining full redable programs the common operations per famed on character strings are
1.reading and writing strings
2.combinigstring together
3.copying one string to another
4.comparing strings
Declaration and insulation of string variables: -
A string variable is any valed c variable main and is always declared as an array.
Syntax: char string_name [size];
Eg: char city [10]:
1.reading strings: -
The input function scan can be used with personage of % format specification to read in a string of char's
Eg: char address [15];
Scan ["%s ", address];
Writing strings: -
We have used extensively the printf function with %s format to print strings to the screen, the format %s can be used to display an array of chars that is terminated by the null chars.
Eg: printf ("%s", name)
2. Combinigstring together: -
We can't assign one string to another string directly; we can't join two strings together by the simple arithmetic addition
Eg: string3=string1+string2;
The parses of combining two strings together is called concatenation OR putting string together
3. Copying one string to another: -
1.when the field with is less than the length of the string, the entair string is printed
2.the inter value on the right side of the decimal point specifies the no of char's to be
- Printed Sravan cse 2nd batch
3.when the no of char's to be printed is specified as zero [0], nothing is
- Printed
4.the mines sign in the specification causes the string to be printed left
- Justified
4.comparition two strings: -
"C" doesn't permit the comparison of two strings directly that is the
Statement such as
If (name1==name2)
Are not permeated it is necessary to comparison of two strings to be tested,
Character-by-character.
Sravan cse 2nd batch
STRING HANDLING FUNCTION'S
"C" support's a large number of string handling function that can be used to carry out many of the string manipulations.
FUNCTION ACTION
Str cat () Combining two strings
Str cmp () Compares two strings
Str cpy () Copy one string to another
Str Len () Finds length of a string
1.String concatenation: -
The strcat function joints two strings toghather
FOR E.g.
: Syntax:
Strcat (str1, str2);
2.Strcmp function: -
String comparison compares two string identified by the arguments and has a value zero if they rent between the no matching characters in the strings
For E.g.:
Strcmp (name,"C.S.E.");
Syntax:
Strcmp (str1, str2);
String1&string2 may be string variables or string constants.
3.strcpy function: -
The strcpy function works almost like a string assignment operator
For E.g.:
Strcpy (city,"HYD");
: Syntax:
Strcpy (str1, str2):
4.strlen function: -
These function countess and returns the number of character in a string
For E.g.:
N=strlen ("GJC");
: Syntax:
N=strlen (string);
Sravan cse 2nd batch
STRACTURES
A stricture is a collection of data items or data variables. a stricture defines any where in the programme
: Syntax: -
Struct tag_name;
{
Type1 data 1;
Type2 data 2;
Type3 data 3;
.
.
.
.
Typen data n;
}
For E.g.:
Struct student:
{
Int reg_no;
Char name;
Float avg;
}
They are 4 types of strictures variables is there
1.Declaration of stricture variables
2.comparision of structures variables
3.array of structures
4.stracture with in stricture
Sravan cse 2nd batch
1.Declaration of stricture variables: -
Stricture is user defined data type we can declare strictures variables using the tag name or structure name any where in the programme
Syntax:
Struct tag_name variable list; [data type]
E.g.
Struct emp
{
Int emp_code;
Char name [20];
Float salary;
};
2.comparision of structures variables: -
OPERATION MENINING
Person1=person2 Assign person2 to person1
Person1==person2 Compare all members of person1 and person2, return if they are equal, other wise "0" [zero]
Person1! =Person2 Returen1 if they are not equal, other wise "0" [zero]
3.array of structures: -
We use structures to describe the format of a no' of related variables analizeining the marks obtained by a class of students, we use to describe student name marks may declare on array of student and each element of the array representing a structure variable
Syntax:
Struct marks
{
Int sub 1;
Int sub2;
Int sub3;
};
Main ()
{
Stract struct marks student [3]={{45,68,81},{75,53,69},{57,36,71}};
Sravan cse 2nd batch
4.stracture with in stricture: -
Structure with in a structure means nesting of structure's .a structure member it self may be a structure i.e; making structure as member of another structure, then these can be accessed by writing variable member, sub member.
Syntax: -
Struct salary
{
Char name [10];
Char dept [10];
int basic_ pay;
int dearness_allowance;
int house_rent_allowence;
int city_allowence;
}
Employee;
Sravan cse 2nd batch
RECURSION
When a called function in turn calls another function a praises of 'changing' accurse. Recursion is a special case of these process, where a function calls it self
A very simple ex recursion is shown bellow
Main ()
{
Printf ("this is an example of recursion \n");
Main ()
}
When excuted, these programme will produce an output something like these.
This is an example of recursion
Executed is terminated abruptly, otherwise the execution will continue definitely
Sravan cse 2nd batch
SORTING AND SEARCHING TECNIQUES
Sorting: -
Sorting means rearranging in a pree defined the sequence.
Sorting tequncs have a great significance in computer applications.for instance, concedar the flowering requirements. Those require the use of sorting techniques.
(a) arrange the list of students in the descending order of average marks obtained
(b) sort the recorder in the employee file in the order of employee names
(c) sort the array sales persons in the increasing order of their sales figures
a number of sorting algorithms are available. There are 4 types of sorting techniques are there
1.exchange sort.
2.selaction sort.
3.quict sort.
4.tree sort.
1.exchange sort: - exchange sort is called as a bubble sort
Bubble sort is an Eg. Of exchange sort techniques .the name bubble sort presents an interesting analogy consider purring water in tank water is purred, bubble a emerge each bubble selfless down at some place, after a shart time.
Bubble sort is the simplest to understand but is very slow in perfume trams. The bubble sort algorithm always performs the same number of steps regardless.
To sort n value bubble sort always requires [n*(n-1)/2] steps
[10,000*(10,000-1)/2]
I.e.; 49,995,000 steps
Sravan cse 2nd batch
2.selaction sort.
To understand how it was imagine that n items list .the items is compared with the remaining (n-1) items, and which ever of all these is lower is put in the first option then the second item is taken and compare with the remaining (n-2) if an item with a value less than that of the second item his found in the (n-2) items, it is swapped with the second item of the list, and so on.
It is also requires a total of [n*(n-1)/2] steps/compressions.
Selection sort work faster has compared to exchange sort
3.quict sort.
Quick sort is the most efficient sorting technique, given a list of n elements which is to be sorted quick sort identifies an item (say k) in the list. A value less than (<) k to the left of k. and all the items that have a value greater than (>) to the right of the k.
We now have two sub list say list1 and list2 in the main list with K standing between list1 and list2,we identify new K list1 as well as list2.list1 and list2 each will be partied for the in to two sub list and so Ont.'s continues until the entire list is exhausted(executed) K can bay where in the list,but is generally most efficient to have it in the middle of the list
Imaging a list of numbers as fallow
43 33 11 55 77 90 40 60 99 22 88 65
Step 1: - find out the final position of one of the number in the list.it can be any number in the list.we start with the first number i.e. 43 sorting with the last number that is 65 scan the list from right to left comparing each number with 43 and stopping at the first number that is less that 43. We can "C" this number is 22 so swap 43 with 23
The list now looks as follows
22 33 11 55 77 90 40 60 99 43 88 65
Step2: - the number 88 and 65 to the right of 43 are greater than 43.starting with 22 scan the list in to the opposite direction (left to right) comparing each number 43 and swapping at the first number.which is greater than 43.this number is 55
The new list looks as follows.
22 33 11 43 77 90 40 60 99 55 88 65
Step3: - the number 22,33 and 22 are all to the left of 43 and are less than 43.starting with 55 scan the list in the original direction (right to left) stopping at the first number i.e. ; less than 43 it is 40,so swap 43 and 40
The new list now looks are as follows
22 33 11 40 77 90 43 60 99 55 88 65
Step4: - the number to the right of 43 are greater than 43.starting 40 scan the list left to right.staping at the first number which is greater than 43 .it is 77 so swap 77 and 43.
The new list looks as follows
22 33 11 40 43 90 77 60 99 55 88 65
Sravan cse 2nd batch
The number to the left of 43 are less than 43 and all the number to the right of 43 are greater than 43.over original number 43 is at it's correct started position.we now split the list in to halves one containing the items that are to the left of 43 and other containing the are to the right of 43.
4.tree sort: - the tree sort is based on the mechanism of sorting a binary tree in to its proper order.it is related to placing a value in it's appropriate position os the tree binary tree as a root at the top and elements down the tree. In tree sorting we organize in althea elements in such a position that they are sorted from left to right.
Q:- write the time and space complexicite,time complexicite for all sorting techniques
sorting techniques case Time complexicite Space complexicite
1.selection sort average 0 (n2) 0
Worest 0 (n2) 0
2.Bubble sort Average 0 (n2) 0
Worest 0 (n2) 0
3.insertion sort Average 0 (n2) 0
Worest 0 (n2) 0
4.merge sort Average 0 (n log n) 0 (n)
Worest 0 (n log n) 0 (n)
5.Quick sort Average 0 (n log n) 0 (n)
Worest 0 (n log n) 0 (n)
Sravan cse 2nd batch
SEARCHING TEACHNIQUES
SEARCHING TEACHNIQUES: - searching for information is a very common and widely used in computer applications.there are numerous occasions when information needs to be searched for
Eg:
a. Find out the list of employee who earns more than rs.10, 000 for month.
b. List all the customers who were serviced by a particular sales person in the last month
There are two searching methods is available
1.secuentiol search (al so called as linear search)
2.Binary search
1.sequentiol search: - sequential search in the traditional mechanism of searching for information .it is very simple under stands, but can be very poor in performance some times.as the name says, the process of searching for information in a sequential search is sequential (or one ofter the other) given a list so items, to find if a particular item exist (or does not exist) in the list.the following sequential algorithm can be used
Sequential algorithm: -
1.start with a number I=1
2.if there are still more items in the list. Compare the 1th element in the list with the item to be searched
else
Item is not found in the list. Stop
3.if a match is found
The item is found in the list. Stop
else
odd one 1 to I,and go back to step 1.
The important point in this algorithm is that we strat with the first item in the list, and go up to the end of the list, or until the item to be searched is found which ever is earlier.
The number times this algorithm is likely it be executed, depending on the best average and worst possible case. We assume that the list contains "N"items
case Meaning Number of interation
Best The item to be searched is the first item in the list 1
Average The item to be searched is found some were close to be middle of the list N/2
Worst The item to be searched is the last item in the list it or a does not existent at all N
Sravan cse 2nd batch
If we have 10,000 items in a listen an average it would required 10,000/2.i.e; 5,000 interation. Consider an array named arr, containing 1,000 integers. We can use the following function to search for a specific item (say item) in that array.
Syntax: -
Sequentiol_search (int item)
{
Int I;
For (I=0;I<1000;I++)
{
if (arr[I]==item)
{
Printf ("item found at the position %d in the arr \n",I+1);
return;
}
}
Printf ("item not found in the arr \n");
}
The function is quite simple to under stands.it basically scans through all the elements of the array one by one. Starting with the first element of the array.
Binary search: - Binary is a vast improvement over the sequential search. It can't always be used for binary search the item in the list must be in stored order
(Either ascending or descending) This is a pre-requisite for binary search. It the list to be searched for a specific item is not stored, binary search fails
Binary search is called as divided-and-conquer method. Assume that a list contains 1,000 elements. Which are stored in an ascending order of their values. An item "x" is to be searched in the list. Then the approach used by the binary search algorithm is as follows
Steps 1: - devoid the original list into two equals sized logical values. Let us call then of half1 and half 2. In this case the original1, 000 elements list will be split into two values. Each containing 500 elements
Step 2: - compare x with the last (I.e.; 500th ) elements of half1. There are 3 possibilities.
a. The value of 'x' matches with that of the 500 element of half1,the search is successful their four display an appropriate message and stop processing.
b. The value of 'x' is greater than that of the 500 element of . note that over list was originally sorted in the ascending order thus if the values of 'x' is greater than the last elements of half1,it means that 'x' is definitely not one of the first 500 elements in the 10,000 elements array.
c. The values of 'x' is less than that of the 500 elements of half1.note that over list was originally stored in the ascending order. Thus if the values of 'x' is less than the last elements of half1,it means that if 'x' is in the list . it must definitely be one of the first 500 elements in the 1,000 elements array.
Sravan cse 2nd batch
Out come Next action
a.x=last element of haif1 1.stop processing
b.x>last element of half1 2.search of x with in half2
c.x<last elements of half1 3.search of x half2
Int binary_search (int arr [], int item)
{
Int low=0,heigh=999,mid;
While (low<=high)
{
Mid = (low+high)/2;
If (item<arr [mid])
High=mid-1;
else
if(item>arr[mid])
low=mid+1;
else
Return_mid;
}
Return-1;
}
Sravan cse 2nd batch
