정렬 구현하기

'자료구조' 수업을 최근 계속 들어왔는데 오늘 처음으로 정리해보네요! 오늘은 수업시간에 정렬을 구현해보는 실습을 했는데요. 생각보다 쉽지 않더라구요. 주어진 미션은 다음과 같습니다.

• 배열 생성하기
• 그 배열 무작위로 섞기
• 본인이 구현하고 싶은 정렬방법으로 정렬하기

 

배열 생성하기

배열을 생성하는 방법은 어렵지 않죠. 보통은 for문의 인덱스를 이용하여 만드는데요. 이번엔 IntStream 을 이용하여 만들어보았습니다.

public int[] genArray(int size) {
        return IntStream.range(0, size).toArray();
    }

 

배열 무작위로 섞기

Collections.shuffle() 를 사용하지 않고 배열을 무작위로 섞는 방법을 생각해봤는데요. 생각보다 쉽지 않았습니다. 그러다가 knuth shuffle에 대해 배웠는데요. 이를 이용하면 다음과 같이 구현할 수 있습니다.

public static void shuffle (int[] array) {
    int n = array.length;
    while (n > 1) {
        int k = gen.nextInt(n--); //decrements after using the value
        int temp = array[n];
        array[n] = array[k];
        array[k] = temp;
    }
}

참고 : https://www.rosettacode.org/wiki/Knuth_shuffle#Java

설명을 하자면 while문을 돌면서 n범위 내 랜덤값을 찾아 k에 저장합니다. 이 랜덤값 k와 n과의 자리를 바꿉니다(swap). 그 다음은 n을 하나 줄여 n이 1보다 클때까지 진행합니다. 여기서 1보다 클때만 반복하는 이유는 Random 의 nextInt() 에 넣는 매개변수가 만약 m이라면 0부터 m-1범위 내 랜덤값을 고르기 때문입니다. 즉, n=1일때는 0밖에 안나오기 때문에 큰 의미가 없는 것이죠.

 

정렬하기

저는 Insert Sort를 사용하여 정렬하였습니다. '삽입정렬'이라고 불리는데요. 먼저 코드부터 보겠습니다.

    // insert sort
    public void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int temp = arr[i];
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > temp) swap(arr, j, j + 1);
                else break;
            }
        }
    }

전 조금 비효율적으로 삽입정렬을 한 것 같아 다른 사이트의 코드를 참고하여 설명할게요.

    /*Function to sort array using insertion sort*/
    void sort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=1; i<n; ++i) 
        { 
            int key = arr[i]; 
            int j = i-1; 
  
            /* Move elements of arr[0..i-1], that are 
               greater than key, to one position ahead 
               of their current position */
            while (j>=0 && arr[j] > key) 
            { 
                arr[j+1] = arr[j]; 
                j = j-1; 
            } 
            arr[j+1] = key; 
        } 
    } 

참고 : https://www.geeksforgeeks.org/insertion-sort/

삽입정렬을 기본적으로 가리키는 숫자를 들어올린다음 비교해가면서 적절한 자리에 다시 삽입하는 것으로 이미지를 그리면 이해하기 쉬운데요. 위 코드에서 key가 숫자를 들어올리는 수 입니다. 그리고 j는 들어올린 수의 바로 이전의 인덱스이죠. 그리고 반복문 돌릴때는 j를 줄여나가면서 key보다 큰 수를 뒤로 다 밀고 더 작은 수를 발견하면 그 바로 뒤에 key 값을 넣는 것입니다.

 

오늘 정렬 관련한 코드를 구현해보면서 제가 얼마나 망각의 동물인지, 아직 각각의 정렬에 대한 개념들이 확실히 머리 속에 잡히지 않았다는 것을 확인할 수 있었습니다. 다음 수업엔 정렬을 계속 다룬다고 하니 빠지지 않고 다시 잘 배워두어야겠습니다!