0% found this document useful (0 votes)
8 views8 pages

Csc206 Data Structure Note1

The document covers fundamental data structures and algorithms using C++, focusing on algorithms, performance analysis, searching, and sorting techniques. It defines algorithms and their properties, outlines the development process, and details various searching methods like linear and binary search, as well as sorting algorithms such as bubble sort, selection sort, insertion sort, quick sort, and merge sort. Additionally, it discusses performance analysis in terms of time and space complexity.
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
8 views8 pages

Csc206 Data Structure Note1

The document covers fundamental data structures and algorithms using C++, focusing on algorithms, performance analysis, searching, and sorting techniques. It defines algorithms and their properties, outlines the development process, and details various searching methods like linear and binary search, as well as sorting algorithms such as bubble sort, selection sort, insertion sort, quick sort, and merge sort. Additionally, it discusses performance analysis in terms of time and space complexity.
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

(CSC 206) FUNDAMENTAL DATA STRUCTURES AND ALGORITHMS USING C++

Unit I:
Algorithms, performance analysis‐ time complexity and space complexity, Searching: Linear and
binary search methods. Sorting: Bubble sort, selection sort, Insertion sort, Quick sort, Merge sort,
Heap sort. Time complexities.
ALGORITHMS
Definition: An Algorithm is a method of representing the step-by-step procedure for solving a
problem. It is a method of finding the right answer to a problem or to a different problem by
breaking the problem into simple cases.
It must possess the following properties:

1. Finiteness: An algorithm should terminate in a finite number of steps.


2. Definiteness: Each step of the algorithm must be precisely (clearly)
stated.
3. Effectiveness: Each step must be effective. i.e.; it should be easily
convertible into program statement and can be performed exactly in a
finite amount of time.
4. Generality: Algorithm should be complete in itself, so that it can be
used to solve all problems of given type for any input data.
5. Input/output: Each algorithm must take zero, one or more quantities
as input data and gives one of more output values.
An algorithm can be written in English like sentences or in any standard representations. The
algorithm written in English language is called Pseudo code.
Example: To find the average of 3 numbers, the algorithm is as shown below.
Step1: Read the numbers a, b, c, and d.
Step2: Compute the sum of a, b, and c.
Step3: Divide the sum by 3.
Step4: Store the result in variable of d.
Step5: End the program.
Development of an Algorithm
The steps involved in the development of an algorithm are as follows:
1. Specifying the problem statement.
2. Designing an algorithm.
3. Coding.
4. Debugging
5. Testing and Validating
6. Documentation and Maintenance.
Specifying the problem statement: The problem which has to be implemented in to a program
must be thoroughly understood before the program is written. Problem must be analyzed to
determine the input and output requirements of the program
Designing an Algorithm: Once the problem is cleared then a solution method for solving the
problem has to be analyzed. There may be several methods available for obtaining the required
solution. The best suitable method is designing an Algorithm. To improve the clarity and
understandability of the program flowcharts are drawn using algorithms.
Coding: The actual program is written in the required programming language with the help of
information depicted in flowcharts and algorithms.
Debugging: There is a possibility of occurrence of errors in program. These errors must be
removed for proper working of programs. The process of checking the errors in the program is
known as Debugging ‘.
There are three types of errors in the program.
Syntactic Errors: They occur due to wrong usage of syntax for the statements. Ex:
x=a*%b
Here two operators are used in between two operands.
Runtime Errors: They are determined at the execution time of the program Ex:
Divide by zero Range out of bounds.
Logical Errors: They occur due to incorrect usage of instructions in the program. They are
neither displayed during compilation or execution nor cause any obstruction to the program
execution. They only cause incorrect outputs.
Testing and Validating: Once the program is written, it must be tested and then validated. i.e.,
to check whether the program is producing correct results or not for different values of input.
Documentation and Maintenance: Documentation is the process of collecting, organizing and
maintaining, in written the complete information of the program for future references.
Maintenance is the process of upgrading the program, according to the changing requirements.
PERFORMANCE ANALYSIS
When several algorithms can be designed for the solution of a problem, there arises the need to
determine which among them is the best. The efficiency of a program or an algorithm is
measured by computing its time and/or space complexities.
The time complexity of an algorithm is a function of the running time of the algorithm.
The space complexity is a function of the space required by it to run to completion. The time
complexity is therefore given in terms of frequency count.
Searching: Searching is the technique of finding desired data items that has been stored within
some data structure. Data structures can include linked lists, arrays, search trees, hash tables, or
various other storage methods. The appropriate search algorithm often depends on the data
structure being searched. Search algorithms can be classified based on their mechanism of
searching. They are Linear searching and Binary searching
Linear or Sequential searching: Linear Search is the most natural searching method and It is
very simple but very poor in performance at times. In this method, the searching begins with
searching every element of the list till the required record is found. The elements in the list may
be in any order. i.e. sorted or unsorted. We begin the search by comparing the first element of the
list with the target element. If it matches, the search ends and position of the element is returned.
Otherwise, we will move to next element and compare. In this way, the target element is
compared with all the elements until a match occurs. If the match does not occur and there are no
more elements to be compared, we concluded that target element is absent in the list by returning
position as - 1
Linear search Algorithm
The algorithm for linear search is relatively simple. The procedure starts at the very first index of
the input array to be searched.

Step 1 − Start from the 0th index of the input array, compare the key value with the value present
in the 0th index.

Step 2 − If the value matches with the key, return the position at which the value was found.

Step 3 − If the value does not match with the key, compare the next element in the array.

Step 4 − Repeat Step 3 until there is a match found. Return the position at which the match was
found.

Step 5 − If it is an unsuccessful search, print that the element is not present in the array and exit
the program. Pseudocode
procedure linear_search (list, value)
for each item in the list

if match item == value


return the item's location
end if end for end procedure
Analysis
Linear search traverses through every element sequentially therefore, the best case is when the
element is found in the very first iteration. The best-case time complexity would be O(1).
However, the worst case of the linear search method would be an unsuccessful search that does
not find the key value in the array, it performs n iterations. Therefore, the worst-case time
complexity of the linear search algorithm would be O(n).
Example
Let us look at the step-by-step searching of the key element (say 47) in an array using the linear
search method.
0 1 2 3 4 5 6 7
34 10 66 27 47 8 55 78

Implementation using C++ #include <iostream> using


namespace std; void linear_search(int a[], int n, int key){ int
i, count = 0; for(i = 0; i < n; i++) { if(a[i] == key) { //
compares each element of the array cout << "The element
is found at position " << i+1 <<endl; count = count + 1;
}
}
if(count == 0) // for unsuccessful search cout << "The
element is not present in the array" <<endl; } int main(){
int i, n, key; n = 6; int a[10] =
{12, 44, 32, 18, 4, 10}; key = 18;
linear_search(a, n, key); key = 23;
linear_search(a, n, key); return 0;
}

Output
The element is found at position 4
The element is not present in the array
BINARY SEARCHING
Binary search is a fast search algorithm with run-time complexity of Ο (log n). This search
algorithm works on the principle of divide and conquer. Binary search looks for a particular item
by comparing the middle most item of the collection. If a match occurs, then the index of item is
returned. If the middle item is greater than the item, then the item is searched in the sub-array to
the left of the middle item. Otherwise, the item is searched for in the sub- array to the right of the
middle item. This process continues on the sub-array as well until the size of the subarray
reduces to zero.
Before applying binary searching, the list of items should be sorted in ascending or descending
order.
Binary search Algorithm
Binary search algorithm is an interval searching method that performs the searching in intervals
only. The input taken by the binary search algorithm must always be in a sorted array since it
divides the array into sub-arrays based on the greater or lower values.
Step1: select the middle item in the array and compare it with the key value to be searched. If its
matched, return the position of the median.
Step2: if it does not match the key value, check if the key value is greater than or less than the
median value
Step3: if the key is greater, perform the search in the right sub-array, but if the key is lower than
the median value, perform the search in the left sub-array.
Step4: repeat step 1-3 iteratively until the size of sub-array becomes 1.
Step5: if the key value does not exist in the array then the algorithm returns an unsuccessful
search
Pseudocode
Procedure binary_search
A sorted array n
size of array x value
to be searched set
lowerBound = 1 set
upperBound = n while x
not found
if upperBound < lowerBound
EXIT: x does not exists.
Set midPoint = lowerBound + (upperBound - lowerBound)/2
If A[midPoint] < x
Set lowerBound = midPoint + 1
If A[midPoint] > x
Set upperBound = midPoint – 1
If A[midPoint] = x
EXIT: x found at location midPoint
End while
end procedure

SORTING
Arranging the elements in a list either in ascending or descending order. various sorting
algorithms are
1. Bubble sort
2. selection sort
3. Insertion sort
4. Quick sort
5. Merge sort
6. Heap sort
BUBBLE SORT
The bubble sort is an example of exchange sort. In this method, repetitive comparison is
performed among elements and essential swapping of elements is done. Bubble sort is commonly
used in sorting algorithms. It is easy to understand but time consuming i.e. takes more number of
comparisons to sort a list. In this type, two successive elements are compared and swapping is
done. Thus, step-by-step entire array elements are checked. It is different from the selection sort.
Instead of searching the minimum element and then applying swapping, two records are swapped
instantly upon noticing that they are not in order.
SELECTION SORT
selection sort:- Selection sort ( Select the smallest and Exchange ):The first item is compared
with the remaining n-1 items, and whichever of all is lowest, is put in the first position. Then the
second item from the list is taken and compared with the remaining (n-2) items, if an item with a
value less than that of the second item is found on the (n-2) items, it is swapped (Interchanged)
with the second item of the list and so on.
INSERTION SORT
Insertion sort: It iterates, consuming one input element each repetition, and growing a sorted
output list. Each iteration, insertion sort removes one element from the input data, finds the
location it belongs within the sorted list, and inserts it there. It repeats until no input elements
remain
QUICK SORT
Quick sort: It is a divide and conquer algorithm. Developed by Tony Hoare in 1959. Quick sort
first divides a large array into two smaller sub-arrays: the low elements and the high elements.
Quick sort can then recursively sort the sub-arrays. ALGORITHM:
Step 1: Pick an element, called a pivot, from the array.
Step 2: Partitioning: reorder the array so that all elements with values less than the pivot come
before the pivot, while all elements with values greater than the pivot come after it (equal values
can go either way). After this partitioning, the pivot is in its final position. This is called the
partition operation.
Step 3: Recursively apply the above steps to the sub-array of elements with smaller values and
separately to the sub-array of elements with greater values.

MERGE SORT
Merge sort is a sorting technique based on divide and conquer technique. In merge sort the
unsorted list is divided into N sub-lists, each having one element, because a list of one element is
considered sorted. Then, it repeatedly merges these sub-lists, to produce new sorted sub-lists, and
at lasts one sorted list is produced. Merge Sort is quite fast, and has a time complexity of O(n log
n).
Conceptually, merge sort works as follows:
1. Divide the unsorted list into two sub lists of about half the size.
2. Divide each of the two sub lists recursively until we have list sizes of length 1, in
which case the list itself is returned.
3. Merge the two sub lists back into one sorted list.

You might also like