[자료구조] Sort

Quick Sort

정렬이 안되어 있는 배열이 있으면 아무거나 값을 잡고 그 값을 기준으로 작은 것은 왼쪽 큰 것을 오른쪽으로 정렬 => 계속 반복하다 보면 파티션이 2개만 남는 일이 생김.

Quick Sort 시간복잡도

평균적으로 O(nlogn)
: 파티션을 나누는 횟수가 n -> 한 번 나누면 검색해야 되는 데이터가 절반으로 줄기 때문에 logn의 시간이 걸림

최악의 경우 O(n^2)
: 선택한 기준 값이 가장 작거나 가장 큰 경우에 퀵 정렬은 최악의 경우 O(n^2)의 시간 복잡도를 가진다.

public class QuickTest{
	private static void quickSort(int[] arr){
    	quickSort(arr, 0, arr.length - 1);
    }
    private static void quickSort(int[] arr, int start, int end){
    	int part2 = partition(arr, start, end);
        if(start < part2 - 1){
        	quickSort(arr, start, part2 - 1);
        }
        if(part2 < end){
        	quickSort(arr, part2, end);
        }
    }
    private static int partition(int[] arr, int start, int end){
    	int pivot = arr[(start + end) / 2];
        while(start <= end){
        	while(arr[start] < pivot) start++;
            while(arr[end] > pivot) end--;
            if(start <= end){
            	swap(arr, start, end);
                start++;
                end--;
            }
        }
        return start;
    }
    private static void swap(int[] arr, int start, int end){
    	int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
    }
    private static void printArray(){
    	for(int data : arr){
        	System.out.print(data + ", ");
        }
        System.out.println();
    }
    public static void main(String[] args){
    	int[] arr = {3, 9, 4, 7, 5, 0, 1, 6, 8, 2};
        printArray(arr);
        quickSort(arr);
        printArray(arr);
    }
}

# 결과 값
3, 9, 4, 7, 5, 0, 1, 6, 8, 2,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Merge Sort

정렬이 되어 있는 2개의 배열을 양쪽 배열에서 양쪽 값을 비교해서 더 작은 값을 먼저 넣는다.
함수가 호출 될 때마다 절반씩 잘라서 재귀적으로 함수를 호출하고 맨 끝에 제일 작은 조각 부터 2개씩 병합해서 정렬된 배열을 Merge 해 나가는 방법이 바로 Merge Sort이다.

Merge Sort 시간복잡도

n개 만큼 씩 logn 만큼 돌기 때문에 O(nlogn)이 된다.

• Merge Sort는 별도의 저장 공간을 필요로 하기 때문에 공간을 사용할 수 없는 경우에는 퀵소트를 이용해야 한다.

# Merge Sort 구현 코드
public class MergeSortTest{
	private static void mergeSort(int[] arr){
    	int[] tmp = new int[arr.length];
        mergeSort(arr, tmp, 0, arr.length - 1);
    }
    private static void mergeSort(int[] arr, int[] tmp, int start, int end){
    	if(start < end){
        	int mid = (start + end) / 2;
            mergeSort(arr, tmp, start, mid);
            mergeSort(arr, tmp, mid + 1, end);
            merge(arr, tmp, start, mid, end);
        }
    }
    private static void merge(int[] arr, int[] tmp, int start, ind mid, int end){
    	for(int i = start; i <= end; i++){
        	tmp[i] = arr[i];
        }
        int part1 = start;
        int part2 = mid + 1;
        int index = start;
        while(part1 <= mid && part2 <= end){
        	if(tmp[part1] <= tmp[part2]){
            	arr[index] = tmp[part1];
                part1++;
            }
            else{
            	arr[index] = tmp[part2];
                part2++;
            }
            index++;
        }
        for(int i = 0; i <= mid - part1; i++){
        	arr[index + i] = tmp[part1 + i];
        }
    }
    private static void printArray(int[] arr){
    	for(int data: arr){
        	System.out.print(data + ", ");
        }
        System.out.println();
    }
    public static void main(String[] args){
    	int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        printArray(arr);
        mergeSort(arr);
        printArray(arr);
    }
}

# 결과 값
9, 8, 7, 6, 5, 4, 3, 2, 1
1, 2, 3, 4, 5, 6, 7, 8, 9

Bubble Sort

앞에서 부터 자기 옆에 있는 애랑 비교하여 작은 값을 앞으로 큰 값을 그 뒤로 바꾸면서 배열에 끝까지 반복해서 정렬을하는 방법이다.

Bubble Sort 시간복잡도

Bubble Sort는 앞에서부터 1개씩 뒤로가면서 전체방을 돌기 때문에 O(n^2)의 시간이 든다.

# Bubble Sort 구현
public class Test {
	private static void bubbleSort(int[] arr){
		bubbleSort(arr, arr.length - 1);
	}
    private static void bubbleSort(int[] arr, int last){
		if(last > 0){
			for(int i = 1; i <= last;i++){
				if(arr[i - 1] > arr[i]){
                	swap(arr, i - 1, i);
                }
			}
            bubbleSort(arr, last - 1);
		}
	}
    private static void swap(int[] arr, int source, int target){
    	int tmp = arr[source];
        arr[source] = arr[target];
        arr[target] = tmp;
    }
    private static void printArray(int[] arr){
    	for(int data : arr){
        	System.out.print(data + ", ");
        }
        System.out.println();
    }
    public static void main(String[] args){
		int[] arr = {6, 5, 4, 3, 2, 1};
        printArry(arr);
        bubbleSort(arr);
        printArray(arr);
	}
}

# 결과 값
6, 5, 4, 3, 2, 1
1, 2, 3, 4, 5, 6

Selection Sort(선택 정렬)

배열을 돌면서 가장 작은 것부터 하나씩 앞으로 차곡차곡 옮기는 것이다.

Selection Sort 시간복잡도

앞에서 부터 한 칸씩 가면서 갈 때마다 전체 방을 한번씩 돌기 때문에 O(n^2)의 시간이 든다.

public class SelectionSortTest{
	private static void selectionSort(int[] arr){
    	selectionSort(arr, 0);
    }
    private static void selectionSort(int[] arr, int start){
    	if(start < arr.length - 1){
        	int min_index = start;
            for(int i = start; i < arr.length;i++){
            	if(arr[i] < arr[min_index]) min_index = i;
            }
            swap(arr, start, min_index);
            selectionSort(arr, start + 1);
        }
    }
    private static void swap (int[] arr, int index1, int index2){
    	int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
    
    public static void main(String[] args){
    	int[] arr = {4, 5, 2, 1, 3};
        printArray(arr);
        selectionSort(arr);
        printArray(arr);
    }
}