Copyright

Quick Sort in Java: Functionality, Implementation & Performance

Instructor: Gary Dohmeier II

Gary is an independent consultant, working in IT for over 25 years. He has a BS in Computer Science from the Univ. of Baltimore.

This lesson will explain how Quick Sort works including its algorithm and implementation in Java. A simple implementation in Java will be presented. The performance and efficiency measured in Big-O notation will be discussed.

Sorting

Sorting is a common requirement in computer science. It's as a way to take a list that is out of order and put it into an order, for example, thing A to thing Z or 1 to 10. What is the fastest and most efficient way to take an unordered list and make it ordered?

There are two major sorting methods, internal and external. In internal sorting, the memory provided is large enough to hold the entire data set. External sorting is when the data exceeds the memory available and an additional merging step is required. We will be considering the case of internal sorting. There are several different types of sorting algorithms: insertion, selection, exchange, and merge. Quick Sort is a type of exchange sort.

Quick Sort

All sorts need to compare elements in the list so that they can be placed in order. In an exchange sort, pairs of elements in the list are repeatedly compared and if they are out of order they are exchanged. The Quick Sort was developed by Tony Hoare in the early 1960's and is considered one of the fastest internal sorting methods. The main idea behind the Quick Sort is a fairly simple divide and conquer method called a partition-exchange sort. The most common implementation of Quick Sort involves recursion. Recursion or re-entrance is the concept of program code that calls itself. In a recursive routine, there is a test for the end condition that allows the routine to unwind returning the results from each of the calls to itself, thereby producing the final result.

This example illustrates how a recursive routine calls itself and how it satisfies the end condition and returns.


recursive factorial routine


Algorithm

  1. Select a partitioning element from the list (there are different methods for this, we will choose the first element for simplicity).
  2. Reorder the list by comparing items with the pivot and exchanging them. Place items less than the pivot before it in the list and items greater than the pivot after it in the list. The last exchange operation puts the pivot into its final position.
  3. Recursively apply this same approach to the 'left' list and the 'right' list.

Let's look at how this works.

visual representation of quicksort algorithm


Pseudocode

In order to implement the Quick Sort, we can develop the basic logic of the algorithm with pseudocode, a generic form of coding that does not have to adhere to a formal language specification.

algorithm qsort ( data[], left , right )

 if left >= right

  return

 swap data[left] with data[(left+right)/2)]

 last = left

 loop for i = left+1 to i <= right increment by i

  if data[i] < data[left]

   swap data[last+1] with data[i]

 swap data[left] with data[last]

 qsort ( data[], left, last-1 )

 qsort ( data[], last+1, right )


Java Implementation

This is a simple but fully functional version of the Quick Sort in Java. You can use the pseudocode to build your own implementation and use the code as a reference for validation.

With a Java implementation of the Quick Sort, you can move the sort data out of the function and into private class data. In addition, you can move the swap function into its own private method which can be reused as needed in the sort. Although the partitioning function is included in the qsort method, it could be handled separately by its own method.

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create An Account
Support