Practical No:5
Write a python program to store first year percentage of students in array. Write
function for sorting array of floating point numbers in ascending order using
a) Selection Sort
b) Bubble sort and display top five scores.
Pre-requisite:
• Basics of Sorting Techniques
• Different types of Sorting Techniques
Objective:
• To Sorting operations on Array
Input:
• Size of Array
• Elements in Array
• One for selection sort and other for Bubble sort
Outcome:
• Result of ascending order by using Selection sort.
• Result of Top five numbers by using Bubble sort.
Description:
Bubble Sort
Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-
based algorithm in which each pair of adjacent elements is compared and the
elements are swapped if they are not in order. This algorithm is not suitable for
large data sets as its average and worst case complexity are of Ο(n2) where n is
the number of items.
How Bubble Sort Works?
We take an unsorted array for our example. Bubble sort takes Ο(n2) time so
we're keeping it short and precise.
Bubble sort starts with very first two elements, comparing them to check which
one is greater.
In this case, value 33 is greater than 14, so it is already in sorted locations.
Next, we compare 33 with 27.
We find that 27 is smaller than 33 and these two values must be swapped.
The new array should look like this −
Next we compare 33 and 35. We find that both are in already sorted positions.
Then we move to the next two values, 35 and 10.
We know then that 10 is smaller 35. Hence they are not sorted.
We swap these values. We find that we have reached the end of the array.
After one iteration, the array should look like this −
To be precise, we are now showing how an array should look like after each
iteration. After the second iteration, it should look like this −
Notice that after each iteration, at least one value moves at the end.
And when there's no swap required, bubble sorts learns that an array is
completely sorted.
Selection Sort
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place
comparison-based algorithm in which the list is divided into two parts, the
sorted part at the left end and the unsorted part at the right end. Initially, the
sorted part is empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with
the leftmost element, and that element becomes a part of the sorted array. This
process continues moving unsorted array boundary by one element to the
right.
This algorithm is not suitable for large data sets as its average and worst case
complexities are of Ο(n2), where n is the number of items.
How Selection Sort Works?
Consider the following depicted array as an example.
For the first position in the sorted list, the whole list is scanned sequentially.
The first position where 14 is stored presently, we search the whole list and
find that 10 is the lowest value.
So we replace 14 with 10. After one iteration 10, which happens to be the
minimum value in the list, appears in the first position of the sorted list.
For the second position, where 33 is residing, we start scanning the rest of the
list in a linear manner.
We find that 14 is the second lowest value in the list and it should appear at
the second place. We swap these values.
After two iterations, two least values are positioned at the beginning in a sorted
manner.
The same process is applied to the rest of the items in the array.
Following is a pictorial depiction of the entire sorting process −
Algorithms:
We assume list is an array of n elements. We further assume
that swap function swaps the values of the given array elements.
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
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;
end if
end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure
Program: Write your own program and attach printouts
Output:
Conclusion:
By this way, we can perform different sorting operation on array.
Question Bank:
1. What is stability of sorting?
2. What are the different sorting techniques?
3. Explain all the sorting?
Practical No:6
Write a python program to store 12th class percentage of students in array.
Write function for sorting array of floating point numbers in ascending order
using bucket sort and display top five scores.
Pre-requisite:
• Basics of Sorting Techniques
• Different types of Sorting Techniques
Objective:
• To Sorting operations on Array
Input:
• Size of Array
• Elements in Array
Outcome:
• Result of ascending order by using Bucket sort.
Description:
In the Bucket Sorting technique, the data items are distributed in a set of
buckets. Each bucket can hold a similar type of data. After distributing, each
bucket is sorted using another sorting algorithm. After that, all elements are
gathered on the main list to get the sorted form.
The complexity of the Bucket Sort Technique
• Time Complexity: O(n + k) for best case and average case and O(n^2)
for the worst case.
• Space Complexity: O(nk) for worst case
Bucket Sort is a sorting algorithm that divides the unsorted array elements into
several groups called buckets. Each bucket is then sorted by using any of the
suitable sorting algorithms or recursively applying the same bucket algorithm.
Finally, the sorted buckets are combined to form a final sorted array.
Scatter Gather Approach
The process of bucket sort can be understood as a scatter-gather approach.
Here, elements are first scattered into buckets then the elements in each
bucket are sorted. Finally, the elements are gathered in order.
Working of Bucket Sort
Working of Bucket Sort
1. Suppose, the input array is:
2. Input array
Create an array of size 10. Each slot of this array is used as a bucket for
storing elements.
Array in which each position is a bucket
3. Insert elements into the buckets from the array. The elements are inserted
according to the range of the bucket.
In our example code, we have buckets each of ranges from 0 to 1, 1 to 2, 2 to
3,...... (n-1) to n.
Suppose, an input element is .23 is taken. It is multiplied by size =
10 (ie. .23*10=2.3). Then, it is converted into an integer (ie. 2.3≈2). Finally,
.23 is inserted into bucket-2.
Insert elements into the buckets from the array
Similarly, .25 is also inserted into the same bucket. Everytime, the floor value
of the floating point number is taken.
If we take integer numbers as input, we have to divide it by the interval
(10 here) to get the floor value.
Similarly, other elements are inserted into their respective buckets.
Insert all the elements into the buckets from the array
4. The elements of each bucket are sorted using any of the stable sorting
algorithms. Here, we have used quicksort (inbuilt function).
Sort the elements in each bucket
5. The elements from each bucket are gathered.
It is done by iterating through the bucket and inserting an individual element
into the original array in each cycle. The element from the bucket is erased
once it is copied into the original array.
Gather elements from each bucket
Algorithms :
Bucket Sort Algorithm
bucketSort()
create N buckets each of which can hold a range of values
for all the buckets
initialize each bucket with 0 values
for all the buckets
put elements into buckets matching the range
for all the buckets
sort elements in each bucket
gather elements from each bucket
end bucketSort
Program: Write your own program
Output:
Conclusion:
