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?
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?
Discuss how organisation narrative may impact upon organisation's performance in the context of change management due...
Discuss how organisation narrative may impact upon organisation's performance in the context of change management due to globalization?
Please choose a publicly traded company to work on. You may select a company whose securities...
Please choose a publicly traded company to work on. You may select a company whose securities are traded on the NYSE, AMEX or NASDAQ. Please do not select a company that is a financial institution or services company. The company should sell merchandise. Part I Fill in some basic information about your company. Name of company ______________________________________ Principal exchange where the company trades _______________ Market price of the stock ________________ as of _____________ (date) Annual dividend ________________________________________ Last dividend paid...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT