📕 기준에 따라 데이터를 정렬

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능하다.

• 내림차순 정렬은 오름차순의 반대로 하면 된다.

📜 선택정렬

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하면, 전체 데이터의 정렬이 이루어진다.

• N개의 데이터를 정렬하고 마지막 N - 1번째 데이터는 어차피 정렬이 되어있다.
  • 따라서 가장 작은 데이터를 앞으로 보내는 과정을 N - 1번 반복하면 정렬이 되어있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
    	int n = 3;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        
        for (int i = 0; i < n; i++) {
        	int min_index = i; // 가장 작은 원소의 인덱스
            for (int j = i + 1; j < n; < j++) {
            	if (arr[min_index] > arr[j]) min_index = j;
            }
        }
        
        // 스와프
        int temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
    
    for (int i = 0; i < n; i ++) System.out.print(arr[i] + " ");
}

🔔 스와프

import java.util.*;

public class Main {

    public static void main(String[] args) {

        int[] arr = {3, 5};

        // 스와프(Swap)
        int temp = arr[0];
        arr[0] = arr[1];
        arr[1] = temp;

        System.out.println(arr[0] + " " + arr[1]);
    }

}

🔔 선택 정렬의 시간 복잡도

선택 정렬은 앞에서부터 한 요소를 가지고 반복적으로 쭉 탐색을 하기 때문에 O(N^2)이다

• 문제 풀이에는 느린 편이다.

📜 삽입정렬

삽입정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 그리고 데이터를 적절한 위치에 삽입한다.

• 가장 앞의 데이터(첫번째)는 정렬되어있다고 가정한다.
• 그 다음의 데이터(두번째)를 정렬되어 있는 데이터의 뒤에서부터 앞으로 이동하면서 비교하며 적절한 위치에 삽입한다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
    	int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        
        for (int i = 1; i < n; i++) {
        	// 인덱스 i부터 1까지 감소하며 반복하는 문법
            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;
        }
    }
    for(int i = 0; i < n; i++) System.out.print(arr[i] + " ");
}

🔔 삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)입니다.

• 꼭 기억할 내용은 삽입정렬은 데이터가 거의 정렬이 되어있으면 매우 빠르게 동작합니다.
  • 그래서 최선의 경우 O(N)을 가집니다.
• 따라서 보통은 퀵정렬보다 비효율적이지만, 정렬이 되어있는 경우 삽입정렬이 더욱 빠릅니다.
  • 2번째 역으로 진행하는 for문을 할 필요가 없습니다.

📜 퀵정렬

가장 많이 사용되는 알고리즘입니다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 교환하고 리스트를 반으로 나누는 방식으로 동작합니다.

• 따라서 Pivot, 기준이 필요합니다.(이코테에서는 첫 번째 데이터를 피벗으로 설정합니다.)
• 두 값이 서로 엇갈리게 되는 과정에서는 2개의 값 중 '작은 값'과 Pivot을 변경합니다.
  • 따라서 Pivot을 기준으로 왼쪽에는 Pivot보다 작은값, 오른쪽에는 Pivot보다 큰 값이 존재합니다.

import java.util.*;

public class Main {
	// 다음과 같은 인자들이 필요합니다.
    public static void quickSort(int[] arr, int start, int end) {
    	if (start >= end) return; // 재귀함수의 종료 조건=원소가 1개인 경우(start, end 같을 때)
        int pivot = start;// 피벗은 첫 번째 원소
        int left = start + 1;
        int right = end;
        while (left <= right) { // 오른쪽이 크거나 같은 경우는 계속 진행
        	// 피벗보다 큰 데이터를 찾을 때까지 반복(선형탐색)
            while (left <= end && arr[left] <= arr[pivot]) left++;
            // 피벗보다 작은 데이터를 찾을 때까지 반복(선형탐색)
            while (right > start && arr[right] > arr[pivot]) right--;
            
            // 엇갈렸다면 작은 데이터와 피벗을 교체
            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); // 오른쪽
    }
    public static void main(String[] args) {
        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        quickSort(arr, 0, n - 1); // 첫번째 원소는 pivot이기 때문에 n - 1

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    

}

🔔 퀵정렬 재귀호출

퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해집니다.

• Pivot을 기준으로 왼쪽 리스트와 오른쪽 리스트가 만들어지기 때문에, left리스트와 right리스트를 따로 퀵정렬을 합니다.
  • 즉, Pivot을 기준으로 왼쪽, 오른쪽 재귀호출을 계속해서 합니다.

🔔 퀵정렬 재귀호출의 종료조건

현재 리스트의 데이터 개수가 1개일 경우, 분할이 불가능함으로 재귀호출이 종료되야 합니다.

🔔 퀵정렬 시간복잡도

평균은 Nlog(N), 최악(이미 정렬이 되어 있는 경우) O(N^2) 이 경우는 삽입 정렬을 사용하자

📜 계수정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘입니다. 데이터 N개 중 최댓값이 K일 때 최악의 경우에도 O(N + K)를 보장합니다.

• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능합니다.
  • 데이터의 값이 무한한 범위를 가질 수 있는 실수형일 경우 사용이 불가합니다.
  • 데이터의 큰 값과 작은 값의 차이가 1,000,000을 넘지 않을 때 효과적을 사용할 수 있습니다.
  • 따라서 1,000,000 데이터가 있으면 1,000,001 크기의 배열을 선언해야합니다.
    • 1을 더하는 이유는 0도 포함하기 때문입니다.

import java.util.*;

public class Main {
	
    public static final int MAX_VALUE = 9; // 배열을 위한 고정값 세팅

    public static void main(String[] args) {
    	int n = 15;
        // 모든 원소의 값이 0보다 크거나 같다고 가정
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
        // 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
        int[] count = new int[MAX_VALUE + 1];
        
        for (int i = 0; i < n; i++) count[arr[i]] += 1;
        for (int i = 0; i <= MAX_VALUE; i++) {
        	 // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
        	for (int j = 0; j < count[i]; j++) System.out.print(i + " ");
        }
    }

}

🔔 계수정렬 특징

가장 작은 데이터와 큰 데이터의 범위를 모두 감길 수 있도록 하나의 리스트를 만들고, 데이터를 하나씩 확인하면서 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 됩니다.

• 따라서 해당 배열은 정렬된 형태입니다.
• 배열을 선언하면 0으로 초기화를 해야합니다.

🔔 계수정렬이 제한이 있는 이유

모든 데이터의 범위를 담아야하는 리스트를 선언해야 하기 때문입니다.

🔔 계수정렬 시간복잡도

데이터 N개, 데이터 중 최댓값 K면 O(N +K)가 됩니다.

• 현존하는 알고리즘 중에서 가장 빠릅니다.
• 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있습니다.

🔔 계수정렬 공간복잡도

계수정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.
단점은 만약 데이터가 0, 9999 단 2개일 경우를 생각해보자. 10000개의 배열을 만들어야 한다. 비효율적이다.

• 계수정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하다.

📜 자바 정렬 라이브러리 기본 예제

import java.util.*;

public class Main {

    public static void main(String[] args) {
    	
        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        Arrays.sort(arr);

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

📜 자바 정렬 라이브러리 키(Key) 기준 정렬 예제

import java.util.*;

class Fruit implements Comparable<Fruit> {
	private String name;
   	private int score;
    
    public Fruit(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String getName() {
        return this.name;
    }

    public int getScore() {
        return this.score;
    }
    
    // 정렬 기준은 '점수가 낮은 순서'
    @Override
    public int compareTo(Fruit other) {
    	if (this.score < other.score) return -1; // 역순으로 정렬
        return 1;
    }
}

public class Main {

    public static void main(String[] args) {
        List<Fruit> fruits = new ArrayList<>();
        
        fruits.add(new Fruit("바나나", 2));
        fruits.add(new Fruit("사과", 5));
        fruits.add(new Fruit("당근", 3));

        Collections.sort(fruits);
        
        for (int i = 0; i < fruits.size(); i++) {
            System.out.print("(" + fruits.get(i).getName() + "," + fruits.get(i).getScore() + ") ");
        }
    }
}

참조

https://velog.io/@dongchyeon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
.
https://devjin-blog.com/sort-algorithm-3/
.
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
.
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=k_blomkv&logNo=221137056088