Bubble Sort

At the heart of bubbling sort is a double nested loop that continually compares adjacent elements and moves the larger ones to the back, so the larger ones move back, hence the name bubbling.

Algorithm ideas

  1. Compare adjacent elements. If the first one is bigger than the second, swap them both
  2. Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number
  3. Repeat this step for all elements except the last one
  4. Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare

Image from Visualgo

implementation

Java

public class BubbleSort {

    public static void main(String[] args) {
        int[] unsortedArray = new int[] {6.5.3.1.8.7.2.4};
        bubbleSort(unsortedArray);
        System.out.println("After sorted: ");
        for (int number : unsortedArray) {
            System.out.print(""+ number); }}private static void bubbleSort(int[] array) {
        if (array == null || array.length == 0) { // Illegal check
            return;
        }

        int i, temp, len = array.length;
        boolean changed;
        
        do {
            changed = false;
            len -= 1;
            for (i = 0; i < len; i++) {
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    changed = true; }}}while(changed); }}Copy the code

Python

#! /usr/bin/env python
# coding=utf-8


def bubble_sort(arrayList):
    length = len(arrayList)

    for i in range(length - 1):
        count = 0

        for j in range(length - 1 - i):
            if (arrayList[j] > arrayList[j + 1]):
                arrayList[j], arrayList[j + 1] = arrayList[j + 1], arrayList[j]
                count += 1

        if count == 0:
            break


if __name__ == "__main__":
    arrayList = [6.5.3.1.8.7.2.4]
    print("orgin array list: {0}".format(arrayList))
    bubble_sort(arrayList)
    print("after sorted list: {0}".format(arrayList))
Copy the code

Time complexity and space complexity

Best case: positive order order, then only n times need to compare. So to O (n)

Worst case: reverse order, then need to compare (n-1)+(n-2)+… Plus 1, so it’s order n^2.

The space complexity is O(1), since a temporary variable is needed to swap elements (and a variable is necessary for indexing when traversing sequences)

The stability of

Only two adjacent elements are swapped during sorting. So, when two numbers are equal, there’s no need to swap them. So their relative positions don’t change, bubble sort is stable.

conclusion

If you have n numbers to sort by, you only have to put n minus 1 numbers back, which means you have to do n minus 1 operations. In “each trip”, it is necessary to compare the two adjacent numbers from the first place, and put the smaller number behind. After the comparison, move back one place to continue comparing the size of the next adjacent number. Repeat this step until the last unreturned number, and the number that has been returned does not need to be compared.

The core of bubble sort is a double nested loop, and it is easy to see that the time complexity of bubble sort is O(n^2). This is a very high time complexity. So bubble Sort doesn’t seem to have much to recommend it other than its charming name

Selection Sort

Selecting sort is finding the smallest element in the array and swapping it with the first element, then finding the smallest element in the remaining array and swapping it with the second element, and so on, until the entire array is sorted.

Algorithm ideas

  1. Find the smallest element in the array and swap it with the first element
  2. Find the smallest element among the remaining elements and swap it with the second element of the array until the entire array is sorted

Image from Visualgo

implementation

Java

public class SelectionSort {

    public static void main(String[] args) {
        int[] unsortedArray = new int[] {6.5.3.1.8.7.2.4};
        selectionSort(unsortedArray);
        System.out.println("After sorted: ");
        for (int number : unsortedArray) {
            System.out.print(""+ number); }}private static void selectionSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;
        int min;
        int temp;
        for (int i = 0; i < length - 1; i++) {

            min = i;
            for (int j = length - 1; j > i; j--) {
                if(array[min] > array[j]) { min = j; }}if(array[i] > array[min]) { temp = array[i]; array[i] = array[min]; array[min] = temp; }}}}Copy the code

Kotlin

object SelectionSortKt {

    fun selectionSort(array: IntArray) {
        if (array.isEmpty()) {
            return
        }

        val size = array.size
        var min: Int

        for (i in 0 until size - 1) {

            min = i
            (size - 1 downTo i)
                    .asSequence()
                    .filter { array[min] > array[it] }
                    .forEach { min = it }

            if (array[min] < array[i]) {
                val temp = array[i]
                array[i] = array[min]
                array[min] = temp
            }
        }
    }
}

fun main(args: Array<String>) {
    val unsortedArray = intArrayOf(6.5.3.1.8.7.2.4)
    SelectionSortKt.selectionSort(unsortedArray)
    println("After sorted: ")
    unsortedArray.forEach {
        print(" $it")}}Copy the code

Python3

#! /usr/bin/env python
# coding=utf-8


def selection_sort(arrayList):
    length = len(arrayList)
    minIndex = 0

    for i in range(length - 1):
        minIndex = i

        for j in range(length - 1, i, - 1) :if (arrayList[minIndex] > arrayList[j]):
                minIndex = j

        if (arrayList[i] > arrayList[minIndex]):
            arrayList[i], arrayList[minIndex] = arrayList[minIndex], arrayList[
                i]


if __name__ == "__main__":
    arrayList = [6.5.3.1.8.7.2.4]
    print("orgin array list: {0}".format(arrayList))
    selection_sort(arrayList)
    print("after sorted list: {0}".format(arrayList))

Copy the code

Time complexity

Best case: swap 0 times, but find the smallest element each time, so must traverse approximately N*N times, hence O(N^2).

Worst Case & average case: O(N^2)

The stability of

Since the smallest element X in the unordered sequence A is selected and exchanged with the first element in A every time, the distance is crossed and the relative position between elements is likely to be damaged, so the selection sort is unstable

conclusion

Selection sort is a sort similar to bubble sort. Unlike bubble sort, which exchanges linked data, selection sort does not swap until the smallest number of data is determined

Insertion Sort

By building ordered sequences, scan from back to front for unordered sequences (or back to front for unidirectional lists) to find the appropriate position and insert. Implementation usually uses in-place sorting (requires O(1) extra space)

Algorithm ideas

  1. Start with the first element, which can be considered sorted
  2. Takes the next element and scans back to front in the sorted element sequence
  3. If the element (sorted) is larger than the new element, move the element to the next position
  4. Repeat step 3 until you find a place where the sorted element is less than or equal to the new element
  5. After inserting the new element into the location
  6. Repeat steps 2 to 5

Image from Visualgo

implementation

Java

public class InsertionSort {

    public static void main(String[] args) {
        int[] unsortedArray = new int[] {6.5.3.1.8.7.2.4};
        insertionSort(unsortedArray);
        System.out.println("After sorted: ");
        for (int number : unsortedArray) {
            System.out.print(""+ number); }}private static void insertionSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;
        int i,j;
        for (i = 1; i < length; i ++) {

            int holder = array[i];

            for (j = i; j > 0 && array[j - 1] > holder; j--) {
                    array[j] = array[j - 1];
            }

            // The following code logic is wrong, because it must be array[j-1] > holder should be j--
            // The following code executes j-- every time
// for (j = i; j > 0; j--) {
// if (array[j - 1] > holder) {
// array[j] = array[j - 1];
/ /}
/ /}array[j] = holder; }}}Copy the code

Kotlin

object InsertionSortKt {

    fun insertionSort(array: IntArray) {
        if (array.isEmpty()) {
            return
        }

        val size = array.size
        for (i in 1 until size) {

            val holder = array[i]
            var j = i
            while (j > 0 && array[j - 1] > holder) {
                array[j] = array[j - 1]
                j--
            }

            array[j] = holder
        }
    }
}

fun main(args: Array<String>) {
    val unsortedArray = intArrayOf(6.5.3.1.8.7.2.4)
    InsertionSortKt.insertionSort(unsortedArray)
    println("After sorted: ")
    unsortedArray.forEach {
        print(" $it")}}Copy the code

Python3

#! /usr/bin/env python
# coding=utf-8


def insertion_sort(arrayList):
    length = len(arrayList)

    for i in range(1, length):
        holder = arrayList[i]
        j = i
        while(j > 0 and arrayList[j - 1] > holder):
            arrayList[j] = arrayList[j - 1]
            j -= 1

        arrayList[j] = holder


if __name__ == "__main__":
    arrayList = [6.5.3.1.8.7.2.4]
    print("orgin array list: {0}".format(arrayList))
    insertion_sort(arrayList)
    print("after sorted list: {0}".format(arrayList))
Copy the code

Time complexity

Best case: positive order order (from small to large), which requires only n comparisons and no movement. So the time is order n.

Worst case: reverse order, so every element has to be compared n times, n elements, so the actual complexity is O(n^2).

Average case: O(n^2)

Hill sorting

Core: Based on insertion sort, make the array of any interval h elements are ordered, that is, all elements are divided into H regions using insertion sort. The implementation can be similar to insert sort but with a different delta. It is more efficient because it balances the size and order of subarrays

Hill sort is an improved method based on the following two properties of insertion sort:

  • Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort
  • But insert sort is generally inefficient because it can only move data one bit at a time

Algorithm implementation

Improve the performance of insert sort by dividing all the elements being compared into several regions. This allows an element to make one big step towards its final position at a time. Then the algorithm takes smaller and smaller steps for sorting. The last step of the algorithm is normal insert sort, but by this step, the data to be sorted is almost already sorted (insert sort is faster).

If you have an array array = [80, 93, 60, 12, 42, 30, 68, 85, 10], first take d1 = 4 and divide the array into 4 groups.

Then, insert sort was conducted for the 4 groups respectively, and the results after sorting were as follows:

Then, take d2 = 2 and divide the original array into 2 groups, as shown below:

Then, insert sort was conducted for the two groups respectively, and the result after sorting was as follows:

Finally, take D3 = 1 to get the final result after insertion sort:

Shell Sort (Shell Sort)

Step sequence

Step size selection is an important part of Hill sorting. Any sequence of steps will work as long as the final step is 1. The algorithm starts by sorting by a certain step size. It then continues to sort at a certain step size, and eventually the algorithm sorts at a step size of 1. When the step size is 1, the algorithm changes to insertion sort, which guarantees that the data will always be sorted.

The following is a sequence of step sizes with good performance

  1. Shell’s original sequence: N/2 , N/4 , … , 1 (repeatedly divide by 2);
  2. Hibbard’s increments: 1, 3, 7, … , 2k – 1 ;
  3. Knuth’s increments: 1, 4, 13, … , (3k – 1) / 2 ;
  4. Sedgewick’s increments: 1, 5, 19, 41, 109, …. It is obtained by interleaving the elements of two sequences: 1, 19, 109, 505, 2161… . , 9(4k — 2k) + 1, k = 0, 1, 2, 3… 5, 41, 209, 929, 3905… . 2K +2 (2k+2 — 3) + 1, k = 0, 1, 2, 3…

The best known sequence of step sizes was proposed by Sedgewick (1, 5, 19, 41, 109…). . This study also shows that comparison, rather than interchange, is the dominant operation in Hill sorting. Hill sort with this step size sequence is faster than insert sort, even faster than quicksort and heap sort in small arrays, but still slower than quicksort when large amounts of data are involved.

implementation

Java

public class ShellSort {

    public static void main(String[] args) {
        int[] unsortedArray = new int[] {6.5.3.1.8.7.2.4};
        shellSort(unsortedArray);
        System.out.println("After sorted: ");
        for (int number : unsortedArray) {
            System.out.print(""+ number); }}private static void shellSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;

        int gap = length / 2;
        int i, j;

        for (; gap > 0; gap /= 2) { // Shell's original sequence: N/2 , N/4 , ... , 1 (repeatedly divide by 2)
            for (i = gap; i < length; i += gap) {

                int temp = array[i];
                for (j = i; j > 0&& array[j - gap] > temp; j -= gap) { array[j] = array[j - gap]; } array[j] = temp; }}}}Copy the code

Kotlin

object ShellSortKt {

    fun shellSort(array: IntArray) {

        if (array.isEmpty()) {
            return
        }

        val size = array.size
        var gap = size / 2

        while (gap > 0) {

            for (i in gap until size step gap) {

                val temp = array[i]
                var j = i

                while (j > 0 && array[j - gap] > temp) {
                    array[j] = array[j - gap]
                    j -= gap
                }

                array[j] = temp
            }

            gap /= 2}}}fun main(args: Array<String>) {
    val unsortedArray = intArrayOf(6.5.3.1.8.7.2.4)
    ShellSortKt.shellSort(unsortedArray)
    println("After sorted: ")
    unsortedArray.forEach {
        print(" $it")}}Copy the code

Python3

#! /usr/bin/env python
# coding=utf-8


def shell_sort(arrayList):
    length = len(arrayList)

    gap = length // 2
    while (gap > 0) :for i in range(gap, length, gap):
            holder = arrayList[i]
            j = i
            while (j > 0 and arrayList[j - gap] > holder):
                arrayList[j] = arrayList[j - gap]
                j -= gap

            arrayList[j] = holder

        gap //= 2


if __name__ == "__main__":
    arrayList = [6.5.3.1.8.7.2.4]
    print("orgin array list: {0}".format(arrayList))
    shell_sort(arrayList)
    print("after sorted list: {0}".format(arrayList))
Copy the code

conclusion

A more understandable implementation of Hill sort is to put array columns in a table and sort the columns (by insertion sort). Repeat the process, but each time with a longer column. You end up with just one column. Converting an array to a table is to better understand the algorithm, which itself only sorts the original array (by increasing the step size of the index, for example I += step_size instead of I ++).

reference

  • Summary of sorting algorithm
  • Data structures and Algorithms/Leetcode/LintCode
  • Aha! algorithm
  • Visualgo
  • wikipedia