Why is Quicksort considered an unstable sort

  • Source | wish code (ChainDesk.CN) edit content
  • Wish Code Slogan | Connect the stories of each programmer
  • Website | http: //chaindesk.cn
  • Wishma Vision | Create a Fully Disciplinary IT Free Systems course to help young white users and junior engineers learn free systems at zero cost, at low cost, and help senior BAT engineers grow after bed and take advantage of their own, to generate income.
  • Official public account | Wish Code | Wish Code Service Account | Blockchain tribe
  • Join the Wishcode community for thinking engineers for free | Any official account can reply to the word "Wishcode" to receive the group QR code

Reading time of this article: 6min

Do you understand the difference between QuickSort and MergeSort? What does your stable and unstable sorting algorithm mean?

How should the interviewer answer the above questions?
If the sorting algorithm keeps the relative order of the numbers / records, that is, if you need to sort 1 1 2 3, then the sorting algorithm is considered stable if you don't change the order of the first two sorts, if you swap them, the overall result or the sort order becomes unstable.

This difference becomes more apparent when you sort objects (e.g. sort key-value pairs by key). With a stable algorithm, the original order of the key-value pairs is retained, as shown in the following example.

If you forget to mention these concepts, the interviewer may consider this question to be a consequence of the quick sorting and collating of the sorting.

One of the main differences between quicksort and mergesort is that quicksort is unstable, while mergesort is a stable sorting algorithm. By the way, if you are not familiar with basic sort algorithms like quicksort and mergesort, I recommend you study a comprehensive data structure course like data structure and algorithm: deep use of java. It will give you all the basics you need to explore further.

Stable and unstable algorithms

For example, suppose you need to sort the following key-value pairs in ascending key order:

INPUT : (4.5) (3.2) (4.3) (5.4) (6.4)

Now there are two possible solutions for two pairs with the same key, namely (4,5) and (4,3) as follows:

OUTPUT1 : (3.2) , (4.5) , (4.3) , (5.4) , (6.4)
OUTPUT2 : (3.2) , (4.3) , (4.5) , (5.4) , (6.4)

The sorting algorithm that produces the first output is called the stable sorting algorithm. Since the original order of the same keys is kept, you can see that (4,5) appears before (4,3) in sorted order. This is the original order. This means that (4,5) appears before (4,3) in the given input.

The algorithm that produces the second output is known as the unstable sort algorithm because the order of the objects with the same key is not maintained in the sort order. You can see that (4,3) appears before (4,5) in the second output, which it does not in the original input.

Now the biggest question is what are some examples of stable and unstable sorting algorithms? You can then subdivide all known sorting algorithms into stable and unstable. Some examples of robust algorithms are merge sort, insert sort, bubble sort, and binary tree sort. QuickSort, heap sort, and pick sort are unstable sort algorithms.

If you recall, the Collections.sort () method in the Java Collection framework uses iterative merge sorting, which is a stable algorithm. If the input array is partially sorted, it will compare much less than NLog (N).

If you want to learn more about this topic, I recommend that you study data structures and algorithms such as Algorithms and Data Structures - Part 1 and Part 2. It is one of the most comprehensive courses on algorithms for Java programmers.

Examples of stable and unstable algorithms

The following picture explains how stable and unstable sorting works:

This is the difference between stable and unstable sorting algorithms. Remember that the algorithm is called the sorting algorithm when the original order of like keys or numbers is preserved in the sorted output. Some common examples of robust sort algorithms are merge sort, insert sort, and bubble sort.

What else would you like to know about interview questions? Please leave a message below!