TIL 2022-11-29 (화)

오랜만에 온라인 강의들은 것에 대해서 작성해보려 한다.
자료구조를 간단하게 배우고 정렬 알고리즘에 대해서 강의가 이루어졌기 때문에 그에 관해서 이번 포스트를 작성해보겠다.

먼저 오늘은 가장 간단한 정렬 알고리즘들을 적으려고 한다. 버블, 선택, 삽입 정렬이 해당되는 내용이다.

버블 정렬

인접한 데이터 두 개를 비교해서 앞에 있는 데이터가 뒤의 데이터 보다 크면 자리를 바꾸는 형식의 정렬 알고리즘이다.

코드로 구현하면 다음과 같다. ArrayList를 이용해서 데이터를 나열하고 Collections 패키지의 swap 메소드를 이용해서 자리를 바꾸는 방법을 이용할 것이다.

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

이중 반복문을 이용해서 이미 정렬한 데이터를 또다시 정렬하는 일이 없도록 했다.

---

선택 정렬

주어진 데이터 중에서 최소값을 찾은 후 그 값을 맨 앞의 데이터와 자리를 바꾼다. 나머지 데이터들은 맨 앞의 위치를 빼고 다시 동일하게 반복하는 방법이다.

import java.util.ArrayList;
import java.util.Collections;

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

버블 정렬과 동일한 방법이지만 lowest를 설정해서 최소값을 설정하도록 한다. 동일하게 이중 반복문으로 구성해서 중복 정렬을 시행하지 않도록 한다.

삽입 정렬

해당 인덱스 값의 앞에 있는 데이터부터 비교해서 값이 더 작으면 비교당한 값을 뒷 번호의 인덱스로 복사한다. 그리고 큰 값의 데이터를 만나면 만난 위치의 바로 뒤로 값을 이동시킨다.

import java.util.ArrayList;
import java.util.Collections;

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

가장 간단하다고 하는 정렬알고리즘 3개에 대해서 공부해보았다. 아직까지는 머리로는 이해가 되는데 직접 구현하라고 하면 많이 헤멜 것 같다. 조금 더 코드를 작성하는 것에 대해서 익숙해져야 할 것 같다. ArrayList를 사용하는 법이라던지 구조를 생각하면서 코드를 짜야한다고 느낀다.

영상 출처
반디캠 사용 (https://www.bandicam.co.kr/)
Sorting 사이트 (https://visualgo.net/en)