Array as Data Structure
1. Array is collection of similar type data element.
2. An array is a collection of items of same data type stored at
contiguous memory locations.
3. Array in ‘C’ declared as int a[5].
4. All elements are stored in continuous memory location
5. Note: “Location of next index depends on the data type we use”.
Advantages of Array in C
1. Easy to declare and initialize -It is easy to declare
2. Quick access to elements – Arrays provide direct access to any
element in the array.
3. Efficient use of memory – Arrays are a compact way of storing data
in memory. They occupy a contiguous block of memory, which makes
it easy for the computer to locate and retrieve data.
4. Simplify complex operations – Arrays can be used to simplify
complex operations that involve multiple data items.
5. Enhanced functionality with pointers – In C, arrays can be easily
manipulated using pointers. Pointers allow you to perform operations
such as swapping elements in an array
Disadvantages of Array in C
1. Limited Size – In C, arrays have a fixed size that cannot be changed
during runtime.
2. Inflexible Structure – Arrays in C are a static data structure, which
means that the size and type of data they hold are predetermined.
3. Wastage of Memory – Arrays in C allocate memory for all their
elements, even if they are not used.
4. No Built-in Bounds Checking – In C, there is no built-in bounds
checking for arrays. This means that if a program tries to access an
element that is outside the bounds of the array, it can cause a runtime
error or even crash the program.
5. Limited Data Types – Arrays in C can only hold data of one type.
This means that if a program needs to store data of different types, it
will need to use multiple arrays or a different data structure.
Applications of Array Data Structure:
1. Storing and accessing data: Arrays are used to store and retrieve data
in a specific order. For example, an array can be used to store the
scores of a group of students, or the temperatures recorded by a
weather station.
2. Sorting: Arrays can be used to sort data in ascending or descending
order. Sorting algorithms such as bubble sort, merge sort, and quick
sort rely heavily on arrays.
3. Searching: Arrays can be searched for specific elements using
algorithms such as linear search and binary search.
4. Matrices: Arrays are used to represent matrices in mathematical
computations such as matrix multiplication, linear algebra, and image
processing.
5. Stacks and queues: Arrays are used as the underlying data structure
for implementing stacks and queues, which are commonly used in
algorithms and data structures.
6. Graphs: Arrays can be used to represent graphs in computer science.
Each element in the array represents a node in the graph, and the
relationships between the nodes are represented by the values stored
in the array.
7. Dynamic programming: Dynamic programming algorithms often use
arrays to store intermediate results of sub problems in order to solve a
larger problem.
Basic Operations in the Arrays
1. Traverse − print all the array elements one by one.
2. Insertion − Adds an element at the given index.
3. Deletion − Deletes an element at the given index.
4. Search − Searches an element using the given index or by the value.
5. Update − Updates an element at the given index.
6. Display − Displays the contents of the array.
Algorithm for Insert Element in Array
1. Get the element value which needs to be inserted.
2. Get the position value.
3. Check whether the position value is valid or not.
4. If it is valid,
Shift all the elements from the last index to position index by 1
position to the right.
insert the new element in arr[position]
5. Otherwise,
Invalid Position
Algorithm for Delete Element in Array
1. Find the given element in the given array and note the index.
2. If the element found,
Shift all the elements from index + 1 by 1 position to the left.
Reduce the array size by 1.
3. Otherwise, print "Element Not Found"
Sorting:
Sorting means arranging a set of data in some given order or ordering a
list of items.
‘Or’
Sorting is a process of ordering a list of elements in either ascending or
descending order.
List is a collection of record each contains one or more fields. The field
which contains unique value for each record is called key field.
Definition:-
Sorting is the operation of arranging the records of a table according to
the key value of each record
Sort Stability:
A sorting algorithm is said to be stable if it preserves the order for all
records with duplicate keys
The Sorting Algorithms are stable in nature are Bubble Sort, Insertion
Sort, Merge Sort, Count Sort.
The Sorting Algorithms are stable in nature are Quick Sort, Heap Sort
The sorting algorithm are divided into two categories
1) Internal sorting-Sorting is done on data which is sorted in main
memory.
2) External sorting – Sorting is done on data which is stored on auxiliary
storage device.
e.g. hard disk, floppy, tape etc.
BUBBLE SORT
1. This is one of the simplest and most popular sorting methods. The
basic idea is to pass through the file sequentially several times.
2. In each pass we compare successive pairs of elements(x[i] with
x[i+1]) and interchange the two if they are not in the required order.
3. One element is placed in its correct position in each pass.
4. In first pass, the largest element will sink to the bottom, second
largest in the second pass and so on. Thus a total of n-1 passes are
required to sort n keys
5. Time Complexity:
a) Base Case: O(n),
b) Worst Case: O(n2 ),
c) Average Case: O(n2 )
Algorithm for Bubble sort:
Step1: Start
Step2: Accept ‘n’ numbers in array ‘A’
Step3: for i=0 to n-1 do
for j=0 to n-i-1 do
if(A[j]>A[j+1]) then
Temp=A[j];
A[j]=A[j+1]
A[j+1]=temp
Step4:Stop
Advantage of Bubble Sort:
1. It is Simple algorithm
2. Easy to implement
Disadvantage of Bubble Sort:
1. It is slowest method
2. Inefficient for large array size
INSERTION SORT
1. Insertion sort inserts each item into its proper place in the final list
2. In this the first iteration starts with comparison of 1st element with
0th
3. In second iteration 2nd element is compared with the 0th and 1st
element and so on.
4. In every iteration an element is compared with all elements
5. The basic idea of this method is to place an unsorted element into its
correct position in a growing sorted list of data. We select one element
from the unsorted data at a time and insert it into its correct position
in the sorted set.
6. E.g. in order to arrange playing cards we pick one card at a time and
insert this card hold in the hand.
7. Time Complexity:
a. Base Case: O(n)
b. Worst Case: O(n2 )
c. Average Case: O(n2 )
Algorithm for Insertion sort:
Step1: Start
Step2: Accept ‘n’ numbers in array ‘A’
Step3: Set i=1
Step4:key=A[i]
Step5:Set j=i-1
Step6:if key<A[j] then
A[j+1]=A[j]
j=j-1;
Repeat step 2 until j>=0
Step5:A[j+1]=key;
i=i+1;
Step6:Repeat step 2 to 5 until i<n
Step7:Stop
Advantage of Insertion Sort:
1. It is Simple algorithm
2. Easy to implement
Disadvantage of Insertion Sort:
1. Inefficient for large array size
SELECTION SORT
1. It is also called pushdown sort.
2. In this the largest or smallest element is selected by placing it
repeatedly till it reaches its proper position.
3. The 0th element is compared with all other elements, if the 0th is
found to be greater than the compared element then they are
interchanged . In this way after first iteration the smallest element is
placed at 0th position. The Procedure is repeated for 1st element and
so on.
4. It is Simple to implement.
5. The main advantage is that data movement is very less
6. It is not stable so. It is an in-place sort
7. Time Complexity:
a) Base Case: O(n2 )
b) Worst Case: O(n2 )
c) Average Case: O(n2 )
Algorithm for Selection Sort
Step1: Start
Step2: Accept ‘n’ numbers and store all in array ‘A’
Step3: set i=0
Step4: if i <n-1 then goto next step else goto step 11
Step5: set min=i and j=i+1
Step6: if j< n then goto next step else goto step 9
Step7: if A[j]< A[min] then min=j
Step8: set j=j+1 and goto step 7
Step9: if(min not equal to i) then interchange A[i] and A[min]
Step10: i=i+1 and goto step 4
Step11: Stop
Advantages of Selection Sort
1. Simple and easy to implement
2. 60% performance improvement than bubble sort
Disadvantages of Selection Sort
1. Not suitable of large number of elements
QUICK SORT
1. It is also called “partition Exchange sort. The strategy used here is
“divide and conquer” i.e we successively partition the list in smaller
lists and apply the same procedure to the sub-list. The procedure is as
follows:-
2. Procedure –
3. We will consider one element at a time (pivot) and place it in its
correct position.
4. The pivot is placed in a position such that all elements to the left of
the pivot are less than the pivot and all elements to the right are
greater.
5. The array is partitioned into two parts:- left partition and right
partition.
6. The same method is applied for each of the partition.
7. The process continues till no more partition can be made. We shall be
considering the first element of the partition as the pivot element.
Algorithm:
Step 1: start.
Step 2: A is an array of n element.
Step 3: lb=0
lb = lower bound
ub = n-1
ub = upper bound.
Step 4: if(lb<ub)
i.e. if the array can be partitioned
j=partition(A,lb,ub) // j is the pivot position
quicksort(A,lb,j-1);
quicksort(A,j+1,ub);
Algorithm for partitioning
QuickSort(A,n)
Step1: Start
Step2: Accept ‘n’ numbers and store all in array ‘A’
Step3: lb=0, ub=n-1
Step3:
if (lb<ub)
j=Partition(A,lb,ub)
QuickSort(A,lb,j-1)
QuickSort(A,j+1,ub)
Partition(A, lb, ub)
Step1: down=lb, up=ub
Step2: pivot=A[lb]
Step3:
while (A[down]<=pivot && down<up)
down++
Step4:
while (A[up]>pivot && up>down)
up--
Step5:
if (down < up)
Interchange A[down] and A[up] and goto step 3.
Step6: Interchange A[up] and pivot
Step7: return up
Step8: Stop
Efficiency of quick sort.
Best case = average case = O(nlogn)
Worst case = O(n2)
MERGE SORT.
1. Merging is the process of combining two or more sorted data lists into
a third list such that it is also sorted.
2. Merge sort follows Divide and Conquer strategy.
a) - Divide :- divide an n element sequence into n/2 subsequence.
b) - Conquer :- sort the two sequences recursively.
c) - Combine :- merge the two sorted sequence into a single
sequence.
3. In this two list are compared and the smallest element is stored in the
third array.
Algorithm:-
mergesort(a, N) algorithm:
Step1: Start
Step2: Accept N numbers and store into array a
Step3: Assign low=0 and high=N-1
Step4: if low < high
mid=(low+high)/2
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,high);
algorithm: merge(A, low, mid, high)
Step1: i=low, j=mid+1, k=0;
Step2:
while i<=mid && j<=high
if(a[i]<=a[j])
b[k]=a[i]
k=k+1, i=i+1
else
b[k]=a[j]
k=k+1, j=j+1
Step3:
while(i<=mid)
b[k]=a[i]
k=k+1, i=i+1
Step4:
while(j<=high)
b[k]=a[j]
k=k+1, j=j+1
Step5: j=low, k=0
Step6:
while j<=high
a[j]=b[k]
j=j+1, k=k+1
Step7: stop
Searching is the process of finding a value in a list of values. The
commonly used searching methods used are linear search and Binary
search.
linear search
Step 1: Start
Step 2: Accept n numbers in an array num and a number to be searched
Step 3: se ti=0 and flag=0
Step 4: if i<n then goto next step else goto step 7
Step 5: Compare num[i] and number
If equal then
set flag=1 and goto step 7
Step 6: i=i+1 and goto step 4
Step 7: if (flag=1) then
Print “Required number is found at location i+1”
else
Print “Require data not found”
Step 8: Stop
Time Complexity:
Base Case: O(1)
Worst Case: O(n)
Average Case: O(n)
Sentinel search
Sentinel search is a type of linear search where the number of
comparisons is reduced as compared to a traditional linear search. The
value to be searched can be appended to the list at the end as a “sentinel
value.
Algorithm:
Step 1: Start
Step 2: Accept n numbers in an array num and a number to be searched
Step 3: set i=0, last=num[n-1], num[n-1]=number
Step 4: Compare num[i] and number
If equal then goto step 6
Step 5: i=i+1 and goto step 4
Step 6: num[n-1]=last
Step 7: if (num[i]=number) then
Print “Required number is found at location i+1”
else
Print “Require data not found”
Step 8: Stop
Time Complexity:
Base Case: O(1)
Worst Case: O(n)
Average Case: O(n)
Binary Search
Binary Search is used with sorted array or list. So a necessary condition
for Binary search to work is that the list/array should be sorted. It works
by repeatedly dividing in half the portion of the list that could contain the
item.
Algorithm:
Step 1: Start
Step 2: Accept n numbers in an array num and a number to be searched
Step 3: set low=0, high=n-1 and flag=0
Step 5: if low <= high then
middle=(low+high)/2
else
goto step 8.
Step 6: if (num[middle]=number)
position=middle, flag=1 goto step 8.
else if (number< num[middle])
high=middle-1
else
low=middle+1
Step 7: goto step 5
Step 8: if flag=1
Print “Required number is found at location position+1”
Else
Print “Required number is not found.
Step 9: Stop
Time Complexity:
Base Case: O(1)
Worst Case: O(log n)
Average Case: O(log n)
Analysis of sorting techniques :
sorting Time Complexity Space
Algorithm Complexity
Best Average Worst Worst Case
Case Case Case
Bubble Sort Ω(N) Θ(N2) O(N2) O(1)
Selection
Ω(N2) Θ(N2) O(N2) O(1)
Sort
Insertion
Ω(N) Θ(N2) O(N2) O(1)
Sort
Ω(N log O(N log
Merge Sort Θ(N log N) O(N)
N) N)
Ω(N log O(N log
Heap Sort Θ(N log N) O(1)
N) N)
Ω(N log
Quick Sort Θ(N log N) O(N2) O(log N)
N)
Radix Sort Ω(N k) Θ(N k) O(N k) O(N + k)
Count Sort Ω(N + k) Θ(N + k) O(N + k) O(k)
sorting Time Complexity Space
Algorithm Complexity
Best Average Worst Worst Case
Case Case Case
Bucket Sort Ω(N + k) Θ(N + k) O(N2) O(N)
Sort stability, Efficiency, Passes Comparison Table :
Sorting Efficiency Passes Sort stability
algorithm
Bubble sort 0(n2) n-1 stable
Selection sort 0(n2) n-1 stable
Insertion sort
0(n) n-1
Best case stable
0(n2) n-1
Worst case
Quick sort
0(n log n) log n
Best case unstable
0(n2) n-1
Worst case
Merge sort 0(n log n) log n stable
Radix sort No. of
digits in
0(n) the stable
largest
number