합병정렬 (Merge Sort)

• 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식
• 시간 복잡도: $O(nlogn)$

public static void mergeSort(int[] arr, int[] tmp, int left, int right){
	if(left<right){
    	int mid = (left+right) /2;
        mergeSort(arr, tmp, left, mid);
        mergeSort(arr, tmp, mid+1, right);
        merge(arr, tmp, right, mid);
	}
}
public static void merge(int[] arr, int[] tmp, int left, int right, int mid){
	int p = left;
    int q = mid+1;
    int idx = p;
    while(p <= || q <= right){
    	if(p <= mid && q<= right){
        	if(arr[p] <= arr[q]){
            	tmp[idx++] = arr[p++];
			} else {
            	tmp[idx++] = arr[q++];
			} 
		} else if(p <= mid && q > right) {
        	tmp[idx++] = arr[p++];
		} else {
        	tmp[idx++] = arr[q++];
		}
	}
    for (int i = left; i<= right; i++){
    	arr[i] = tmp[i];
	}
}
public static void main(String[] args){
	int[] arr = {3,5,2,7,1,4,6};
    int[] tmp = new int[arr.length];
    mergeSort(arr, tmp, 0, arr.length-1);
    System.out.println(Arrays.toString(arr));
}

힙 정렬 (Heap Sort)

• 힙 자료구조 형태의 정렬방식
• 기존 배열을 최대 힙으로 구조변경후 정렬진행
• 시간 복잡도: $O(nlogn)$

public static void heapSort(int[] arr){
	for (int i =arr.length/2 -1; i >= 0; i--){
    heapify(arr, i ,arr.length);
	}
}

public static void heapify(int[] arr, int parentIdx, int size){
	int leftIdx = 2 * parentIdx + 1;
    int rightIdx = 2 * parentIdx + 2;
    int maxIdx = parentIdx;
    if (leftIdx < size && arr[maxIdx] < arr[leftIdx]){
    	maxIdx = leftIdx;
	}
    if (rightIdx < size && arr[maxIdx] < arr[rightIdx]){
    	maxIdx = rightIdx;
	}
    if (parentIdx != maxIdx){
    	swap(arr, maxIdx, parentIdx);
        heapify(arr, maxIdx, size);
	}
}

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

public static void main(String[] args){
	int[] arr = {3,5,2,7,1,4,6};
    heapSort(arr);
    System.out.println(Arrays.toString(arr));
}

퀵 정렬 (Quick Sort)

• 임의의 기준 값(pivot)을 정하고 그 값을 기준으로 좌우로 분할하면 정렬하는 방식
• 자주 쓰이는 정렬방식이다.
• 시간 복잡도: $O(n^2)$
  

public static void quickSort(int[] arr, int left, int right){
	if(left >= right){
    	return;
	}
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot -1);
    quickSort(arr, pivot+1, right);
}

public static int partition(int[] arr, int left, int right){
	int pivot = arr[left];
    int i = left;
    int j = right;
    while(i < j){
    	while(arr[j] > pivot && i<j){
        	j--;
		}
        while(arr[i] <= pivot && i<j){
        	i++;
		}
        swap(arr, i, j);
    }
    swap(arr, left, i);
    return i;
}

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

public static void main(String[] args){
	int[] arr = {3,5,2,7,1,4,6};
    quickSort(arr, 0, arr.length -1);
    System.out.println(Arrays.toString(arr));
}

트리 정렬 (Tree Sort)

• 이진 탐색 트리(BST) 를 만들어 정렬하는 방식
• 시간 복잡도: $O(nlogn)$