整列選択(Selection Sort)

注意:https://gyoogle.dev/blog/algorithm/Selection%20Sort.html

「ソートの選択」(Selection Sort)とは?

バブルソート(Bubble Sort)のアルゴリズムと同様に、この順序に要素を加える位置が決定され、どの要素を加えるかを選択するアルゴリズムである.

プロセス

で指定された配列で最小値を探します.

値

を一番前の値に置き換えます.

は、第1の位置を除いた残りの配列を同様の方法で置換する.

そして2番目の位置、3番目の位置、...ソートは、それ以外の配列で実行されます.

Java Code (Ascending)

void selectionSortAsc(int[] arr) {
    int indexMin, temp; // 최소값의 위치를 저장할 변수(indexMin)와 교환 시 값을 임시 저장할 변수(temp)
    
    // 최소값으로 교환할 위치 (첫번째, 두번째, ...)
    for (int i=0; i<arr.length-1; i++) {
        indexMin = i;
        // 정렬이 완료된 위치(i) 이후부터 정렬 수행
        for (int j=i+1; j<arr.length; j++) {
            // 비교할 값이 indexMin 위치의 값보다 작으면 indexMin의 값을 해당 위치값으로 바꾼다.
            if (arr[j] < arr[indexMin]) {
                indexMin = j;
            }
        }
        
        // 자리 교환
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
    }
    
    System.out.println(Arrays.toString(arr));
}

Java Code (Descending)

void selectionSortDesc(int[] arr) {
    int indexMax, temp; // 최대값의 위치를 저장할 변수(indexMax)와 교환 시 값을 임시 저장할 변수(temp)
    
    // 최대값으로 교환할 위치 (첫번째, 두번째, ...)
    for (int i=0; i<arr.length-1; i++) {
        indexMax = i;
        for (int j=i+1; j<arr.length; j++) {
            // 비교할 값이 indexMax 위치의 값보다 크면 indexMax의 값을 해당 위치값으로 바꾼다.
            if (arr[j] > arr[indexMax]) {
                indexMax = j;
            }
        }
        
        // 자리 교환
        temp = arr[indexMax];
        arr[indexMax] = arr[i];
        arr[i] = temp;
    }
    
    System.out.println(Arrays.toString(arr));
}

時間の複雑さ

n個のデータがある場合、

の1回目の回転における比較回数:1~(n-1)=>n-1

の2回目の回転における比較回数:2~(n-1)=>n-2
...

(n-1) + (n-2) + ... + 2 + 1 => n(n-1)/2
比較が定数時間内に行われると仮定すると,n個の与えられた配列を並べ替えるにはO(n^2)の時間が必要となる.最適,平均,最悪の場合,時間複雑度はO(n^2)である.

くうかんふくざつさ

与えられた配列では,交換によりソートされるのでO(n)である.

長所

バブルソートと同様にアルゴリズムは簡単である.

ソートの比較回数は多いが、実際の交換回数はバブルソートに比べて少ないため、大量の交換が必要な場合には比較的効率的である.

バブルソート(Bubble Sort)と同様に、ソートするアレイ内で交換する方法であり、他のメモリ領域は必要ありません.=>現地ソート

短所

時間複雑度はO(n^2)であり,効率は低下した.

不安定なソート.