[Algorithm] 정렬 알고리즘(버블정렬, 선택정렬, 삽입 정렬)

버블정렬(Bubble Sort)

---

버블정렬(Bubble Sort)은 인접한 두 개의 요소를 비교하면서 크기가 작은 요소를 앞으로 이동시키고 큰 요소를 뒤로 이동시키면서 정렬하는 알고리즘이다.

버블정렬의 동작 방식
1. 배열의 첫번째 요소부터 마지막 요소까지 반복하여 인접한 두 요소를 비교한다.
2. 왼 쪽 요소가 오른쪽 요소보다 크면, 두 요소의 위치를 교환한다.
3. 배열의 마지막 요소까지 이동한 후, 가장 큰 요소가 배열의 마지막에 위치하게 된다.
4. 다음 반복에서는 배열의 첫번째 요소부터 마지막에서 두번째 요소까지 인접한 두 요소를 비교하면서 정렬한다. 마지막 요소는 이미 정렬이 완료되었기 때문에 제외한다.
5. 이러한 과정을 배열의 모든 요소가 정렬될 때까지 반복한다.

1~4번 과정을 배열이 정렬될 때까지 반복하며 매 반복마다 가장 큰 요소가 배열의 끝으로 이동하게 된다.

버블정렬의 시간 복잡도는 O(n^2)으로, 입력 데이터의 크기가 커질수록 성능이 저하된다. 또한, 구현이 간단하지만, 대용량 데이터 정렬에는 비효율적인 알고리즘이므로 실제로는 잘 사용하지 않는다.
 

public class BubbleSort {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < 10; i++){
            list.add((int) (Math.random()*100));
        }
        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.sort(list);
    }

    public ArrayList<Integer> sort(ArrayList<Integer> dataList){
        for (int idx = 0; idx < dataList.size()-1; idx++){
            boolean swap = false;
            for (int idx2 = 0; idx2 < dataList.size() -1 -idx; idx2++){
                if(dataList.get(idx2) > dataList.get(idx2 + 1)){
                    Collections.swap(dataList, idx2, idx2 + 1);
                    swap = true;
                }
            }
            if (!swap)
                break;
        }
        return dataList;
    }
    
}

 

선택 정렬(Selection Sort)

---

선택 정렬(Selection Sort)은 주어진 리스트에서 최소값을 찾아 맨 앞에 위치시키는 과정을 반복하여 전체 리스트가 정렬되도록 하는 알고리즘이다.

선택 정렬의 동작방식
1. 주어진 리스트 중에서 최소값을 찾는다.
2. 최소값을 리스트의 맨 앞에 위치한 값과 교환한다.
3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.

선택정렬 알고리즘의 시간 복잡도는 O(n^2)이다. 따라서 리스트의 크기가 크면 선택 정렬은 비효율적인 알고리즘이 된다.
 

public class SelectionSort {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < 10; i++){
            list.add((int) (Math.random()*100));
        }
        SelectionSort selectionSort = new SelectionSort();
        selectionSort.sort(list);
    }

    public ArrayList<Integer> sort(ArrayList<Integer> dataList){
        int lowest;
        for (int stand = 0; stand < dataList.size() - 1; stand++){
            lowest = stand;
            for (int idx = stand + 1; idx < dataList.size(); idx++){
                if(dataList.get(lowest) > dataList.get(idx))
                    lowest = idx;
            }
            Collections.swap(dataList, lowest, stand);
        }
        return dataList;
    }

}

 

삽입 정렬(Insertion Sort)

---

삽입 정렬(Insertion Sort)은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분 배열과 비교하여, 적절한 위치에 삽입하는 방식으로 정렬을 수행한다.

삽입 정렬의 동작 방식
1. 배열의 두 번째 요소부터 시작한다.
2. 현재 요소를 이전 요소와 비교하여, 이전 요소가 더 크다면 자리를 바꾼다.
3. 이전 요소와도 비교하며 자리를 찾아간다.
4. 이전 요소들과 비교하다가, 현재 요소보다 작거나 같은 요소를 찾으면 그 요소 뒤에 현재 요소를 삽입한다.
5. 배열의 모든 요소가 정렬될 때까지 위의 과정을 반복한다.

삽입 정렬은 각 요소를 비교하고 교환하는 데 필요한 연산 횟수가 적기 때문에, 데이터의 크기가 작거나 정렬이 거의 완료된 경우에는 다른 정렬 알고리즘에 비해 빠른 속도를 보인다. 하지만 배열이 이미 정렬되어 있는 경우에도 비교 연산을 수행하기 때문에 최악의 경우 시간 복잡도는 O(n^2)이 된다.
 

public class InsertionSort {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < 10; i++){
            list.add((int) (Math.random()*100));
        }
        InsertionSort selectionSort = new InsertionSort();
        selectionSort.sort(list);
    }

    public ArrayList<Integer> sort(ArrayList<Integer> dataList){
        for (int idx = 0; idx < dataList.size() - 1; idx++){
            for (int idx2 = idx + 1; idx2 > 0; idx2--){
                if(dataList.get(idx2) < dataList.get(idx2 - 1))
                    Collections.swap(dataList, idx2, idx2 -1);
                else
                    break;
            }
        }
        return dataList;
    }

}