Blog Details

Bucket Sort, Bubble Sort, Selection Sort, and Quick Sort

1. Description

There are lots of common sorting algorithms, such as merge sort, insertion sort, bubble sort, quick sort, heap sort, and so on. It is commonly used in the programming world. No matter what kind of problems you are trying to solve. Here, I will do a short description of bucket sort, bubble sort, selection sort, and quicksort. And list the code in Java below.

Inputs: 12, 35, 99, 18, 76

Outputs: 12, 18, 35, 76, 99

2. Solutions

  • Bucket sort: The time complexity is O(M+N). The size of the bucket is not depending on the size of the array. However, it is depending on the value of the items of the array.
public static void bucketSort(int[] array) {
        // initialize the whole array list into 0
        // since the value of the arraylist is less than 100, then we must
        // allocate 99 seats for the whole values
        int[] bucket = new int[100];
        for (int i = 0; i < 100; i++) {
            bucket[i] = 0;
        }
        // for certain value, the bucket will add 1;
        for (int i = 0; i < array.length; i++) {
            bucket[array[i]]++;
        }
        // print the result
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] != 0) {
                if (i < bucket.length - 1) {
                    System.out.print(i + ", ");
                } else {
                    System.out.print(i);
                }
            }
        }
        System.out.println();
}
  • Bubble sore: Time complexity is O(n^2).
public static void bubbleSort(int[] array) {
        System.out.print("The bubble sort result is: ");
        // swap two integer values
        int dwTemp = 0;
        // loop the whole array
        for (int i = 0; i < array.length; i++) {
            // for each loop, if the first value is greater than the second
            // value,
            // then, swap those two values.
            for (int j = 0; j < array.length - 1; j++) {
                if (array[j] > array[j + 1]) {
                    dwTemp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = dwTemp;
                }
            }
        }
        // Printing the result.
        for (int i = 0; i < array.length; i++) {
            if (i < array.length - 1) {
                System.out.print(array[i] + ", ");
            } else {
                System.out.print(array[i]);
            }
        }
        System.out.println();
}
  • Quick Sort: It is good for sorting big data volume. The divide-conquer strategy is used in quicksort. Follow three steps to solve the problem: 1. choose a pivot value, if the value in the middle that should be good. 2. Partition: from left to right. 3. Sort both parts.
public static int partition(int[] array, int low, int high){
        int dwLeftGuard = low;
        int dwRightGuard = high;
        int dwTemp = 0;
        int dwKey = array[(low + high) / 2];
        while(dwLeftGuard <= dwRightGuard){
            while(array[dwLeftGuard] < dwKey)
                dwLeftGuard ++;
            while(array[dwRightGuard] > dwKey)
                dwRightGuard --;
            if (dwLeftGuard <= dwRightGuard) {
                dwTemp = array[dwLeftGuard];
                array[dwLeftGuard] = array[dwRightGuard];
                array[dwRightGuard] = dwTemp;
                dwLeftGuard ++;
                dwRightGuard --;
            }
        }
        return dwLeftGuard;
}
public static void quickSort(int[] array, int low, int high) {
        int index = CheckExistDemo.partition(array, low, high);
        if (low < index - 1) {
            quickSort(array, low, index - 1);
        }
        if (index < high) {
            quickSort(array, index, high);
        }
}
//Another way to do quick sort
public void quickSort(int[] array, int left, int right) {
	if(left > right) return;
	
	int temp = array[left];
	int i = left;
	int j = right;
	
	while(i != j) {
		
		while(array[j] >= temp && i < j) {
			j --;
		}
		
		while(array[i] <= temp && i < j) {
			i ++;
		}
		
		if(i < j) {
			int swapTemp = array[i];
			array[i] = array[j];
			array[j] = swapTemp;
		}
	}
	
	array[left] = array[i];
	array[i] = temp;
	
	quickSort(array, left, i - 1);
	quickSort(array, i + 1, right);
}
  • Selection sort: find the smallest element using a linear scan, and then find the second smallest element, and move it to the front. Time complexity is O(n^2).
public static void selectionSort(int[] array){
        int dwTemp = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    dwTemp = array[j];
                    array[j] = array[i];
                    array[i] = dwTemp;
                }
            }
        }
        // print the result
        System.out.print("The selection sort result is: ");
        for (int i = 0; i < array.length; i++) {
            if (i < array.length - 1) {
                System.out.print(array[i] + ", ");
            } else {
                System.out.print(array[i]);
            }
        }
}

3. Wrap up

Linear sort:

AlgorithmTime ComplexityStable?In place?
Bubble SortO(n^2)YesYes
Insert SortO(n^2)YesYes
Select SortO(n^2)NoYes
Quick SortO(nlogn)NoYes
Merge SortO(nlogn)YesNo
Counting SortO(n + k)YesNo
Bucket SortO(n)YesNo
Radix SortO(dn), d is the levelYesNo