[알고리즘] 정렬

버블 정렬

• 두 인접한 데이터를 비교해서 앞의 데이터가 뒤의 데이터보다 크면 자리를 바꿈.

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

시간 복잡도 : O(n^2), 완전정렬상태 : O(n)

---

선택 정렬

• 주어진 데이터 중에서 최소값을 찾은 후 해당 데이터를 맨 앞의 데이터와 교체. 그렇게 마지막 데이터까지 해당 방법을 반복하여 정렬

public static ArrayList<Integer> selectionSort(ArrayList<Integer> dataList) {
    int lowest; // 가장 작은 값의 인덱스
    for (int i = 0; i < dataList.size() - 1; i++) {
        lowest = i;
        for (int j = i + 1; j < dataList.size(); j++) {
            if (dataList.get(j) < dataList.get(lowest)) {
                lowest = j;
            }
        }
        Collections.swap(dataList, i, lowest);
    }
    return dataList;
}

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

---

삽입 정렬

• 두 번째 인덱스(key)부터 시작하여 해당 인텍스 앞에 있는 데이터들과 비교해서 key 값이 더 작으면 앞의 데이터와 순서를 바꾼다. 이를 key보다 더 작은 데이터를 만날 때 까지 반복하고 만났다면 그 다음 인덱스로 넘어가서 끝까지 반복하여 정렬

public static ArrayList<Integer> insertionSort(ArrayList<Integer> dataList) {
    for (int i = 0; i < dataList.size() - 1; i++) {
        for (int j = i + 1; j > 0; j--) {
            if (dataList.get(j) > dataList.get(j - 1)) {
                break;
            }
            Collections.swap(dataList, j, j - 1);
        }
    }
    return dataList;
}

시간 복잡도 : O(n^2), 완전정렬상태 : O(n)

---

병합 정렬

분할 정복 알고리즘 중 하나로 재귀용법을 이용한다.

1. 정렬하려는 리스트를 절반으로 자른다. 이 때 리스트의 크기가 1이라면 이미 정렬된 것으로 한다. (분할 단계)
2. 각 부분의 리스트를 재귀적으로 합병 정렬을 이용해 부분 정렬한다. (정복 단계)
3. 정렬되고 나누어진 리스트를 하나의 정렬된 리스트로 병합하여 반환하는 것을 반복. (결합 단계)

public static ArrayList<Integer> mergeSplit(ArrayList<Integer> dataList) {
		if (dataList.size() <= 1) {
        return dataList;
    }
    int mid = dataList.size() / 2;
    ArrayList<Integer> leftList = mergeSplit(new ArrayList<>(dataList.subList(0, mid))); // 0 ~ mid - 1
    ArrayList<Integer> rightList = mergeSplit(new ArrayList<>(dataList.subList(mid, dataList.size()))); // mid ~ dataList.size() - 1
    return merge(leftList, rightList);
}

public static ArrayList<Integer> merge(ArrayList<Integer> leftList, ArrayList<Integer> rightList) {
    ArrayList<Integer> mergeList = new ArrayList<>();
    int leftIndex = 0;
    int rightIndex = 0;

    // 왼쪽 리스트와 오른쪽 리스트의 데이터가 아직 정렬되지 않고 남아있는 경우
    while (leftList.size() > leftIndex && rightList.size() > rightIndex) {
		    if (leftList.get(leftIndex) > rightList.get(rightIndex)) {
            mergeList.add(rightList.get(rightIndex));
            rightIndex++;
        } else {
            mergeList.add(leftList.get(leftIndex));
            leftIndex++;
        }
    }

    // 오른쪽 리스트의 데이터가 모두 정렬된 경우. 즉 왼쪽 리스트만 남아있는 경우
    while (leftList.size() > leftIndex) {
        mergeList.add(leftList.get(leftIndex));
        leftIndex++;
    }

    // 왼쪽 리스트가 모두 정렬된 경우. 즉 오른쪽 리스트만 남아있는 경우
    while (rightList.size() > rightIndex) {
        mergeList.add(rightList.get(rightIndex));
        rightIndex++;
    }
    return mergeList;
}

시간 복잡도 : O(nlogn)

---

퀵 정렬

퀵 정렬 역시 분할 정복 알고리즘 중 하나이다.

• 기준점(피벗)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성
• 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
• 함수는 왼쪽, 피벗, 오른쪽을 병합하여 반환

public static ArrayList<Integer> quickSort(ArrayList<Integer> dataList) {
		if (dataList.size() <= 1) {
        return dataList;
    }
    int pivot = dataList.getFirst(); // 맨 처음을 피벗으로 지정
    ArrayList<Integer> leftList = new ArrayList<>();
    ArrayList<Integer> rightList = new ArrayList<>();

    for (int i = 1; i < dataList.size(); i++) {
        if (dataList.get(i) > pivot) {
            rightList.add(dataList.get(i));
        } else {
			      leftList.add(dataList.get(i));
        }
    }

    ArrayList<Integer> mergeList = new ArrayList<>();
    mergeList.addAll(quickSort(leftList));
    mergeList.addAll(Arrays.asList(pivot));
    mergeList.addAll(quickSort(rightList));
    return mergeList;
}

시간 복잡도 : O(nlogn)

피벗이 가장 크거나, 가장 작으면 모든 데이터를 비교하는 상황이 나오므로 최악의 경우

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