[기초 알고리즘] Sort

1. Selection Sort

• in-place

 

과정

• 주어진 리스트 중, 최소값을 찾음
• 최소값을 맨 앞에 위치한 값과 교체 (pass)
• 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체

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;
}

 

Time Complexity : O(n^2)

 

장점

• 교환 횟수 최소화

 

단점

• 성능: 항상 n^2의 시간 복잡도를 가짐
• 안정성 없음 (같은 값이면 순서가 계속 바뀜)

 

2. Bubble Sort

• 인접한 두 원소를 비교하여, 순서가 잘못되어 있으면 교환하는 방식의 알고리즘
• in-place

 

과정

• 이웃한 두 수 중, 큰 수를 뒤로 보냄 (swap)
• 마지막 원소를 제외한 나머지 원소들을 대상으로 반복

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

Time Complexity : O(n^2)

 

장점

• 부분적으로 정렬될 경우) 빠른 성능
• 안정 정렬 (동일한 값을 가진 요소들이 정렬 후에도 상대적인 순서를 유지)

 

단점

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

 

3. Insert Sort

• 앞에서부터 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아 삽입합니다.
• in-place

 

과정

• 두번쨰 요소부터 차례대로 앞 부분과 비교
• 자신보다 작은 요소를 만날 때까지 요소를 오른쪽으로 밀음 (right shift)
• 자신의 위치를 찾아 삽입

public sort(int[] arr) {
   for (int i = 1; i < arr.length; i++) {
    	int key = arr[i], 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)

 

장점

• 부분적으로 정렬될 경우) 빠른 성능 (선택 정렬, 버블 정렬보다 빠름)
• 안정 정렬
• 온라인 알고리즘 (새로운 요소가 추가될 때마다 동적으로 정렬 가능)

 

단점

• 성능 (데이터셋이 클 경우 비효율적)

 

4. Quick Sort

• 분할정복 알고리즘 기반 정렬
• in-place

 

과정

• 피벗 선택
• 피벗 보다 작은 값을 피벗 앞으로 둔다
• 위 과정을 재귀적으로 반복한다 (divide and conquer)

 

public void quickSort(int low, int high) {
    if (low >= high) return;
    
    int pivot = partition(low, high);
    
    quickSort(low, pivot-1);
    quickSort(pivot+1, high);
}

private int partition(int low, int high) {
    int pivot = nums[high], i = low-1;
    
    for (int j = low; j < high; j++) {
    	if (nums[j] <= pivot) swap(++i, j);
    }
    
    swap(++i, high);
    
    return i;
}

 

Time Complexity : O(n^2)

 

장점

• 빠른 성능
  • 부분적으로 정렬될 경우) 빠름
  • 평균적으로 O(n log n)

 

단점

• 안정적이지 않음

 

5. Merge Sort

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

 

과정

분할

• 입력 배열을 두 개의 같은 크기의 하위 배열로 분할 (배열의 크기가 1이면 정렬된 것으로 간주)

 

정복

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

 

결합

• 두 개의 정렬된 하위 배열을 합쳐서 하나의 정렬된 배열로 만듬

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

private void merge(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(n log n)

 

장점

• 안정 정렬
• 성능

 

 

 

출처

• visualgo