[알고리즘 / JAVA] 까먹지 않기 위한 기본 정렬 알고리즘

코딩 테스트에서 정렬 문제는 자주 나옵니다. 하지만 보통 정렬 같은 경우에는 언어에 내장된 함수를 사용합니다. 그래서 개인적으로 정렬 알고리즘을 까먹는 부분이 있어서 이번 기회에 알면 좋을 4가지 정렬 알고리즘을 간략히 정리하려고 합니다.

 

선택 정렬 (Selection Sort)

현재 위치에 들어갈 데이터를 찾아 선택하는 정렬 알고리즘입니다. (시간 복잡도 : O(N^2))

 

✏ 과정

1. 정렬할 리스트에서 최솟값을 찾는다.

2. 최솟값을 맨 앞 자리의 값과 교환 - Swap

3. 맨 앞 자리 제외한 나머지 값들 중 최솟값을 찾아 다음 자리 값과 교환

4. 이후 위의 과정을 반복

 

✒ 코드

public static void main(String[] args) {

    int[] numbers = {1,2,5,7,8,11,10};

    for(int i = 0 ; i < numbers.length  ; i++){
        int minIndex = i;
        for(int j = i+1 ; j < numbers.length ; j++ ){
            if(numbers[j] < numbers[i]){
                minIndex = j;
            }
        }
        swap(numbers, minIndex, i);
    }
}


private static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

 

삽입 정렬 (Insertion Sort)

데이터를 하나씩 확인하며 적절한 위치에 삽입하는 정렬 알고리즘입니다. (시간 복잡도 : O(N^2))

이때 이미 리스트가 거의 정렬되어 있다면 매우 비효율적인 알고리즘입니다.

 

✏ 과정

1. 타겟이 되는 데이터를 이전 위치에 있는 데이터와 비교 (첫 번째 타겟은 두 번째 데이터부터 시작)

2. 만약 이전 위치에 있던 데이터보다 작다면 위치를 서로 교환

3. 타겟에 대한 정렬이 끝나면 다시 타겟을 설정

4. 이후 위의 과정을 반복

 

✒ 코드

    public static void main(String[] args) {

        int[] numbers = {1,2,5,7,8,11,10};

        for(int i = 1 ; i < numbers.length  ; i++){
          
            int target=numbers[i];
            int compareIndex = i-1;
            
            while(compareIndex >=0 && target < numbers[compareIndex]){
                numbers[compareIndex+1] = numbers[compareIndex];
                compareIndex--;
            }
            numbers[compareIndex+1] = target;
        }
    }

 

퀵 정렬 (Quick Sort)

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬 알고리즘입니다. (시간 복잡도 : O(NlogN))

이때 이미 리스트가 거의 정렬되어 있다면 매우 비효율적인 알고리즘입니다. 여기서는 중간 값을 피벗으로 잡고 가는 방법으로 할 겁니다.

 

✏ 과정

1. 피벗을 하나 선택 (중간)
2. 피벗을 기준으로 왼쪽은 피벗보다 큰 값, 오른쪽은 피벗보다 작은 값을 찾는다.
3. 찾았다면 두 데이터를 교환 - swap
4. 왼쪽에서 찾는 위치와 오른쪽에서 찾는 위치가 엇갈리지 않을 때까지 위의 과정을 반복
5. 엇갈린 기준으로 두 개의 부분리스트로 나누어 위의 과정을 반복 (1~ 4번)
6. 모든 부분리스트가 정렬이 되고 최종적으로 합치면 완료

 

✒ 코드

public static int partition(int[] numbers,int left, int right) {
    int pivot = numbers[(left+right)/2];

    while(left<=right) {

        while(numbers[left]<pivot) left++;
        while(numbers[right]>pivot) right--;

        if(left<=right)
        {
            //swap
            int temp = numbers[left];
            numbers[left]=numbers[right];
            numbers[right]=temp;
            left++;
            right--;
        }
    }

    return left;
}

public static int[] quickSort(int[] numbers,int left, int right)
{
    int p = partition(numbers, left, right);
    if(left<p-1) quickSort(numbers,left,p-1);
    if(p<right) quickSort(numbers,p,right);

    return numbers;
}

public static void main(String[] args) {
    int[] numbers = {4,2,3,5,9};

    numbers = quickSort(numbers,0,numbers.length-1);

}

 

 

카운팅 정렬 (Counting Sort)

데이터의 값이 몇 번 나왔는지 세주는 것입니다. 정수 형태로 표현할 수 있을 때만 사용 가능합니다. 정렬 속도는 매우 빠릅니다. (시간 복잡도: O(N+K))

 

✏ 과정

1. 카운팅 배열을 만든다. (numbers = [2,4,1,0] ,counting = [1,1,1,0,1] - 수의 범위 0~4)

2. 카운팅 배열의 각 값을 누적합으로 변환 (counting = [1,2,3,3,4])

3. 카운팅 배열의 각 값은 (시작점 - 1)이다. 이를 가지고 마지막 index부터 순회하여 정렬을 한다.

 

✒ 코드

  
    public static void main(String[] args) {
        
        int[] numbers = {11, 21, 50, 17, 55, 55, 42}; 
        int[] counting = new int[61];	// 수의 범위 : 0 ~ 60
        int[] result = new int[7];	

        //카운팅 배열 만들기
        for(int i = 0; i < numbers.length; i++) {
            counting[numbers[i]]++;
        }
        
        //카운팅 배열을 누적합으로 만들기 (a[i] = a[i] + a[i-1] 으로 전개)
        for(int i = 1; i < counting.length; i++) {
            counting[i] += counting[i - 1];
        }

        //정렬하기
        for(int i = numbers.length - 1; i >= 0; i--) {
            int value = numbers[i];
            counting[value]--;
            result[counting[value]] = value;
        }
    }