Practical 1:- Implementation and Time analysis of sortingalgorithms.

Bubble sort, Selection sort, Insertion sort, Merge sort and Quicksort

>>Bubble Sort
Explanation:

Algorithm:

1. We are given with an input array which is supposed to be sorted in

ascending order
2. We start with the first element and i=0 index and check if the element
present at i+1 is greater then we swap the elements at index i and i+1.
3. If above is not the case, then no swapping will take place.
4. Now “ i ” gets incremented and the above 2 steps happen again until the
array is exhausted.
5. We will ignore the last index as it is already sorted.
6. Now the largest element will be at the last index of the array.
 7. Now we will again set i=0 and continue with the same steps that will
eventually place second largest at second last place in the array. Now the
last 2 indexes of the array are sorted.

Pseudo Code:
procedure bubbleSort( list : array of items )

loop = [Link];

for i =0 to loop-1do:
swapped =false

for j =0 to loop-1do:

/* compare the adjacent elements */

if list[j]> list[j+1]then
/* swap them */
swap( list[j], list[j+1])
swapped =true
endif

endfor

/*if no number was swapped that means

array is sorted now, break the loop.*/

if(not swapped)then
break
endif

endfor

end procedure return list

Analysis:
Time Complexity
 • Each and every element is compared with the other elements for array
which takes n time
• And the above steps continues for n iterations
• Best Time Complexity: O(n^2)
• Average Time Complexity: O(n^2)
• Worst Time Complexity: O(n^2)

Space Complexity

• No auxiliary space is required in bubble sort implementation

• Hence space complexity is: O(1)

>>Selection Sort

Explanation:
Algorithm:

• Set min index to the first index of an unsorted array

• Iterate the entire unsorted array and do the comparison with min
• If element present at the min is greater than the element present at the
current index then update min with a current index
• Once the iteration is complete, swap the element of min index with the
first element of the unsorted part
• For descending order, instead of maintaining the smallest element index,
maintain the largest element index

Pseudo Code:
procedure selection sort
list : array of items
n : size of list

for i =1 to n -1
/* set current element as minimum*/
min = i

/* check the element to be minimum */

for j = i+1 to n
if list[j]< list[min]then
min = j;
endif
endfor

/* swap the minimum element with the current element*/

if indexMin != i then
swap list[min]and list[i]
endif
endfor
end procedure

Analysis:
 Time Complexity

• In the worst case, in every iteration, we have to traverse the entire array
for finding min elements and this will continue for all n elements. Hence
this will perform n^2 operations in total.
• In the best case that is sorted array, we can do some modification by
using lag to check whether the lament is already sorted or not
• Best Time Complexity: O(n)
• Average Time Complexity: O(n^2)
• Worst Time Complexity: O(n^2)

Space Complexity

• No auxiliary space is required in Selection Sort implementation that is

we are not using any arrays, linked list, stack, queue, etc to store our
elements
• Hence space complexity is: O(1)

>>Insertion sort

Explanation:
Algorithm:

• Take the first element and consider it to be a sorted part(a single element
is always sorted)
• Now pick arr[1] and store it is a temporary variable
• Start comparing the values of tmp with elements of the sorted part from
the rear side
• If tmp is less than the rear element, say arr[k], then shift arr[k] to k+1
index
• This shifting will continue until the appropriate location is identified.
Then, we will put the temporary element at the identified location
• This will continue for all the elements, and we will have our desired
sorted array in ascending order
Pseudo code:

procedure insertionSort( A : array of items )

int holePosition
int valueToInsert

for i =1 to length(A) inclusive do:

/* select value to be inserted */

valueToInsert = A[i]
holePosition = i

/*locate hole position for the element to be inserted */

while holePosition >0and A[holePosition-1]> valueToInsert do:

A[holePosition]= A[holePosition-1]
holePosition = holePosition -1
endwhile

/* insert the number at hole position */

A[holePosition]= valueToInsert

endfor

end procedure
Analysis:

Time Complexity

• In the worst-case scenario, n will pick all elements and then n shifts to set
it to the right position
 • In the best-case scenario, that is a sorted array, we will just pick the
elements, but no shifting will take place leading it to n time complexity,
that is, every element is traversed at least once
• Best Time Complexity: O(n)
• Average Time Complexity: O(n^2)
• Worst Time Complexity: O(n^2)

Space Complexity

• No auxiliary space is required in insertion sort implementation. That is,

we are not using any arrays, linked list, stack, queue, etc, to store our
elements
• Hence space complexity is: O(1)

>>Merge sort

Explanation:
Algorithm:

• Declare left and right var which will mark the extreme indices of the
array
• Left will be assigned to 0 and right will be assigned to n-1
• Find mid = (left+right)/2
• Call mergeSort on (left,mid) and (mid+1,rear)
• Above will continue till left<right
• Then we will call merge on the 2 subproblems
Pseudo code:

procedure mergesort(var a as array )

if( n ==1)return a

var l1 as array = a[0]... a[n/2]

var l2 as array = a[n/2+1]... a[n]

l1 = mergesort( l1 )
l2 = mergesort( l2 )

return merge( l1, l2 )

end procedure

procedure merge(var a as array,var b as array )

var c as array
while( a and b have elements )
if( a[0]> b[0])
add b[0] to the endof c
remove b[0]from b
else
add a[0] to the endof c
remove a[0]from a
endif
endwhile

while( a has elements )

add a[0] to the endof c
remove a[0]from a
endwhile

while( b has elements )

add b[0] to the endof c
remove b[0]from b
endwhile

return c

end procedure
Analysis:
Time Complexity

• In the worst case, in every iteration, we are dividing the problem into
further 2 subproblems. Hence this will perform log n operations and this
has to be done for n iteration resulting in n log n operations total.
• In the best case that is sorted array, we can do some modification by
using a flag to check whether the lament is already sorted or not
• Best Time Complexity: O(nlogn)
• Average Time Complexity: O(nlogn)
• Worst Time Complexity: O(nlogn)

Space Complexity

• n auxiliary space is required in Merge Sort implementation as all the

elements are copied into an auxiliary array
• Hence space complexity is: O(n)
>>Quicksort

Explanation:

Algorithm:

• We are given with an input array

• Choose pivot, here we are choosing the last element as our pivot
• Now partition the array as per pivot
o Keep a partitioned index say p and initialize it to -1
o Iterate through every element in the array except the pivot
o If an element is less than the pivot element then increment p and
swap the elements at index p with the element at index i.
 oOnce all the elements are traversed, swap pivot with element
present at p+1 as this will the same position as in the sorted
array
o Now return the pivot index
• Once partitioned, now make 2 calls on quicksort
o One from beg to p-1
o Other from p+1 to n-1

Pseudo code:

function partitionFunc(left, right, pivot)

leftPointer = left
rightPointer = right -1

whileTruedo
while A[++leftPointer]< pivot do
//do-nothing
endwhile

while rightPointer >0&& A[--rightPointer]> pivot do

//do-nothing
endwhile

if leftPointer >= rightPointer

break
else
swap leftPointer,rightPointer
endif

endwhile

swap leftPointer,right
return leftPointer

endfunction
Analysis:

Time Complexity
• Partition of elements take n time
• And in quicksort problem is divide by the factor 2
• Best Time Complexity : O(nlogn)
• Average Time Complexity : O(nlogn)
• Worst Time Complexity : O(n^2)
• Worst Case will happen when array is sorted

Space Complexity

• O(n) : basic approach

• O(logn) : modified approach