Purchase Solution

Worst Case for Quick Sort Algorithm and Improvement

Not what you're looking for?

Ask Custom Question

Describe the worst case scenario for quick sort algorithm. Any ideas to improve the worst case? Comment on the improvement in running time vs. increase in code complexity.

Purchase this Solution
Solution Summary

Discusses the worst case condition for quick sort algorithm. Also suggests ideas to improve the worst case and comments on the improvement in running time vs. increase in code complexity.

Solution Preview

The worst case for Quicksort depends on the selection of the pivot element. Normally, if the first or the last element is chosen then there is a danger that the all the rest of the numbers need to be moved to the other side of the pivot and this happens recursively. In other words, the worst-case occurs when the input is already sorted. Since, many real-life inputs are nearly sorted, quicksort might perform worse ...

Purchase this Solution
Free BrainMass Quizzes
Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

Javscript Basics

Quiz on basics of javascript programming language.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

View More Free Quizzes
Related BrainMass Solutions

  • Quick sort

    Therefore quick sort cannot guarantee a O(N log N) performance for all array types. Visit the link http://www.cs.wisc.edu/~bobh/367/SORTING.html#quick Quick sort is demonstrated. The median of three worst case scenarios are determined.

  • Sorting Algorithms Comparison

    136056 Sorting Algorithms Comparison We have considered the following sorting algorithms in this book: Heap, Insertion, Merge, Quicksort, Radix, Selection For each sort, give the average and worst case running time and the space requirements, and

  • A basic overview of algorithm analysis

    For a list of n items a bubble sort will take on average N*N (N-squared) operations to perform the sort while the quick sort algorithm will take on average N*log(N) operations.

  • Seating arrangement to increase social contact

    Sort Students array in decreasing order. // Worst case sorting time complexity (p log p). Sort Tables array in decreasing order. // Worst case sorting time complexity (q log q). cavl = q // Currently available tables.

  • Sorting in Java

    b) What is the worst-case runtime of this incorrect algorithm? Give as tight an asymptotic upper bound as possible, using Big-Oh notation as a function of n. Justify your answer.

  • Data structures C++ -- Quick sort Algorithm

    The solution uses the data structure C++ to quick sort an algorithm. The C++ quick sort algorithm is determined.

  • heap structure

    than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime.

  • Sorting Algorithms

    117111 Comparison and Examples of Sorting Algorithms Compare and evaluate performance of various sorting algorithms. Include exchange (bubble) sort, selection sort, insertion sort, quick sort, merge sort and heap sort.

  • Sorting Algorithm in Java

    How do the algorithm techniques of fragmentation affect the end result of sorting through larger amounts? Please see the attached source java code. I use bubble sort and quick sort and compare them.

View More Related Solutions