Question

In: Computer Science

Sorting algorithms are one kind of algorithm whose performance may depend upon the data. Choose one...

Sorting algorithms are one kind of algorithm whose performance may depend upon the data. Choose one of the sorting algorithms or any other algorithm and explain whether the there are any differences in the best, average and worst cases. If there are no differences, explain why not. If there are differences, describe the data in the different cases and explain how the performance differs in each case.

Solutions

Expert Solution

Please let me know if anything is required

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Example: 5 1 4 2 8
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.

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 our 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 )

Worst Time Complexity: O(n*n). Worst case occurs when array is sorted in reverse order.

Average Case Time Complexity : O(n*n). Average Case occurs when array is not sorted.

Best Case Time Complexity: O(n). Best case occurs when array is already sorted.


Related Solutions

Mergesort is known to be one of the fastest algorithms for sorting lists of data. In...
Mergesort is known to be one of the fastest algorithms for sorting lists of data. In fact, the runtime of mergesort is proportional to n· logn where n is the size of the list to be sorted. Bubblesort, on the other hand is a much slower algorithm, since it's runtime is proportional to n2 , where n is the size of the list to be sorted. As an experiment, mergesort is run on a slow computer, bubblesort is run on...
Evaluate the performance in general on two real applications of sorting algorithms in parallel computing. Support...
Evaluate the performance in general on two real applications of sorting algorithms in parallel computing. Support your description with diagrams and examples where it is necessary.
How does one decide upon the size of a sample?  Upon what does this decision depend?
How does one decide upon the size of a sample?  Upon what does this decision depend?
Import a data set (txt file) then do the sorting algorithm using bubble sort, radix sort,...
Import a data set (txt file) then do the sorting algorithm using bubble sort, radix sort, insertion sort, and merge sort, It must show how long it took and how many movements occurred. Please write codes in C++ Here's data set (should be stored in txt file) 7426 4524 4737 9436 3997 2757 6288 5414 9590 5968 6638 3199 9514 1541 9866 2144 6731 911 2171 6135 6437 912 9417 2662 6606 6349 707 2890 5386 9718 3492 5068 9674...
Import a data set (txt file) then do the sorting algorithm using quick sort, shell sort,...
Import a data set (txt file) then do the sorting algorithm using quick sort, shell sort, and selection sort. It must show how long it took and how many movements occurred. Please write codes in C++ Here's data set (should be stored in txt file) 7426 4524 4737 9436 3997 2757 6288 5414 9590 5968 6638 3199 9514 1541 9866 2144 6731 911 2171 6135 6437 912 9417 2662 6606 6349 707 2890 5386 9718 3492 5068 9674 8578 8323...
Please find and share one sorting/searching algorithm. Explain it, and discuss its efficiency with your friends!
Please find and share one sorting/searching algorithm. Explain it, and discuss its efficiency with your friends!
Lorenzo notes that the market includes securities A and B whose prices in one-year depend only...
Lorenzo notes that the market includes securities A and B whose prices in one-year depend only upon whether the market is “up,” “steady,” or “neutral.” A, which has a current share price of $25, will sell for $32,$25, or $22 respectively, while B, with a current share price of $14, will sell for $16, $14, or $12, respectively. Explaining how Lorenzo has an arbitrage opportunity, assuming there are no costs associated with trading A and B.
Sexuality is essential to the way one conceives oneself. It may depend on one's experiences and...
Sexuality is essential to the way one conceives oneself. It may depend on one's experiences and considerations that often fluctuate throughout his or her lifespan. It gets impacted by different biopsychosocial, economic, cultural, religious, and spiritual factors. The textbook states that with the passing time, the emotional, intellectual, and physical aspects of sexual desire and expression become fairly stable in both genders. The Western views have equalized aging with dying, so most of the people probably have a confined view...
1) Please find and share one sorting/searching algorithm. Explain it, and discuss its efficiency 2) Please...
1) Please find and share one sorting/searching algorithm. Explain it, and discuss its efficiency 2) Please find and share algorithm about red/black trees. Explain it, give 2 real world usages and discuss its efficiency 3) Please find and share one algorithm about Binary Search Trees. Explain it, and discuss it's efficiency
Discuss how organisational narrative may impact upon organisational's performance in the context of change management due...
Discuss how organisational narrative may impact upon organisational's performance in the context of change management due to globalization? Please draw upon communication theory and use example to support your claims?
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT