15.Stable vs Non_stable
15 May 2020 | Data structure_1
Introduction
- Sometimes the order of data within data structures is important. Certain sorting algorithms adhere to this importance, while others don’t. If a data structure takes order in to account(视为), we call it stable, if it doesn’t, we call it not stable or non-stable.
Why is it Important?
- It is important to understand what stability is. There are a lot of cases where stability matters, and understanding which sorting algorithms will get you a stable or non-stable result is important
Lesson Notes
- Say we have a data set that contains groups of information. It looks like this:
{
(Bob, A)
(Chris, B)
(Kathy, A)
(Phillis, B)
}
-
This algorithm is already sorted in to alphabetic order. Now, let’s say we want to sort this algorithm based on the letters on the back end, so A’s come before B’s.
-
If we use a non-stable sorting algorithm, we could very well get a result that looks like this:
{
(Chris, A)
(Phillis, A)
(Kathy, B)
(Bob, B)
}
-
If you notice, the A’s and B’s have been sorted, however the order of the names wasn’t respected (Kathy now comes before Bob). Because of the non-stable nature of the sorting algorithm, we lost the alphabetical grouping of the names.
-
This is situation where a stable sorting algorithm would be important. If we applied a stable sorting algorithm to this group, we would instead get:
{
(Chris, A)
(Phillis, A)
(Bob, B)
(Kathy, B)
}
- Now, not only are the names sorted by A’s and B’s, but they are also sorted with respect to the order they came in, which was alphabetical.
Sorting Algorithms
- Bubble Sort: Stable – This algorithm is stable because it just swaps the largest value up the structure to the top. If two objects are the same, no swap takes place. This means equal values that were to the left will stay to the left.
- (2a 1 2b) -> (1 2a 2b) (The 2a will never swap with the 2b because swaps don’t take place when two values are equal)
- Selection Sort: Nonstable – By default selection sort isn’t stable. This is because it takes a number and swaps it to the left “sorted” side. This gives the possibility that a number can be swapped behind another equal number.
- (2a 2b 1) -> (1 2b 2a) (The 2a was swapped with the lowest number 1 which was on the right side of 2b. The swap takes place, and the order is not preserved)
-
Insertion Sort: Stable – Insertion sort uses a similar swapping mechanism as Bubble sort. It starts from the right while swapping, but never swaps equal values, meaning there is never a chance for elements positions to be flipped.
- Quick Sort: Nonstable – Quick sort uses a splitting mechanism to order to sort. If this “pivot” is a number which has a duplicate, there is a good chance the order will be broken.
- (2a 2b 1) -> (1 2b 2a) (In this scenario, 2b was chosen as the pivot, anything less than it went to the left, and anything greater than or equal went to the right. 2a is equal so it went to the right, breaking the stability of the algorithm)
- Merge Sort: Stable – Merge Sort splits up the data and recombines it in a way that grabs the smallest element and sticks it back in to the array. It however adheres to the order of values, giving preference to values that are in the left subarray to maintain order.
Quiz
Introduction
- Sometimes the order of data within data structures is important. Certain sorting algorithms adhere to this importance, while others don’t. If a data structure takes order in to account(视为), we call it stable, if it doesn’t, we call it not stable or non-stable.
Why is it Important?
- It is important to understand what stability is. There are a lot of cases where stability matters, and understanding which sorting algorithms will get you a stable or non-stable result is important
Lesson Notes
- Say we have a data set that contains groups of information. It looks like this:
{ (Bob, A) (Chris, B) (Kathy, A) (Phillis, B) }
-
This algorithm is already sorted in to alphabetic order. Now, let’s say we want to sort this algorithm based on the letters on the back end, so A’s come before B’s.
-
If we use a non-stable sorting algorithm, we could very well get a result that looks like this:
{ (Chris, A) (Phillis, A) (Kathy, B) (Bob, B) }
-
If you notice, the A’s and B’s have been sorted, however the order of the names wasn’t respected (Kathy now comes before Bob). Because of the non-stable nature of the sorting algorithm, we lost the alphabetical grouping of the names.
-
This is situation where a stable sorting algorithm would be important. If we applied a stable sorting algorithm to this group, we would instead get:
{ (Chris, A) (Phillis, A) (Bob, B) (Kathy, B) }
- Now, not only are the names sorted by A’s and B’s, but they are also sorted with respect to the order they came in, which was alphabetical.
Sorting Algorithms
- Bubble Sort: Stable – This algorithm is stable because it just swaps the largest value up the structure to the top. If two objects are the same, no swap takes place. This means equal values that were to the left will stay to the left.
- (2a 1 2b) -> (1 2a 2b) (The 2a will never swap with the 2b because swaps don’t take place when two values are equal)
- Selection Sort: Nonstable – By default selection sort isn’t stable. This is because it takes a number and swaps it to the left “sorted” side. This gives the possibility that a number can be swapped behind another equal number.
- (2a 2b 1) -> (1 2b 2a) (The 2a was swapped with the lowest number 1 which was on the right side of 2b. The swap takes place, and the order is not preserved)
-
Insertion Sort: Stable – Insertion sort uses a similar swapping mechanism as Bubble sort. It starts from the right while swapping, but never swaps equal values, meaning there is never a chance for elements positions to be flipped.
- Quick Sort: Nonstable – Quick sort uses a splitting mechanism to order to sort. If this “pivot” is a number which has a duplicate, there is a good chance the order will be broken.
- (2a 2b 1) -> (1 2b 2a) (In this scenario, 2b was chosen as the pivot, anything less than it went to the left, and anything greater than or equal went to the right. 2a is equal so it went to the right, breaking the stability of the algorithm)
- Merge Sort: Stable – Merge Sort splits up the data and recombines it in a way that grabs the smallest element and sticks it back in to the array. It however adheres to the order of values, giving preference to values that are in the left subarray to maintain order.
Comments