Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.


preface

This is the third in our elegant series, and we’re going to take a look at sorting by hand.

How to gracefully implement binary search

How to implement bubble sort elegantly

Algorithm description

  1. Divide the array into two subsets, sorted and unsorted. Each round picks the smallest element from the unsorted subset and puts it into the sorted subset
  2. Repeat until the array is in order

Algorithm implementation

    private static void selection(int[] a){
        for (int i = 0; i < a.length - 1; i++) {
            int smallIndex = i;
            for(int j = smallIndex + 1; j < a.length; j ++) {if(a[smallIndex] > a[j]){ smallIndex = j; }}if(i ! = smallIndex) { swap(a, i, smallIndex); }}}private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
Copy the code

I have to say, it’s not that hard to pick sort, it’s not that hard to understand, but there’s a little bit to realize, and that’s how you represent the sorted interval and the unsorted interval, and you can see that we’re increasing the sorted interval by I going to the right, and j is pointing to the unsorted interval, So this extra variable, smallIndex, is actually pointing to the smallest value that’s not sorted.

It is also important to note that the inner for loop does not swap directly in the if, but instead records that the index gets the smallest value after the round selection is completed before it is placed into the sort range.

Also, when I is the same as smallIndex, there is no need to replace it, because I is already the smallest position.

Okay, so that’s it for selection sort, and now we can do a little comparison with bubble sort.

So before we do that, let’s talk about the concept of algorithm stability. For example, if you have two numbers that are the same, and they don’t change their positions relative to each other before and after sorting, we call that a stability algorithm.

Select sort compared to bubble sort

  1. The average time is n squared
  2. Selection sort is generally faster than bubbling because there are fewer swaps
  3. If the order of the set is high, bubbling is better than selection
  4. Bubble is a stable sorting algorithm, selection is an unstable sorting algorithm

The last

On the comparison of algorithms, we can from several aspects to consider, time complexity and space complexity, is stable, the array of initial state, the above points also need not go back, understand the algorithm is to understand the advantages and disadvantages between them, to remember these differences are not enough, there is a lot of algorithm, the key is to understand ideas of the algorithm.