you will investigate some of these sorting algorithms: *Bidirectional Bubble Sor
ID: 3770588 • Letter: Y
Question
you will investigate some of these sorting algorithms: *Bidirectional Bubble Sort *Bubble Sort *Bucket Sort *Comb Sort *Cycle Sort *Gnome Sort *Heap Sort *Insertion Sort *Merge Sort *Odd-Even Sort *Pigeonhole Sort *Quick Sort *Quick Sort with Bubble Sort *Selection Sort *Shell Sort
Main question:
Compare the algorthims above (at least two) on the performance in terms of efficiency (running time complexity, code size, memory use, etc.) and simplicity (easiness to employ), and write an essay, which contains the following sections: 1)Introduction to sorting algorithms 2) Algorithm description/analysis 3)Algorithm comparison 4)Summary.
Explanation / Answer
Introduction to Sorting Algorithms:
An algorithm used to sort the list of elements in a sorted order either in ascending order or descending order. This technique can be applied for the numerical data or for the lexicographical data. Depending upon this algorithm, other algorithms like search or merge algorithms are made optimized.
In this process, the output should satisfy two conditions. They are:
There are different types of algorithms which are used to sort the elements of a given list. Depending on the run time complexity, size, and efficiency, each algorithm is applied in different applications in today’s computing world. Each algorithm uses different techniques to sort the elements in the given list like bubble sort, counting sort, time sort, linear sort etc.,.
Selection Sort:
Section sort is well known for its in-place comparison sort. It sorts the elements in the given list by dividing the list into two equal parts such as sub lists.
According to Selection sort logic,
Algorithm/Code:
Function SelectionSort(a[], n)
{
int i,j;
//use a loop to advance the move of the boundary
//limits starting from the initial index to the
//n-1 elements
for (i = 0; i < n-1; i++)
{
//consider the index position i to be the
//minimum element in the entire array
int min = i;
//use another loop to test the position
//value is minimum among the all the
//elements in the list
for ( j = i+1; j < n; j++)
{
//test the element at the position j
//with the element present at min
//position. If the element at position
//j is minimum than the a[min] then
//replace the min with j
if (a[j] < a[min])
{
min = j;
}
}
if(min != i)
{
swap(a[i], a[min]);
}
}
}
Analysis:
From the above algorithm,
Therefore, the time complexity or the run time is given as O(n2).
Bubble Sort:
Bubble sort is well known as the sinking sort and the technique used simple sorting.
According to Bubble sort algorithm,
Thus, it pushes the largest element from the minimum position to the largest element. Hence, it got the name as bubble sort.
Algorithm:
Function BubbleSort(a[], n)
{
int i, j, temp, newPos;
while(n!=1)
{
newPos = 1;
for(i=1; i<n-1;i++)
{
if(a[i-1)>a[i])
{
temp = a[i-1];
a[i-1]=a[i];
a[i]=temp;
newPos = i;
}
}
n = newPos;
}
}
Analysis:
From the above algorithm,
Comparisons:
In both the cases of algorithms, the worst case of the algorithm is O(n2).
Algorithm
Worst case performance
Best case performance
Average case performance
Worst case space complexity
Selection sort
O(n2)
O(n2)
O(n2)
Total O(n), auxiliary O(1)
Bubble sort
O(n2)
O(n)
O(n2)
O(1) auxiliary
Conclusion:
In both the cases, the algorithms performs at O(n2) time.
The only changes are:
Algorithm
Worst case performance
Best case performance
Average case performance
Worst case space complexity
Selection sort
O(n2)
O(n2)
O(n2)
Total O(n), auxiliary O(1)
Bubble sort
O(n2)
O(n)
O(n2)
O(1) auxiliary
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.