🗃️ 정렬

>> 정렬2 (합병 정렬, 퀵 정렬)

선택 정렬 Selection Sort

: 최솟값을 선택하여 앞으로 swap

→ 시간복잡도 O(n^2)

• Java

public void SelectionSort(int[] arr) {
    for(int i = 0; i < arr.length-1; i++) {
        // 우선, 첫번째 값을 최솟값으로 두기
        int idxOfMin = i;

        // 최솟값의 인덱스 찾기
        for(int j = i+1; j < arr.length; j++) {

            if(arr[j] < arr[idxOfMin]) {
                idxOfMin = j;
            }
        }

        // 최솟값을 앞으로 swap    
        int temp = arr[idxOfMin];
        arr[idxOfMin] = arr[i];
        arr[i] = temp;
    }
}

• Python

def selection_sort(num_list):
    for i in range(len(num_list)-1):
        # 우선, 첫번째 값을 최솟값으로 두기
        idx_min = i

        # 최솟값의 인덱스 찾기
        for j in range(i+1, len(num_list)):
            if num_list[j] < num_list[idx_min]:
                idx_min = j

        # 최솟값을 앞으로 swap
        num_list[idx_min], num_list[i] = num_list[i], num_list[idx_min]

 

---

버블 정렬 Bubble Sort

: 근접 값과 비교해서 큰 값을 뒤로 swap

→ 시간복잡도 O(n^2)

• Java

public void BubbleSort(int[] arr) {
	
    for(int i = arr.length - 1; i > 0; i--) {

        for(int j = 0; j < i; j++) {

            // 오른쪽 값보다 크면 swap
            if(arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

• Python

def bubble_sort(num_list):
    # 정렬범위 앞쪽으로 점점 좁아짐
    for i in range(len(num_list) - 1, 0, -1):
        # 앞에서 뒤로 비교해 나감
        for j in range(i):

            # 뒤의 값보다 크면 swap
            if num_list[j] > num_list[j + 1]:
                num_list[j], num_list[j + 1] = num_list[j + 1], num_list[j]

 

---

계수 정렬 Counting Sort

: 각 값의 갯수를 세어 위치 결정

→ 시간복잡도 O(n + k) → 최댓값 k의 크기와 시간복잡도 비례

안정 정렬 : 같은 값도 기존 순서대로 정렬됨

• Java

public int[] CountingSort(int[] arr) {
	// 최댓값 구하기
    int maxi = arr[0];
    for(int i = 0; i < arr.length; i++) {
    	if(arr[i] > maxi) {
        	maxi = arr[i];
        }
    }
    
    // 개수 세기
	int[] count = new int[max];
    for(int i = 0; i < arr.length; i++) {
        count[arr[i]]++; 
    }
    
    // 누적합(=count인덱스값이 sorted에 들어갈 위치)
    for(int j = 1; j < maxi; j++) {
    	count[j] += count[j - 1];
    }
    
    // arr 뒤에서부터 정렬
    int[] sortedArr = new int[arr.length];
    for(int i = arr.length - 1; i <= 0; i++) {
    	int idx = count[arr[i]] - 1;
        sortedArr[idx] = arr[i];
        count[arr[i]]--;
    }
    return sortedArr;
}

• Python

def counting_sort(num_list):
	size = len(num_list)
    
	# 최댓값 구하기
    maxi = num_list[0]
	for i in range(size):
    	if num_list[i] > maxi:
        	maxi = num_list[i]
    
	# 개수 세기
    count = [0] * maxi
    for i in range(size):
    	count[num_list[i]] += 1
        
    # 누적합
    for j in range(1, max):
    	count[j] += count[j - 1]
    
    # num_list 뒤에서부터 정렬
    sorted_list = [0] * size
    for i in range(size - 1, -1, -1):
    	idx = count[num_list[i]] - 1
        sorted_list[idx] = num_list[i]
        count[num_list[i]] -= 1
        
    return sorted_list