삽입정렬, 선택정렬, 버블정렬 시간복잡도 O(n^2) 정렬 알고리즘

삽입정렬

k번째 원소를 1부터 k-1번까지 비교하여 적절한 위치에 배치한 뒤 나머지는 k번부터 다시 밀어넣는 방식

시간복잡도 O(n^2)

선택정렬

반복하여 현재위치에 들어갈 값을 찾아서 정렬하는 방법

시간복잡도 O(n^2)

버블정렬

인덱스 2개를 반복 비교하여 정렬하는 방법

시간복잡도 O(n^2)

package com.example.lib;

public class myClass {

    // O(n^2)
    public int[] ascendingInsertionSort(int[] Arr) {
        int len = Arr.length;
        for(int i = 1; i < len; i++) {
            if(Arr[i] < Arr[i-1]) {
                for(int j = i; j > 0; j--) {
                    if(Arr[j] < Arr[j-1]) {
                        int temp = Arr[j];
                        Arr[j] = Arr[j-1];
                        Arr[j-1] = temp;
                    }
                }
            }
        }

        return Arr;
    }

    // O(n^2)
    public int[] ascendingSelectionSort(int[] Arr) {
        int len = Arr.length;
        for(int i = 0; i < len; i++) {
            int minIndex = i;
            int min = Arr[i];
            for(int j = i; j < len; j++) {
                if(Arr[j] < min) {
                    min = Arr[j];
                    minIndex = j;
                }
            }
            int temp = Arr[i];
            Arr[i] = Arr[minIndex];
            Arr[minIndex] = temp;
        }

        return Arr;
    }

    // O(n^2)
    public int[] ascendingBubbleSort(int[] Arr) {
        int lastIndex = Arr.length;
        while(lastIndex!=0){
            for(int i = 0; i < lastIndex - 1; i++) {
                int temp = Arr[i];
                if(Arr[i] > Arr[i+1]) {
                    Arr[i] = Arr[i+1];
                    Arr[i+1] = temp;
                }
            }
            lastIndex--;
        }
        return Arr;
    }


    public static void main(String[] args)
    {
        myClass test = new myClass();
        test.ascendingSelectionSort(new int[]{10,9,8,4,1,0});
        test.ascendingBubbleSort(new int[]{10,9,8,4,1,0});
        test.ascendingInsertionSort(new int[]{10,9,8,4,1,0});
    }
}

참고

나무위키 선택정렬