Bubble Sort

Codes

for (int i = 0; i < values.length - 1; i++) {
	for (int j = 0; j < values.length; j++) {
    	if (values[j] > values[j + 1]) {
        	swap(values, j, j+1);
        }
    }
}

Analysis

Time complexity

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 ~ O(n^2)

• Best case : O(n) by flag
• Worst case : O(n^2)
• Average case : O(n^2)
• Stable : Y
• In-place : Y

---

Selection Sort

Codes

for (int i = 0; i < values.length - 1; i++) {
	int minIndex = i;
    for (int j = i + 1; j < values.length; j++) {
    	if (values[j] < values[minIndex]) {
        	minIndex = j;
        }
    }
    swap(values, i, minIndex);
}

Analysis

• Best case : O(n^2)
• Worst case : O(n^2)
• Average case : O(n^2)
• Much less swaps : O(n)
• Stable : N
• In-place : Y

---

Insertion Sort

Codes

for (int i = 1; i < values.length; i++) {
	int temp = values[i];
    int j = i;
    
    while (j > 0 && values[j-1] > temp) {
    	values[j] = values[j-1];
        j--;
    }
    values[j] = temp;
}

Analysis

• Best case : O(n) comparisons and swaps
• Worst case : O(n^2) comparisons and swaps
• Average case : O(n^2) comparisons and swaps
• Stable : Y
• In-place : Y

---

Comparisons Sort 분석

When # of element grow, Bubble > Selection > Insertion