SORTING TECHNIQUES
DAA- Unit-1
LINEAR SEARCH
#include <stdio.h>
int main()
{
int array[100], search, c, n;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integer(s)\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Enter a number to search\n");
scanf("%d", &search);
for (c = 0; c < n; c++)
{
if (array[c] == search) /* If required element is found */
{
printf("%d is present at location %d.\n", search, c+1);
break;
}
}
if (c == n)
printf("%d isn't present in the array.\n", search);
return 0;
}
LINEAR SEARCH
Complexity Analysis of Linear Search:
Time Complexity:
Best Case: In the best case, the key might be present at the first index. So the best case
complexity is O(1)
Worst Case: In the worst case, the key might be present at the last index i.e., opposite to the
end from which the search has started in the list. So the worst-case complexity is O(N) where
N is the size of the list.
Average Case: O(N)
Auxiliary Space: O(1) as except for the variable to iterate through the list, no other variable is
used.
Advantages of Linear Search:
Linear search can be used irrespective of whether the array is sorted or not. It can be used on
arrays of any data type.
Does not require any additional memory.
It is a well-suited algorithm for small datasets.
Drawbacks of Linear Search:
Linear search has a time complexity of O(N), which in turn makes it slow for large datasets.
Not suitable for large arrays.
When to use Linear Search?
When we are dealing with a small dataset.
When you are searching for a dataset stored in contiguous memory.
BINARY SEARCH
BINARY SEARCH
#include <stdio.h>
int main() { int c, first, last, middle, n, search, array[100];
printf("Enter number of elements:\n");
scanf("%d",&n);
printf("Enter %d integers:\n", n);
for (c = 0; c < n; c++)
scanf("%d",&array[c]);
printf("Enter the value to find:\n");
scanf("%d", &search);
first = 0;
last = n - 1;
middle = (first+last)/2;
BINARY SEARCH
while (first <= last)
{
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search)
{
printf("%d is present at index %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
printf("Not found! %d is not present in the list.\n", search);
return 0;
}
BINARY SEARCH
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present"
" in array")
: printf("Element is present at "
"index %d",
result);
return 0;
}
BINARY SEARCH
Complexity Analysis of Binary Search:
Time Complexity:
Best Case: O(1)
Average Case: O(log N)
Worst Case: O(log N)
Auxiliary Space: O(1), If the recursive call stack is considered then the auxiliary space will be O(logN).
Advantages of Binary Search:
Binary search is faster than linear search, especially for large arrays.
More efficient than other searching algorithms with a similar time complexity, such as interpolation search
or exponential search.
Binary search is well-suited for searching large datasets that are stored in external memory, such as on a
hard drive or in the cloud.
Drawbacks of Binary Search:
The array should be sorted.
Binary search requires that the data structure being searched be stored in contiguous memory locations.
Binary search requires that the elements of the array be comparable, meaning that they must be able to be
ordered.
Applications of Binary Search:
Binary search can be used as a building block for more complex algorithms used in machine learning, such
as algorithms for training neural networks or finding the optimal hyperparameters for a model.
It can be used for searching in computer graphics such as algorithms for ray tracing or texture mapping.
It can be used for searching a database.
BUBBLE SORT
Bubble Sort is the simplest sorting algorithm
It works by repeatedly iterating input array from 1 st element to
last element, comparing each pair and swapping the adjacent
elements if required
Bubble sort continues its iteration until no swaps are required.
Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ),
Here, algorithm compares the first two elements, and swaps since 5 >
1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ),
Now, since these elements are already in order (8 > 5),
algorithm does not swap them. wrong order.
CONTD..
Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted,
But the algorithm does not know if it is completed.
The algorithm needs one whole pass without any swap to know it
is sorted.
Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
IMPLEMENTATION OF BUBBLE SORT
// A function to implement bubble sort
void bubbleSort(int arr [ ], int n)
{
int i, j, s;
for (i = 0; i < n-1; i++)
{
s=0;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
// Swap elements
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
s=1;
}
}
if(s==0)
break;
}
CONTD..
TIME COMPLEXITY
Worst Case - O(n^2)
Best Case - O(n) – When array is already sorted
SELECTION SORT
The selection sort algorithm sorts an array by repeatedly
finding (selecting) the minimum element (considering
ascending order) from unsorted part and putting it at the
beginning.
The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element
(considering ascending order) from the unsorted
subarray is picked and moved to the sorted subarray.
EXAMPLE
arr[] = 64 25 12 22 11
Find the minimum element in arr[0...4] and place it at beginning
11 25 12 22 64
Find the minimum element in arr[1...4] and place it at beginning of
arr[1...4]
11 12 25 22 64
Find the minimum element in arr[2...4] and place it at beginning of
arr[2...4]
11 12 22 25 64
Find the minimum element in arr[3...4] and place it at beginning of
arr[3...4]
11 12 22 25 64
IMPLEMENTATION OF SELECTION SORT
void selectionSort(int arr[], int n)
{
int i, j, min;
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min = i;
for (j = i+1; j < n; j++)
{
if (arr[j] < arr[min])
min = j;
}
// Swap the found minimum element with the first element
temp= a[min];
a[min] = a[i];
a[i] = temp;
}
}
TIME COMPLEXITY
O(n2) as there are two nested loops.
INSERTION SORT
Insertion sort is a simple and efficient sorting algorithm.
In this algorithm, each iteration removes an element
from input data and inserts it into the correct position in
the list being sorted.
EXAMPLE-
ANOTHER EXAMPLE (WITH STEPS):
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 5
(Size of input array)
i = 1.
Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2.
13 will remain at its position as all elements in A[0..i-1] are
smaller than 13
11, 12, 13, 5, 6
CONTD..
i = 3.
5 will move to the beginning and all other elements from 11
to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4.
6 will move to position after 5, and elements from 11 to 13
will move one position ahead of their current position.
5, 6, 11, 12, 13
IMPLEMENTATION OF INSERTION SORT
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[ ], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
COMPLEXITY
Time Complexity: O(n2)
QUICK SORT
Quick Sort is a Divide and Conquer algorithm.
It picks an element as pivot and partitions the given array around
the picked pivot.
There are many different versions of Quick Sort that pick pivot
in different ways such as-
Always pick first element as pivot. (implemented below)
Always pick last element as pivot.
Pick a random element as pivot.
Pick median as pivot.
STEPS-
The key process in quickSort is partition().
Target of partitions is-
given an array and an element x of array as pivot,
place x at its correct position in sorted array
place all smaller elements (smaller than x) before x, and
place all greater elements (greater than x) after x.
All this should be done in linear time.
EXAMPLE
low high
54 will serve as our first pivot value.
The partition process will happen next.
It will find the split point and at the same time move other items to the
appropriate side of the list, either less than or greater than the pivot
value.
Partitioning begins by locating two position markers—let’s call
them leftmark and rightmark—at the beginning and end of the
remaining items in the list (positions 1 and 8 in above figure).
The goal of the partition process is to move items smaller than pivot
to its left and items greater than pivot to its right.
CONTD..
CONTD..
QUICK SORT LEFT & RIGHT HALF
RECURSIVE ALGORITHM FOR QUICK SORT
partition (low, high)
{
Quick Sort (low, high)
pivot = A[low]; {
i=low;
if(low<high)
j=high;
while (i < j) {
{ j=partition (low, high);
do
{
Quicksort(low, j);
i++; Quicksort(j+1, high)
}while (A[ i ] <= pivot)
}
do
{ }
j--;
}while (A[ j ] > pivot)
if(i<j)
swap (A[ i ] , A[ j ])
}
swap (A[low] , A[ j ])
return j;
}
ANALYSIS OF QUICK SORT
If partitioning is always done in the middle (Best Case)
Time Complexity- O(nlogn)
Achieving best case is not possible (Randomly it may
happen)
If Partitioning is always done at the beginning (If the list
is already sorted - Worst Case)
Time Complexity- O(n2)
MERGE SORT
Merge sort is a recursive algorithm that continually splits
a list in half.
If the list is empty or has one item, it is sorted by
definition (the base case).
If the list has more than one item, we split the list and
recursively invoke a merge sort on both halves.
Once the two halves are sorted, the fundamental
operation, called a merge, is performed.
Merging is the process of taking two smaller sorted lists
and combining them together into a single, sorted, new
list.
EXAMPLE- PART-1 SPLITTING
low high
EXAMPLE- PART-2 MERGING
IMPLEMENTATION OF MERGE SORT
Algorithm MergeSort(low, high)
{
If(low < high)
{
mid= ( low + high) / 2;
MergeSort( low, mid );
MergeSort( mid+1, high);
Merge(low, mid, high);
}
}
ANALYSIS OF MERGE SORT
Since the list is partitioned into two halves every time
Time Complexity is O(nlogn)
SHELL SORT
The shell sort, sometimes called the “diminishing
increment sort,” improves on the insertion sort by
breaking the original list into a number of smaller
sublists,
Each sublist is sorted using an insertion sort.
The unique way that these sublists are chosen is the key
to the shell sort.
Instead of breaking the list into sublists of contiguous
items, the shell sort uses an increment i, sometimes
called the gap, to create a sublist by choosing all items
that are i items apart.
Figure below shows a final insertion sort using an increment of one;
in other words, a standard insertion sort.
Note that by performing the earlier sublist sorts, we have now
reduced the total number of shifting operations necessary to put the
list in its final order.
For this case, we need only four more shifts to complete the process.
SHELL SORT EXAMPLE WITH GAP=4
