[Backend 개발자 면접 준비] 정렬 알고리즘 (버블, 선택)

𝟙. Bubble Sort (버블 정렬, 거품 정렬)

버블 정렬은 정렬하면 쉽게 생각 할수 있는 정렬 알고리즘이다. 버블 정렬은 두 개의 인접한 원소를 비교하여 정렬하는 방식이다.

버블 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 

 

시간 복잡도는 O(N^2) 이다.

 

버블 정렬 진행 과정

초기배열이 위와 같이 주어졌을 때, 모든 원소들이 위와 같은 과정으로 비교 과정이 진행 되며, 숫자가 클때는 두 숫자가 스왑이 된다. 결국 맨 뒤에 가장 큰 숫자가 오게 된다.

 

두번째도 같은 방식으로 반복되어 뒤에서 두번째 위치에 2번째로 큰 숫자가 자리하게 된다.

 

위와 같은 예제에서는 두번만에 정렬이 완료 되었지만, 버블정렬에서는 정렬이 끝나지 않고 3번 더 반복한 뒤에 정렬이 종료 된다.

 

버블 정렬 코드

public static void BubbleSort() {
    int[] nums = {5, 3, 1, 2, 4}

    // 한 번의 반복이 완료될 때 마다 가장 큰 수는 배열의 가장 마지막 부분으로 밀리는 것이 보장된다.
    for(int i = nums.length - 1; i > 0; i--) {
        // 따라서, 한 번의 반복마다 가장 뒤의 인덱스는 비교하지 않도록 반복문을 설계할 수 있다.
        for(int j = 0; j < i; j++) {
            // 만일, 앞의 수가 뒤의 수보다 더 크다면 swap 연산을 진행해준다.
            if(nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

 

𝟚. 선택 정렬 (Selection Sort)

선택 정렬은 말 그대로 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다.

데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다.

 

시간 복잡도는 O(N^2) 이다.

선택 정렬 진행 과정

1. 주어진 리스트에서 최솟값을 찾는다.

2. 최솟값을 맨 앞 자리의 값과 교환한다.

3. 맨 앞 자리를 제외한 나머지 값들 중 최솟값을 찾아 위와 같은 방법으로 반복한다. 

 

선택 정렬 코드

private static void selection_sort() {
	int[] nums = {5,3,1,2,4};
    int size = nums.length;

    for(int i = 0; i < size - 1; i++) {
        int min_index = i;	

        // 최솟값을 갖고있는 인덱스 찾기 
        for(int j = i + 1; j < size; j++) {
            if(nums[j] < nums[min_index]) {
                min_index = j;
            }
        }

        // i번째 값과 찾은 최솟값을 서로 교환 
        swap(nums, min_index, i);
    }
}

private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
	nums[j] = temp;
}

 

 

 

 

 

Reference Link

https://st-lab.tistory.com/195

https://st-lab.tistory.com/168