Java의 선택 정렬

Selectionsort는 물론 Java에서도 구현될 수 있는 정렬 알고리즘입니다. Selectionsort 알고리즘은 MinSort(최소에서) 또는 MaxSort(최대에서), Selectsort 또는 ExchangeSort라고도 합니다. Selectsort 알고리즘 뒤에 숨겨진 것, 작동 방식 및 기타 알아야 할 사항은 이제 다음에서 배우게 됩니다.

기능

Selectionsort의 기능은 다음과 같습니다. 정렬할 데이터가 포함된 배열이 있습니다. 이제 배열을 두 부분(하위 배열)으로 나눕니다. 첫 번째 부분은 정렬된 부분이고 두 번째 부분은 정렬되지 않은 부분이어야 합니다. 처음에는 아무 것도 정렬되지 않으므로 전체 배열은 정렬되지 않은 부분을 나타냅니다.
이제 배열에서 가장 작은 요소를 찾아 첫 번째 요소로 바꿉니다. 이제 첫 번째 요소는 정렬된 부분에 있고 나머지 요소는 정렬되지 않은 부분에 있습니다. 이제 가장 작은 요소가 정렬되지 않은 부분에서 다시 검색되고 이것은 이제 정렬된 영역의 첫 번째 요소 뒤에 삽입됩니다. 이것은 모든 요소가 정렬된 영역에 있고 정렬되지 않은 영역에는 아무것도 없을 때까지 계속됩니다. 가장 큰 요소부터 시작하여 크기별로 정렬하려면 항상 가장 작은 요소 대신 가장 큰 요소를 검색하십시오. 따라서 Simplesort와 유사하게 배열의 나머지 하위 범위가 전면에서 통과됩니다.


다음은 테스트 출력을 포함하여 함수에 저장된 선택 정렬 알고리즘의 구현 예입니다.

public static void main(String[] args) {

        int[] unsorted = { 4, 2, 1, 6, 3, 5 };
        int[] sorted = selectionsort(unsorted);

        for (int i = 0; i < sorted.length; i++) {
            System.out.print(sorted[i] + ", ");
        }

    }

    public static int[] selectionsort(int[] sorted) {
        for (int i = 0; i < sorted.length - 1; i++) {
            for (int j = i + 1; j < sorted.length; j++) {
                if (sorted[i] > sorted[j]) {
                    int temp = sorted[i];
                    sorted[i] = sorted[j];
                    sorted[j] = temp;
                }
            }
        }

        return sorted;
    }

실행 시간

Selectionsort Worst Case의 런타임은 Best Case의 복잡성과 정확히 일치합니다. 따라서 Selectionsort 런타임은 항상 O(n2)입니다. 사전 정렬된 데이터에 관계없이 목록이 항상 앞에서 뒤로 완전히 실행되기 때문에 여기에는 매우 간단한 이유가 있습니다.

최적화

selectionsort 알고리즘의 최적화는 한 번에 가장 큰 요소와 가장 작은 요소를 동시에 검색하는 것입니다. 이 경우 가장 작은 요소는 배열의 시작 부분으로 이동하고 가장 큰 요소는 마지막 위치로 교체됩니다. 이것은 일반적으로 2배의 속도 향상을 제공합니다. 이것은 "최적화된 선택 정렬 알고리즘(OSSA)"이라고 합니다.