[알고리즘] 정렬 알고리즘

정렬 알고리즘

• 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것

Selection Sort (선택 정렬)

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
• O(N^2)
  

public class SelectionSort{
    public static void main(String[] args)  {
        int[] arr = {3, 5, 4, 6, 2, 1};
        for (int i=0; i<arr.length; i++) {
            int minIdx = i;
            for (int j=i+1; j<arr.length;j++) {
                if (arr[minIdx] > arr[j])
                    minIdx = j;
            }
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

Insertion Sort (삽입 정렬)

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
• 선택 정렬에 비해 더 효율적으로 동작
• O(N^2)
• 최선의 경우 O(N) : 리스트가 정렬되어 있는 상태라면 빠르게 동작
  

public class InsertionSort{
    public static void main(String[] args)  {
        int[] arr = {3, 5, 4, 6, 2, 1};
        for (int i=1; i<arr.length; i++) {
            for (int j=i; j>0; j--) {
                if (arr[j] < arr[j-1]) {
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                } else
                    break;
            }
        }
    }
}

Quick Sort

• 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 일반적으로 가장 많이 사용되는 정렬 알고리즘
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
• O(NlogN)
  

public class QuickSort{
    public static void main(String[] args) {
        int[] arr = {3, 5, 4, 6, 2, 1};
        quicksort(arr, 0, arr.length-1);
    }

    public static void quicksort(int[] arr, int start, int end) {
        if (start >= end)
            return;
        int pivot = start;
        int left = start+1;
        int right = end;
        while (left <= right) {
            while (left <= end && arr[left] <= arr[pivot]) {
                left += 1;
            }
            while (right > start && arr[right] >= arr[pivot]) {
                right -= 1;
            }
            if (left > right) {
                int temp = arr[pivot];
                arr[pivot] = arr[right];
                arr[right] = temp;
            } else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
            quicksort(arr, start, right-1);
            quicksort(arr, right+1, end);
        }
    }
}

Countung Sort (계수 정렬)

• 특정한 조건이 부합할 때만 사용 가능하지만 매우 빠르게 동작하는 정렬 알고리즘
• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
• 데이터의 개수가 N, 데이터 중 최댓값이 K 일 때 최악의 경우에도 O(N+K)를 보장

문제 1: 두 배열의 원소 교체

• 희동이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다.
• 희동이는 최대 k 번의 바꿔치기 연산을 수행할 수 있는데,
  바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다.
• 희동이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것
• N, K 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 k 번의 바꿔치기 연산을 수행하여 만들 수 있는
  배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.
  [입력]
  5 3
  1 2 5 4 3
  5 5 6 6 5
  [출력]
  26

해답

cf. Java 정렬 Tip

기본 배열 오름차순 정렬

import java.util.Arrays;

public class Sort{
    public static void main(String[] args)  {
        int[] arr = {7, 5 ,9, 3, 2, 1};
        Arrays.sort(arr);
    }
}

기본 배열 내림차순 정렬

import java.util.Arrays;

public class Sort{
    public static void main(String[] args)  {
        Integer[] arr = {7, 5 ,9, 3, 2, 1};
        Arrays.sort(arr,Collections.reverseOrder());
    }
}

ArrayList 오름차순 정렬

Collections.sort(arrayList);

ArrayList 내림차순 정렬

Collections.reverse(arrayList);

문자열 길이에 따라 정렬

Arrays.sort(arr, new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
});

List<String> sortedList = new ArrayList<>(importand_document_entities);
Comparator<String> c = new Comparator<String>() {
    public int compare(String s1, String s2) {
        return Integer.compare(s2.length(), s1.length());
    }
};
Collections.sort(sortedList, c);

자료 출처 :
이것이 취업을 위한 코딩테스트다, 나동빈
https://gmlwjd9405.github.io