[기초 알고리즘] Sort

1. 정렬이란?

• 주어진 데이터를 기준에 따라 순서대로 배열하는 알고리즘 입니다.
• 알고리즘과 자료구조의 기초입니다.
  • 자료구조를 최적화할 수 있습니다.
• 데이터를 보다 빠르게 찾을 수 있습니다.
• 코드를 간결하게 만들어줍니다.

 

2. 선택 정렬

• 배열에서 가장 작은 값을 선택하여 맨 앞자리 원소와 자리를 교환합니다.
• 맨 앞자리로 옮겨진 원소는 정렬이 끝날때까지 그 자리를 지킵니다.
• 첫번째 원소를 제외한 나머지 원소들을 대상으로 교환을 반복합니다.

public int[] sort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIdx = i;
        for (int j = i+1; j < arr.length; j++) {
            if (arr[minIdx] > arr[j]) minIdx = j;
        }

        if (minIdx != i) swap(arr, i, minIdx);
    }

    return arr;
}

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Time Complexity : O(n^2)

 

3. 버블 정렬

• 왼쪽부터 한 칸씩 이동하면서 이웃한 두 수를 비교해서 큰 수를 선택하여 뒤로 보냅니다.
• 한번 반복할 때마다 제일 큰 수가 맨 뒤에 위치합니다.
• 반복할 때마다 마지막 원소를 제외한 나머지 원소들을 대상으로 교환을 반복합니다.

public int[] sort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        boolean swapped = false;
        for (int j = 0; j < arr.length-i-1; j++) {
            int pre = j;
            int post = j+1;
            if (arr[pre] > arr[post]) {
                swap(arr, pre, post);
                swapped = true;
            }
        }

        if (!swapped) break;
    }

    return arr;
}

private void swap(int[] arr, int pre, int post) {
    int tmp = arr[pre];
    arr[pre] = arr[post];
    arr[post] = tmp;
}

Time Complexity : O(n^2)

(선택정렬보다 5배 정도 느립니다)

 

 

4. 삽입 정렬

• 새로운 배열에 최소값부터 하나씩 원소를 삽입하여 정렬 배열을 만들어가는 알고리즘 입니다.

public sort(int[] arr) {
	for (int i = 1; i < arr.length; i++) {
    	int key = arr[i];
        int j = i-1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
    
    return arr;
}

Time Complexity : O(n^2)

 

5. 병합 정렬

• 분할정복과 재귀 알고리즘을 사용한 정렬 방법입니다.

 

분할

• 입력 배열을 두 개의 같은 크기의 하위 배열로 분할합니다.
• 만약 배열의 크기가 1이면 이미 정렬된 것으로 간주합니다.

 

정복

• 두 개의 하위 배열을 재귀적으로 병합 정렬을 사용하여 정렬합니다.

 

결합

• 두 개의 정렬된 하위 배열을 합쳐서 하나의 정렬된 배열로 만듭니다.

 

public int[] sort(int[] arr, int l, int r) {
    if (l < r) {
    	int m = (l+r)/2;
        sort(arr, l, m-1);
        sort(arr, m, r);
        
        merge(arr, l, m, r);
    }
    
    return arr;
}

private void merge(int[] arr, int l, int m, int r) {
	int[] merged = new int[r-l+1];
    int i = l, j = m+1, k = 0;
    
    while (i <= m && j <= r) {
    	if (arr[i] < arr[j]) merged[k++]=arr[i++];
        else merged[k++]=arr[j++];
    }
    
    while (i <= m) {
    	merged[k++]=arr[i++];
    }
    
    while (j <= r) {
    	merged[k++]=arr[j++];
    }
    
    System.arrayCopy(merged, 0, arr, l, merged.length);
}

Time Complexity : O(nlogn)

 

 

출처

• visualgo