Sort

12 Mar 2022 . algorithm .

Bubble Sort

Compare adjacent elements. If the first one is bigger than the second one, exchange them.
Do the same work on each pair of adjacent elements, so that the last element should be the largest number.
Repeat the above steps for all elements, except for the last one;
Repeat steps 1 to 3 until the sort is complete.

Code

public static int[] bubbleSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
                // if true, the loop has not been swapped
                boolean flag = true;
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                                // Change flag
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
    return arr;
}

Selection Sort

Find the smallest (largest) element in the unordered sequence and store it in the starting position of the sorted sequence.
Then continue to look for the smallest (largest) element from the remaining unsorted elements, and then put it at the end of the sorted sequence.
Repeat step 2 until all elements are sorted.

Code

public static int[] selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
    return arr;
}

Insertion Sort

Starting from the first element, the element can be considered to have been sorted.
Retrieve the next element and scan it backward in the sorted sequence.
If the element (ordered) is larger than the new element, move the element to the next position.
Repeat step 3 until you find the position of the sorted element less than or equal to the new element.
After inserting the new element into this position, this sequence with new element is sorted.
Repeat steps 2 to 5.

Code

public static int[] insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int preIndex = i - 1;
        int current = arr[i];
        while (preIndex >= 0 && current < arr[preIndex]) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex -= 1;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

Shell Sort

Code

public static int[] shellSort(int[] arr) {
    int n = arr.length;
    int gap = n / 2;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int current = arr[i];
            int preIndex = i - gap;
                        // Insertion sort
                        while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex + gap] = current;
        }
        gap /= 2;
    }
    return arr;
}

Merge Sort

If there is only one element, it will be returned directly. Otherwise the input sequence of length n will be divided into two subsequences of length n/2.
The two subsequences are merge sorted separately to make the subsequences orderly.
Set two pointers to the starting position of the two sorted subsequences.
Compare the elements pointed to by the two pointers, select the smaller element and put it into the merge space (storing the sorting results), and move the pointer to the next position.
Repeat steps 3 to 4 until a pointer reaches the end of the sequence;
Copy all the remaining elements of another sequence directly to the end of the merged sequence.

Code

public static int[] mergeSort(int[] arr) {
    if (arr.length <= 1) {
        return arr;
    }
    int middle = arr.length / 2;
    int[] arr_1 = Arrays.copyOfRange(arr, 0, middle);
    int[] arr_2 = Arrays.copyOfRange(arr, middle, arr.length);
    return merge(mergeSort(arr_1), mergeSort(arr_2));
}

public static int[] merge(int[] arr_1, int[] arr_2) {
    int[] sorted_arr = new int[arr_1.length + arr_2.length];
    int idx = 0, idx_1 = 0, idx_2 = 0;
    while (idx_1 < arr_1.length && idx_2 < arr_2.length) {
        if (arr_1[idx_1] < arr_2[idx_2]) {
            sorted_arr[idx] = arr_1[idx_1];
            idx_1 += 1;
        } else {
            sorted_arr[idx] = arr_2[idx_2];
            idx_2 += 1;
        }
        idx += 1;
    }
    if (idx_1 < arr_1.length) {
        while (idx_1 < arr_1.length) {
            sorted_arr[idx] = arr_1[idx_1];
            idx_1 += 1;
            idx += 1;
        }
    } else {
        while (idx_2 < arr_2.length) {
            sorted_arr[idx] = arr_2[idx_2];
            idx_2 += 1;
            idx += 1;
        }
    }
    return sorted_arr;
}

Quick Sort

Randomly select an element from the sequence as a pivot.
Partition: put all elements smaller than the pivot in front of it, and put all elements larger than the pivot behind it (the same number can be on either side). At the end of this operation, the pivot is in the middle of the sequence.
Recursively quickly sort subsequences smaller than the pivot and the subsequence greater than the pivot.

Code

public static int partition(int[] array, int low, int high) {
    int pivot = array[high];
    int pointer = low;
    for (int i = low; i < high; i++) {
        if (array[i] <= pivot) {
            int temp = array[i];
            array[i] = array[pointer];
            array[pointer] = temp;
            pointer++;
        }
    }
    int temp = array[pointer];
    array[pointer] = array[high];
    array[high] = temp;
    return pointer;
}

public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int position = partition(array, low, high);
        quickSort(array, low, position - 1);
        quickSort(array, position + 1, high);
    }
}

Heap Sort

Build the initial sequence (R1, R2, …, Rn) into a max heap.
The heap top element R[1] is exchanged with the last element R[n]. A new disordered region (R1, R2, ……, Rn-1) and a new ordered region (Rn) are obtained, satisfying R[1, 2, ……, n-1]<=R[n].
Since the new heap root R[1] may violate the heap, adjust the current disordered region (R1, R2, …, Rn-1) to the new max heap.
Exchange R[1] (might be new one) with the last element of the disordered region again to obtain a new disordered region (R1, R2, …, Rn-2) and the new ordered region (Rn-1, Rn). Repeat this process until the number of elements in the ordered area is n-1, and the whole sorting process is completed.

Code

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

private static void buildMaxHeap(int[] arr) {
        // 左孩子是最后一个结点 2*i+1=n-1 => i=n/2-1
        // 右孩子是最后一个结点 2*i+2=n-1 => i=n/2-1
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        heapify(arr, i);
    }
}

private static void heapify(int[] arr, int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (right < heapLen && arr[right] > arr[largest]) {
        largest = right;
    }
    if (left < heapLen && arr[left] > arr[largest]) {
        largest = left;
    }
    if (largest != i) {
        swap(arr, largest, i);
        heapify(arr, largest);
    }
}

public static int[] heapSort(int[] arr) {
    // index at the end of the heap
    heapLen = arr.length;
    // build MaxHeap
    buildMaxHeap(arr);
    for (int i = arr.length - 1; i > 0; i--) {
        // Move the top of the heap to the tail of the heap in turn
        swap(arr, 0, i);
        heapLen -= 1;
        heapify(arr, 0);
    }
    return arr;
}

Counting Sort

Find the maximum value max and the minimum value min in the array.
Create a new array C, whose length is max-min+1, and the default value of its elements is 0.
Traverse the element A[i] in the original array A, with A[i]-min as the index of the C array, and the number of occurrences of elements A[i] in A as the value of C[A[i]-min].
Change C array, the value of the new element is the sum of the value of the element and the previous element, when i>1, C[i] = C[i] + C[i-1].
Create the result array R, which is the same length as the original array.
Traverse element A[i] in the original array A backward, using A[i]-min as an index, find the corresponding value C[A[i]-min] in the counting array C, and C[A[i]-min]-1 is the index of A[i] in the result array. After completing the above operations, reduce the C[A[i]-min] by 1.

Code

private static int[] getMinAndMax(int[] arr) {
    int maxValue = arr[0];
    int minValue = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > maxValue) {
            maxValue = arr[i];
        } else if (arr[i] < minValue) {
            minValue = arr[i];
        }
    }
    return new int[] { minValue, maxValue };
}
    
public static int[] countingSort(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    int[] extremum = getMinAndMax(arr);
    int minValue = extremum[0];
    int maxValue = extremum[1];
    int[] countArr = new int[maxValue - minValue + 1];
    int[] result = new int[arr.length];

    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - minValue] += 1;
    }
    for (int i = 1; i < countArr.length; i++) {
        countArr[i] += countArr[i - 1];
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        int idx = countArr[arr[i] - minValue] - 1;
        result[idx] = arr[i];
        countArr[arr[i] - minValue] -= 1;
    }
    return result;
}

Bucket Sort

Set a BucketSize as how many different values can be placed in each bucket.
Traverse the input data and map the data to the corresponding bucket.
Sort each non-empty bucket, you can use other sorting methods, or recursively use bucket sorting.
Retrieve the ordered data from the non-empty buckets.

Code

private static int[] getMinAndMax(List<Integer> arr) {
    int maxValue = arr.get(0);
    int minValue = arr.get(0);
    for (int i : arr) {
        if (i > maxValue) {
            maxValue = i;
        } else if (i < minValue) {
            minValue = i;
        }
    }
    return new int[] { minValue, maxValue };
}
    
public static List<Integer> bucketSort(List<Integer> arr, int bucket_size) {
    if (arr.size() < 2 || bucket_size == 0) {
        return arr;
    }
    int[] extremum = getMinAndMax(arr);
    int minValue = extremum[0];
    int maxValue = extremum[1];
    int bucket_cnt = (maxValue - minValue) / bucket_size + 1;
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < bucket_cnt; i++) {
                // From bucket0-bucket_cnt
        buckets.add(new ArrayList<Integer>());
    }
    for (int element : arr) {
        int idx = (element - minValue) / bucket_size;
        buckets.get(idx).add(element);
    }
    for (int i = 0; i < buckets.size(); i++) {
        if (buckets.get(i).size() > 1) {
            buckets.set(i, sort(buckets.get(i), bucket_size / 2));
        }
    }
    ArrayList<Integer> result = new ArrayList<>();
    for (List<Integer> bucket : buckets) {
        for (int element : bucket) {
            result.add(element);
        }
    }
    return result;
}

Radix Sort

Get the maximum number in the array and get the number of digits, which is the number of iterations N (for example, if the maximum value in the array is 1000, then N = 4).
A is the original array, taking each digit to form a radix array.
Assign radix to the original array.
Repeat 2 to 4 steps N times.

Code

public static int[] radixSort(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
        // Iteration times
    int N = 1;
    int maxValue = arr[0];
    for (int element : arr) {
        if (element > maxValue) {
            maxValue = element;
        }
    }
    while (maxValue / 10 != 0) {
        maxValue = maxValue / 10;
        N += 1;
    }
    for (int i = 0; i < N; i++) {
        List<List<Integer>> radix = new ArrayList<>();
        for (int k = 0; k < 10; k++) {
            radix.add(new ArrayList<Integer>());
        }
        for (int element : arr) {
            int idx = (element / (int) Math.pow(10, i)) % 10;
            radix.get(idx).add(element);
        }
        int idx = 0;
        for (List<Integer> l : radix) {
            for (int n : l) {
                arr[idx++] = n;
            }
        }
    }
    return arr;
}