정렬

정렬이란?

어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것

버블정렬

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

public int[] solution(int[] list) {
    for (int i = 0; i < list.length - 1; i++) {
        boolean isSwap = false;
        for (int j = i; j < list.length - 1 - i; j++) {
            if (list[j] > list[j + 1]) {
                swap(list, j, j + 1);
                isSwap = true;
            }
        }
        if (!isSwap) {
            break;
        }
    }
   return list;
}

private void swap(int[] list, int i, int i1) {
    int temp = list[i];
    list[i] = list[i + 1];
    list[i + 1] = temp;
}

시간복잡도 : O(n2)

선택정렬

다음과 같은 순서를 반복하면서 정렬하는 알고리즘
1. 주어진 데이터 중 최소값을 찾는다.
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다.
3. 맨 앞의 위치를 뺸 나머지 데이터를 동일한 방법으로 반복한다.

public int[] solution(int[] list) {
    for (int i = 0; i < list.length - 1; i++) {
        int index = i;
        for (int j = i + 1; j < list.length ; j++) {
            if (list[j] < list[index]) {
                index = j;
            }
        }
        swap(list, i, index);
    }
    return list;
}

private void swap(int[] list, int i, int index) {
    int temp = list[i];
    list[i] = list[index];
    list[index] = temp;
}

시간복잡도 : O(n2)

삽입정렬

• 삽입정렬은 두 번째 인덱스 부터 시작한다.
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면 B값을 뒤 인덱스로 복사한다.
• 이를 key 값이 더 큰 데이터를 만날 때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key값을 이동한다.

public int[] solution(int[] list) {
    for (int i = 0; i < list.length - 1; i++) {
        for (int j = i + 1; j > 0; j--) {
            if (list[j] < list[j - 1]) {
                swap(list, j, j - 1);
            } else {
                break;
            }
        }

    }
    return list;
}

시간복잡도 : O(n2)

병합 정렬

재귀용법을 활용한 정렬 알고리즘
1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

public List<Integer> mergeSplitFunc(List<Integer> list) {
    if (list.size() <= 1) {
        return list;
    }
    int mid = list.size() / 2;

    List<Integer> leftList = mergeSplitFunc(new ArrayList<>(list.subList(0, mid)));;
    List<Integer> rightList = mergeSplitFunc(new ArrayList<>(list.subList(mid, list.size())));

    return mergeFunc(leftList, rightList);
}

private List<Integer> mergeFunc(List<Integer> leftList, List<Integer> rightList) {
    List<Integer> mergeList = new ArrayList<>();
    int leftPoint = 0;
    int rightPoint = 0;

    while (leftList.size() > leftPoint && rightList.size() > rightPoint) {
        if (leftList.get(leftPoint) > rightList.get(rightPoint)) {
            mergeList.add(rightList.get(rightPoint));
            rightPoint++;
            continue;
        }
        if (leftList.get(leftPoint) < rightList.get(rightPoint)) {
            mergeList.add(leftList.get(leftPoint));
            leftPoint++;
        }
    }

    while (leftList.size() > leftPoint) {
        mergeList.add(leftList.get(leftPoint));
        leftPoint++;
    }

    while (rightList.size() > rightPoint) {
        mergeList.add(rightList.get(rightPoint));
        rightPoint++;
    }
    return mergeList;
}

시간복잡도 : O(N)

퀵정렬

정렬 알고리즘의 꽃
1. 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽 큰 데이터는 오른쪽으로 모으는 함수를 작성한다.
2. 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복한다.
3. 함수는 왼쪽 + 기준점 + 오른쪽을 리턴한다.

    public List<Integer> quickSort(List<Integer> list) {
        if (list.size() <= 1) {
            return list;
        }
        final Integer pivot = list.get(0);

        List<Integer> leftList = new ArrayList<>();
        List<Integer> rightList = new ArrayList<>();

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

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

        return mergeList;
    }

시간복잡도 : O(N)