정렬(Sorting) 이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
이책에서는 다양한 정렬 알고리즘 중에서 선택, 삽입, 퀵, 계수 정렬을 소개했다.

1. 선택정렬

선택정렬은 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 방법이다.
선택이라는 뜻은 '가장 작은 것을 선택한다' 는 의미인 것이다.

구현코드:

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 = 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] + " ");
        }
    }

}

선택정렬의 시간 복잡도는 간단하게 O(N^2) 라고 볼 수 있다. 즉 ,값이 커진다면 효율적이지 못한다는 뜻이다. 하지만 특정한 리스트에서 가장 작은 데이터를 찾은 일이 코딩테스트 에서 잦으므로 코드에 익숙해질 필요는 있다.

2. 삽입정렬

삽입정렬은 선택정렬 처럼동작원리를 직관적으로 이해하기 쉬운 알고리즘이다. 선택정렬 보단 효율성이 높다.
선택정렬은 말 그대로 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입정렬이라고 부른다.
삽입정렬은 두 번째 데이터부터 시작한다. 첫 번째 데이터는 이미 정렬되어있다고 판단하기 때문이다.

구현코드:

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++) {
        	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)의 시간복잡도를 가진다.
퀵알고리즘과 비교해도 만약 정렬이 거의 되어있는 상황에서는 퀵정렬 알고리즘보다 더 강력하다.

3. 퀵 정렬 알고리즘

퀵 정렬은 가장많이 사용되는 알고리즘 중 하나이다.
퀵 알고리즘의 순서
1. 기준을 설정한다.(피빗PIVOT)
2. 큰 수와 작은 수를 교환한다.
3. 리스트를 반으로 나누는 방식으로 동작한다.

첫번째 리스트를 피벗으로 설정한다.
피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗버타 작은 데이터를 찾는다.
그다름 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
계속 교환한 후 큰 데이터와 작은 데이터값 의 위치가 서로 엇갈리게 되었을 때 분할(파티션)을 한다.
분할 후 정렬이 끝나는 조건은 현재 리스트의 개수가 1개일 경우이다.

import java.util.*;

public class Main {

    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return; // 원소가 1개인 경우 종료
        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);

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

}