[JAVA] 배열의 정렬(Array Sort)

안녕하세요.

이번에는 배열의 정렬을 공부해보겠습니다.

 

배열에서는 저장된 값들을 순서대로 정렬할 수 있습니다.

정렬을 하는 방식으로는 오름차순(ACS)과 내림차순(DESC)이 있습니다.

정렬을 하는 방법으로는 기본적으로 선택 정렬과 버블 정렬이 있습니다.

 

먼저 선택 정렬을 이용해 배열을 오름차순으로 정렬하는 방법으로는

배열에 저장된 값들을 순차적으로 전부 비교한 뒤에 최솟값을 찾고 그 값을 첫번째 자리로 보냅니다.

다시 최소값을 제외한 값들을 순차적으로 비교하여 가장 작은 값을 찾고 두 번째 자리로 보냅니다.

이렇게 마지막 하나가 남을 때까지 계속 작은 값을 찾고 인덱스 값을 바꾸면 오름차순으로 정렬됩니다.

내림차순은 오름차순과 반대로 최솟값이 아닌 최댓값을 순차적으로 인덱스 값을 바꿔서 정렬하면 됩니다.

// 선택 정렬(오름차순)
int sArr[] = {13, 9, 4, 2, 6, 25, 10};
int min;        // 최소값의 인덱스를 저장할 변수
int temp;       // 값 교환용 임시변수
 
// 선택 정렬 알로리즘
for(int i = 0; i < (sArr.length - 1); i++)
{
    min = i;
    
    // 최소값을 찾는 알로리즘
    for(int j = (i + 1); j < sArr.length; j++)
    {
        if(sArr[min] > sArr[j])
        {
            min = j;
        }
    }
            
    // 찾은 최소값을 왼쪽으로 보내는 알고리즘
    temp = sArr[i];
    sArr[i] = sArr[min];
    sArr[min] = temp;
}

int형 배열에 무작위로 저장된 숫자를 선택 정렬로 오름차순 정렬하기 위해

최솟값의 인덱스를 저장할 변수(min)와 최솟값과 위치를 바꿀 값을 저장할 변수(temp)를 선언합니다.

최솟값을 찾고 0번째 인덱스부터 순차적으로 위치를 바꾸기 위해 중첩 반복문(for문)을 이용했습니다.

 

안의 for문에서는 최소값을 찾기 위해 sArr[min]의 값과 sArr[min+1]의 값을 비교하여

sArr[min]의 값의 클 경우 인덱스 min의 값을 min+1로 증가시켜 다음 값으로 이동합니다.

(min의 시작 값은 인덱스의 처음 값인 0입니다.)

 

예를 들어 0번째 값(13)과 1번째 값(9)을 비교하면 13이 크기 때문에 sArr[0]은 sArr[1]로 이동합니다.

그리고 1번째 값(9)과 2번째 값(4)을 비교하고 1번째 값이 크기 때문에 sArr[2]로 이동합니다.

계속해서 인덱스를 이동하다가 3번째 값(2)과 4번째 값(6)을 비교했을 때

이번에는 4번째 값이 크기 때문에 인덱스를 sArr[4]로 이동하지 않고 sArr[3]에 머무릅니다.

머무른 뒤에는 3번째 값(2)과 5번째 값(25)과 비교하여 이동할지 머무를지를 결정합니다.

이런 식으로 마지막까지 비교가 끝나면 min은 최솟값(2)이 저장된 인덱스 값(3)이 됩니다.

 

최솟값을 찾은 다음에는 밖의 for문으로 나와서 sArr[i]의 값을 변수 temp에 저장합니다.

그리고 sArr[min]을 sArr[i]에 저장하고 sArr[min]에는 temp의 값을 저장합니다.

이렇게 되면 최솟값이 sArr[i]로 이동하고 sArr[i]에 있던 값은 sArr[min]으로 이동하게 됩니다.

for문에서 i는 인덱스의 시작인 0이므로 sArr[0]의 값(13)을 temp에 저장하고 최솟값인 sArr[3]의 값(2)을

sArr[0]로 이동시키고 최솟값이 있던 sArr[3] temp에 저장된 값인 13이 이동하게 됩니다.

 

최솟값을 찾고 인덱스를 이동시킨 후에는 계속해서 순차적으로 그 다음 최소값을 찾고 이동시키면

마지막 값으로 최댓값이 남게 되고 선택 정렬을 이용한 오름차순 정렬이 끝나게 됩니다.

내림차순의 경우에는 안의 for문에서 sArr[min] > sArr[j]를 sArr[min] < sArr[j]로 바꿔주면

오름차순과 정반대로 최댓값을 찾고 이동시켜서 내림차순 정렬하게 됩니다.

선택 정렬은 이와 같이 이루어지게 되는데 만약에 데이터의 개수가 n개라고 하면
첫 번째 반복에서는 n개의 인덱스를 비교하고

두 번째 반복에서는 n-1개의 인덱스를 비교하고

세 번째 반복에서는 n-2개의 인덱스를 비교하고

계속해서 반복하다가 n-1번째 반복에서는 1개의 인덱스를 비교합니다.

그리 하여 선택 정렬의 비교 횟수는 n(n-1) / 2가 되고 이를 시간 복잡도로 나타내면 O(n^2)가 됩니다.

시간 복잡도는 프로그램의 성능과 이어지는데 선택 정렬은 비교할 데이터의 양이 적을 경우에는

좋은 성능을 보여주지만 비교할 데이터의 양이 많아지게 되면 성능이 급격하게 저하됩니다.

 

다음은 버블 정렬을 이용해 내림차순 정렬하는 방법은

선택 정렬처럼 배열의 모든 값을 확인하지 않고 순서대로 확인하면서

이웃된 인덱스의 값이 더 작을 경우 서로의 위치를 바꾸는 형식으로 이루어집니다.

오름차순은 반대로 이웃된 인덱스의 값이 더 클 경우에 위치를 바꾸면 됩니다.

// 버블 정렬(내림차순)
int[] sArr = {13, 9, 4, 2, 6, 25, 10};
int temp;        // 값 교환용 임시변수
 
// 버블 정렬 알고리즘
for(int i = (sArr.length - 1); i > -1; i--)
{
    for(int j = 0; j < i; j++)
    {
        if(sArr[j] < sArr[j + 1])
        {
            temp = sArr[j];
            sArr[j] = sArr[j + 1];
            sArr[j + 1] = temp;
        }
    }
}

버블 정렬로 내림차순 정렬하기 위해 위치를 바꿀 값을 저장할 변수(temp)를 선언합니다.

배열의 인덱스를 차례대로 확인하고 위치를 바꾸기 위해 중첩 반복문을 사용하였습니다.

밖의 반복문에서 배열의 길이에 -1을 한 값을 시작 값으로 주었고 조건값으로는 -1 이상을 주었습니다.

안의 반복문에서는 조건문을 사용해 0번째 인덱스부터 다음 인덱스와 값을 비교합니다.

만약 지금의 다음 인덱스의 값보다 지금 인덱스의 값이 작다면 현재 인덱스의 값을 임시 변수인 temp에 저장합니다.

그리고 다음 인덱스의 값을 현재 인덱스에 저장하고 temp에 저장된 값을 다시 다음 인덱스에 저장합니다.

 

예를 들어 sArr[0]의 값(13)과 sArr[1]의 값(9)을 비교하면 sArr[0]이 더 크기 때문에 위치를 바꾸지 않고

다음 인덱스로 넘어갑니다. 마찬가지로 sArr[1]의 값(9)과 sArr[2]의 값(4)을 비교해도 sArr[1]이 더 크기 때문에

다음으로 넘어갑니다. 이렇게 비교하다가 sArr[3]의 값(2)과 sArr[4]의 값(6)을 비교하면 sArr[3]의 값이 더 작기 때문에

sArr[3]의 값(2)을 temp에 저장하고 sArr[4]의 값(6)을 sArr[3]에 저장한 뒤에 sArr[4]에는 temp의 값을 저장하면

sArr[3]과 sArr[4]의 위치가 바뀌고 첫 번째 단계가 끝나게 됩니다. 

 

두 번째 단계에서는 sArr[4]의 값(2)과 sArr[5]의 값(25)의 위치가 서로 바뀌게 됩니다.

이러한 방식으로 반복하여 위치를 바꾸다가 더 이상 위치를 바꿀 값이 없으면 내림차순 정렬이 끝나게 됩니다.

선택 정렬과 마찬가지로 버블 정렬의 비교 횟수는 n(n-1) / 2가 되고 이를 시간 복잡도로 나타내면 O(n^2)가 됩니다.

버블 정렬의 경우에는 어느 정도 정렬이 되어 있는 배열의 경우에는 수행 속도가 빠르지만

하고자 하는 정렬과 반대로 정렬되어있는 경우에는 시간 복잡도가 제곱수 배로 증가하여 급격히 느려집니다.

이상으로 배열의 정렬에 대해 공부해보았습니다.

수고하셨습니다. 다음 글에서 봬요.