정렬 알고리즘

정렬(Sorting)

: 데이터를 특정한 기준에 따라 순서대로 나열하는 것

정렬 알고리즘의 종류

1. 선택 정렬

: 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

import.java.util.*;

public class 선택정렬 {
	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] = tmep;
        }
        for (int i = 0; i < n; i++) {
        	System.out.println(arr[i] + " "); // {0,1,2,3,4,5,6,7,8,9}
        }
    }
}

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 함

구현 방식에 따라 사소한 오차가 있을 수 있지만 전체 연산 횟수는 다음과 같다.

 

N + (N-1) + (N-2) + ··· + 2

 

이는 (N^2 + N -2) / 2로 표현(등차수열의 합)할 수 있는데 빅오 표기법에 따라 O(N^2)이라고 작성

 

2. 삽입 정렬

: 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

import.java.util.*;

public class 삽입정렬 {
	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++) {
        // 인덱스 i부터 1씩 감소하면 반복하는 문법
        	for (int j = i; j > 0; j--) {
            	// 한 칸씩 왼쪽으로 이동
            	if (arr[j] < arr[j-1]) {
                	// 스와프
                    int tmep = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
                // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
                else break;
            }
        }
        for (int i = 0; i < n; i++) {
        	System.out.println(arr[i] + " "); // {0,1,2,3,4,5,6,7,8,9}
        }
    }
}

삽입 정렬의 시간 복잡도는 O(N^2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용

현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작

  최선의 경우(이미 모든 데이터가 정렬되어 있는 경우) O(N)의 시간복잡도를 가짐

 

3. 퀵 정렬

: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

병합정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정

 

첫 번째 데이터를 기준으로 왼쪽에서부터 첫 번째 데이터보다 큰 수를 찾고, 오른쪽에서부터 첫 번째 데이터보다 작은 수를 찾는데, 만약 그 위치가 엇갈리는 경우 '피벗', 즉 기준 데이터를 작은 데이터의 위치와 바꾸어 준다.

이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide)이라고 한다.

public class Main {
	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++;
            // 피벗보다 작은 데이터를 찾을 때까지 반복
            while (right > start && arr[right] >= arr[pivot]) right--;
            // 엇갈렸다면 작은 데이터와 피벗을 교체
            if (left > right) {
            	int tmep = 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);

 

4. 계수 정렬

: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘

     계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능

  데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장

import java.util.*;

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

 

계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N+K)

계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용 가능!