💡알고리즘은 입력, 출력, 유한성, 명백성, 효과성을 만족해야 한다.

정렬(Sort)은 알고리즘의 효율성 차이를 극명하게 느낄 수 있다.
아래 배열을 1부터 10까지 오름차순으로 정렬하는 문제를 예제로 다음 정렬들을 살펴보자!

int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

선택 정렬(Selection Sort)

선택 정렬은 첫 번째 값을 두 번째 값부터 마지막 값까지 차례대로 비교하고 가장 작은 값과 첫 번째 값을 바꾼다. 두 번째 값을 세 번째 값부터 마지막 값까지 비교하여 바꾸고 이 과정을 마지막까지 반복하여 정렬하는 알고리즘이다. 

이 알고리즘은 $N * (N+1) / 2$ 즉, $N^2$만큼 계산을 실행해야 한다. 따라서 시간 복잡도는 $O(N^2)$이다. 데이터의 개수가 커질수록 비효율적인 알고리즘이다.

public static void main(String[] args){
	int min, index, tmp;
    int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    
    for(int i=0; i<10; i++){
    	min = 9999;
        for(int j=i; j<10; j++){ //i번째 값부터 마지막 값까지 비교
        	if(min > arr[j]) {
            	min = arr[j];
                index = j;
            }
        }
        tmp = arr[i]; 
        arr[i] = arr[index]; //가장 작은 수 찾았으면 앞으로 보내기
        arr[index] = tmp;
    }
}

버블 정렬(Bubble Sort)

옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 알고리즘이다. 

선택 정렬과 개념이 유사하다. 시간복잡도도 선택 정렬과 마찬가지로 $O(N^2)$이다. 실제로 수행을 해보면 선택 정렬보다 느리다. 선택 정렬은 비교하는 연산을 $N^2$만큼 하고, 그 값을 바꾸는 연산은 $N$번 이내로 한다. 하지만 버블 정렬은 $N^2$만큼 두 값을 바꾸는 연산을 해야 하고, 두 값을 바꾸는 연산은 3번의 작업이 필요하기 때문에 선택 정렬보다 더 느리게 작동한다.

public static void main(String[] args){
	int tmp;
    int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    
    for(int i=9; i>=0; i--){ //뒤에서 부터 시작하여 가장 작은 값을 맨 앞으로 보냄
        for(int j=9; j>9-i; j--){ 
        	if(arr[j-1] > arr[j]) { //인접한 두 수만 비교하여 작은 값 앞으로 보냄
            	tmp = arr[j]; 
        		arr[j] = arr[j-1];
        		arr[j-1] = tmp;
            }
        }
    }
}

삽입 정렬(Insertion Sort)

각 값을 적절한 위치에 삽입하는 방법이다. 다른 정렬 알고리즘은 무조건 위치를 바꾸는 방식이었다면, 삽입 정렬은 필요할 때만 위치를 바꾼다. 마찬가지로 $O(N^2)$의 시간복잡도를 가지므로 또 다른 알고리즘에 비해 비효율적이다.

하지만 위의 두 알고리즘보다 연산 횟수가 적고, 이미 거의 정렬된 상태라면 어떤 알고리즘보다도 빠를 수 있다.

public static void main(String[] args){
	int tmp;
    int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    
    for(int i=1; i<10; i++){ 
        int j=i;
        whlie(j>0 && arr[j] < arr[j-1]) {
        	tmp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = tmp;
            j--;
        }
    }
}

퀵 절렬(Quick Sort)

퀵 정렬은 분할 정복 알고리즘으로 특정한 배열이 있을 때 배열의 원소를 분할하여 계산하기 때문에 빠른 알고리즘이다.
때문에 시간복잡도는 $O(N*log_{2}{N})$이다.

특정한 값을 기준(피벗)으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 둘로 나눈다.

1. 배열의 가장 첫 번째 값을 키(피벗) 값으로 잡는다.

2. 키 보다 큰 숫자를 왼쪽부터 찾고, 작은 숫자를 오른쪽부터 찾는다.

3. 값을 바꾼다.

   • 작은 값의 인덱스가 큰 값의 인덱스보다 크다면 즉, 엇갈리지 않았다면 작은 값과 큰 값의 위치를 바꾼다. 다시 2,3번을 반복한다.
   • 작은 값의 인덱스가 큰 값의 인덱스보다 작아졌다면 즉, 엇갈렸다면 키값과 작은 값의 위치를 바꾼다. 키 값은 정렬이 완료되었으므로 다음으로 넘어간다. 이때 작은 값을 찾지 못해서 키값까지 도달했다면 자기 자신과 바뀐다. 

4. 키가 정렬되었다면 키를 기준으로 앞의 배열과 뒤의 배열로 나누고, 각 배열을 1번부터 반복한다.

5. 모든 값이 키가 한 번씩 되어 위치가 정해졌다면 정렬이 완료된다.
   
   

퀵 정렬 알고리즘은 기본적으로 N번 탐색하되, 반으로 쪼개면서 반복한다는 점에서 $logN$을 곱한 복잡도를 가진다.
하지만, 최악의 경우로 거의 모든 정렬이 이미 되어있으면 시간복잡도가 $O(N^2)$가 될 수 있다.

static void quickSort(int[] arr, int start, int end){
	if(start >= end) //배열의 크기가 0이하이면 넘어감
    	return;
    
    int key = start;
    int i = start+1; //큰 값 찾는 인덱스
    int j = end; //작은 값 찾는 인덱스
    int tmp;
    
    while( i < j ){
    	while( i<=end && arr[i] < key ){
        	i++;
        }
        while( j>=start && arr[j] > key ){
        	j--;
        }
        if( i < j ){ //엇갈리지 않았다면 큰 값(i)과 작은 값(j)교체 후 다시 반복
        	tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        } else { //엇갈렸다면 키값과 작은 값(j)을 교체
        	tmp = arr[j];
            arr[j] = arr[key];
            arr[key] = tmp;
        }
    }
    
    quickSort(arr, start, j-1); //현재 키 값은 j인덱스에 있음
    quickSort(arr, j+1; end);
}



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

참고 및 출처

• https://www.youtube.com/watch?v=O-O-90zX-U4&list=PLRx0vPvlEmdDHxCvAQS1\_6XV4deOwfVrz&index=5
• https://blog.naver.com/ndb796/221226813382