[Java] Interface를 활용한 정렬 알고리즘 구현

mincoder·2024년 11월 16일

실습 과제

목록 보기

4/4

Interface로 정렬 알고리즘 구현하기

이번 과제는 Java의 interface를 활용하여 selection sort(선택 정렬)와 insertion sort(삽입 정렬)를 구현하는 것입니다. 전체 문제를 다 다루지는 않을 것이고, 정렬을 구현하는 부분만 다뤄 보겠습니다.

SelectionSort

Abstract

Selection Sort는 Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. Selection Sort와 Insertion Sort를 헷갈려하는 사람들이 종종 있는데, Selection Sort는 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 편하다.

Process (Ascending)

주어진 배열 중에 최소값을 찾는다.

그 값을 맨 앞에 위치한 값과 교체한다. (pass)

맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

시간복잡도

최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일하다.

    public static void customSelectionSort(Comparable[] list) {

        int min;

        Comparable temp;



        for (int index = 0; index < list.length-1; index++) {

            min = index;

            for (int i = index+1; i < list.length; i++){
                if(list[i].compareTo(list[min])<0) min = i;
            }

            temp = list[min];
            list[min] = list[index];
            list[index] = temp;
        }
    }

Comparable 배열을 파라미터로 받는 이유는 정렬 알고리즘 대상이 int list, string list, Employer(새로운 클래스) list으로 다양하기 때문입니다. 선택 정렬의 구현을 보면, 최솟값을 찾아서 최솟값에 해당하는 인덱스를 min에 저장합니다. 그후에 값의 swap을 진행하는데, 각 정렬 횟수마다 처음 위치의 값(index)과 min 위치의 값을 교환해줍니다. (오름차순)

InsertionSort

Abstract

손 안의 카드를 정렬하는 방법과 유사하다. Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘이다. Insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘이다. 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.

Process (Ascending)

정렬은 2번째 위치(index)의 값을 temp에 저장한다.

temp와 이전에 있는 원소들과 비교하며 삽입해나간다.

'1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다

시간복잡도

최선의 경우는 O(n) 의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도를 갖게 된다.

  public static void customInsertionSort(Comparable[] list) {

        for (int index = 1; index < list.length; index++) {

            Comparable key = list[index];
            int position = index;



            // Shift larger values to the right

            while (position > 0 && key.compareTo(list[position-1]) > 0)   {
                list[position] = list[position-1];
                position--;
            }

            list[position] = key;
        }

    }

과제에서 삽입 정렬은 내림차순으로 정렬하라고 하여 내림차순으로 구현하였습니다. 삽입 정렬은 선택 정렬과 달리 Shifting 과정이 있습니다. 키 값을 설정하여, 키 값이 각 원소보다 크다면, 해당 원소를 오른쪽으로 밀어내고 키 값을 (각 반복의) 맨 앞 자리에 삽입하는 식으로 정렬합니다.