[기초 알고리즘] Sort

1. Selection Sort

 

• 리스트에서 가장 작은 원소를 반복적으로 선택하여, 정렬되지 않은 부분의 맨 앞 원소와 교환하는 방식의 알고리즘

 

과정

1. 주어진 리스트 중, 최소값을 찾음
2. pass: 최소값을 맨 앞에 위치한 값과 교체 ➡️ 첫번째 위치가 정렬됨
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 반복

 

코드

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-1번)
• in-place (추가 메모리 사용 ❌)

 

단점

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

 

2. Bubble Sort

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

 

 

과정

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

 

코드

public int[] sort(int[] arr) {
    for (int i = arr.length-1; i > 0; i--) {
    	boolean swapped = false;
        
        for (int j = 0; j < 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)

 

장점

• 빠른 성능 (부분적으로 정렬될 경우에 해당함)
• 안정 정렬 (동일한 값을 가진 요소들이 정렬 후에도 상대적인 순서를 유지)
• in-place (추가 메모리 사용 ❌)

 

단점

• 스왑 횟수 많음 (한 패스에서 인접 쌍을 끝까지 훑으면서 최대 n번 스왑)

 

3. Insert Sort

• 현재 원소를 이미 정렬된 부분 배열 안에서 올바른 위치를 찾아 삽입
• ✅ 앞에서부터 차례대로 확인함

 

과정

1. 두번째 요소부터 차례대로 앞 부분과 비교
2. 자신보다 큰 요소이면 right shift
3. 마지막으로 밀린 자리에 현재 원소 삽입

코드

public sort(int[] arr) {
    int n = arr.length;

    for (int i = 1; i < n; 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)

 

장점

• 빠른 성능 (부분적으로 정렬될 경우에 해당함)
• 온라인 알고리즘 (앞부분을 정렬해 나가면서 삽입 ➡️ 매 단계가 끝날때마다 앞부분은 항상 정렬 상태를 유지함)
• 안정 정렬
• in-place

 

단점

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

 

4. Merge Sort

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

 

과정

1. 분할: 입력 배열을 두 개의 같은 크기의 하위 배열로 분할 (배열의 크기가 1이면 정렬된 것으로 간주)
2. 정복: 두 개의 하위 배열을 병합 정렬을 사용하여 정렬 (재귀함수)
3. 결합: 두 개의 정렬된 하위 배열을 합쳐서 하나의 정렬된 배열로 만듬

 

코드

public void 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);
}

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) {
    	merged[k++] = arr[i] <= arr[j] ? arr[i++] : 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)

 

장점

• 빠른 성능: O(n log n)
• 안정 정렬

 

5. Quick Sort

• 피벗을 사용한 분할정복 기반 정렬 알고리즘

 

과정

1. 피벗 선택
2. partition (피벗 보다 작은 값을 피벗 앞으로 둠)
3. 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)
• in-place

 

단점

• 안정 정렬 ❌

 

 

 

출처

• visualgo