Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
public class SortingTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] alist = {54,26,93,17,77,31,44,55,20};
printArray(alist);
//selectionSort(alist);
//insertionSort(alist);
mergeSort(alist);
printArray(alist);
}
private static void selectionSort(int[] arr){ // O(N^2)
int numArray = arr.length;
int minIndex;
for (int i = 0; i < numArray; i++ ){ // O(N)
int min = arr[i];
minIndex = i;
for (int j = i+1; j<numArray; j++){ // O(N-1)
if (arr[j] < min){
min = arr[j];
System.out.println(i + " 번째 min: " + min);
minIndex = j;
}
}
arr[minIndex] = arr[i];
arr[i] = min;
// printArray(arr);
}
}
private static void insertionSort(int[] arr){ // O(N^2)
int numArray = arr.length;
int temp;
for (int i = 1; i < numArray; i++) { // 0 부터 시작하면 arr[0] 이전의 원소가 없으므로 1부터 시작
temp = arr[i];
for (int j = i-1; j >= 0 && arr[j] > temp ; j-- ){ // arr[j] is the element to be compared with temp
// loop from arr[i-1] to arr[0]
// stop when arr[j] < temp
// arr[j] temp arr[j+1]
// 54 26 26
// if (arr[j] > temp){ // 54 > 26 26
arr[j+1] = arr[j]; // 54 26 54
arr[j] = temp; // 26 26 54
// }
}
// printArray(arr); // use this for visualizing how it is sorted
}
}
private static void mergeSort(int[] arr){
mergeSortHelper(arr, 0, arr.length-1);
}
private static void mergeSortHelper(int [] arr, int low, int high){
// Step 1 : find the middle of the array
// base case
if (low == high) return;
// recursive case
int mid = ( low + high ) / 2;
// Step 2 and 3: Sort the 2 halves of arr
mergeSortHelper(arr, low, mid);
mergeSortHelper(arr, mid+1, high);
// Step 4: Merge sorted halves into an auxiliary array
int[] tmp = new int[high-low+1];
int left = low;
int right = mid+1;
int pos = 0;
while ((left <= mid) && (right <= high)) {
// choose the smaller of the two values "pointed to" by left, right
// copy that value into tmp[pos]
// increment either left or right as appropriate
// increment pos
if (arr[left] < arr[right]){
tmp[pos] = arr[left];
pos++; left++;
}
else {
tmp[pos] = arr[right];
pos++; right++;
}
}
// when one of the two sorted halves has "run out" of values, but
// there are still some in the other half, copy all the remaining
// values to tmp
// Note: only 1 of the next 2 loops will actually execute
while (left <= mid) {
tmp[pos] = arr[left];
pos++; left++;
}
while (right <= high) {
tmp[pos] = arr[right];
pos++; right++;
}
// all values are in tmp; copy them back into arr
System.arraycopy(tmp, 0, arr, low, tmp.length);
}
private static void printArray(int[] arr){
for (int i : arr){
System.out.print(i + ", ");
}
System.out.println();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.