Bugün yaptığım şey, seçtiğim bir sıralama algoritmasını incelemek oldu. Merge Sort’u baştan sona incelemek birçok şeyi hatırlamak için iyi bir karardı sanırım. Java için temel syntaxlar, main memory ve recursion başlıklarının üstünden geçtim. Head Recursion için 2 ayrı örnek üzerinde durdum, ancak çok temel olduklarından burada yalnızca bir tanesine görsel olarak yer vereceğim. Bunlar dışında algoritmanın teorisini ve implementasyonunu incelerken kalem kağıtla neleri not aldığım da burada. Time complexity analysis notlarını daha sonra Latex ile aktaracağım.
İncelediğim merge sort algoritması:
public class Main {
public static void main(String[] args) {
int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };
mergeSort(intArray, 0, intArray.length);
for (int i = 0; i < intArray.length; i++) {
System.out.println(intArray[i]);
}
}
// { 20, 35, -15, 7, 55, 1, -22 }
public static void mergeSort(int[] input, int start, int end) {
if (end - start < 2) {
return;
}
int mid = (start + end) / 2;
mergeSort(input, start, mid);
mergeSort(input, mid, end);
merge(input, start, mid, end);
}
// { 20, 35, -15, 7, 55, 1, -22 }
public static void merge(int[] input, int start, int mid, int end) {
if (input[mid - 1] <= input[mid]) {
return;
}
int i = start;
int j = mid;
int tempIndex = 0;
int[] temp = new int[end - start];
while (i < mid && j < end) {
temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
}
System.arraycopy(input, i, input, start + tempIndex, mid - i);
System.arraycopy(temp, 0, input, start, tempIndex);
}
}
Time complexity analysis:
- Not in-place
- Stable
