본문으로 바로가기

안녕하세요.


오늘은 내부정렬(버블정렬,선택정렬,삽입정렬)의 시간복잡도에 대해 알아보겠습니다.


버블정렬과 선택정렬 삽입정렬 모두 시간복잡도는 O(n²) 로 동일한데요.


그럼 과연 난수 배열을 생성하여 정렬을 시작하고 끝나는 시간이 모두 같은지 확인해보겠습니다.


12만개의 난수 배열을 생성하여 정렬시간을 비교해보았습니다.


결과는 거의 모든 상황에서 삽입정렬이 가장 빨리 끝이났고 버블정렬과 선택정렬은 비슷한 시간이 나오는것을 확인할수 있었습니다.


삽입정렬은 최악의 경우 시간복잡도가 O(n²)인 반면 버블정렬과 선택정렬은 항상 모든상황에서 자신만의 정렬 알고리즘을 전부 수행하기때문에 일정한 시간이 나오는데요.


삽입정렬 같은경우 최악의 경우는 잘 나오지 않기때문에 가장 빠르게 끝나버리는것같습니다.


그래서 난수배열이 아닌 12만크기인 배열에 12만부터 0까지 역순으로 값을 집어넣고 정렬을 한 결과입니다.


그래도 삽입 정렬이 가장빠르지만 확실히 다른 정렬들과 비슷해진것을 알 수 있습니다..


삽입 정렬이 그래도 빠른이유는 다른 정렬 알고리즘보다 내부 반복문이(for문의 조건절에서 비교를하기때문에) 빨라서 그런것 같습니다(이부분에 대해 정확히 아시는분이 계시면 알려주세요.)


아래는 정렬에 사용한 코드입니다.

import java.util.Scanner;
 
public class SortTest extends Thread {
    public static void main(String[] args) {
        System.out.print("배열크기를 정해주세요 : ");
        Scanner sc = new Scanner(System.in);
        int snum = sc.nextInt();
 
        int[] num = new int[snum];
 
        System.out.println("난수배열 생성시작");
        for (int i = 0; i < snum; i++) {
            num[i] = (int) (Math.random() * snum);
            //System.out.println("[" + i + "]:" + num[i] + " ");
        }
        System.out.println("난수배열 생성완료");
        System.out.println();
 
        Bubble bubble = new Bubble(num);
        Selection selection = new Selection(num);
        Insertion insertion = new Insertion(num);
         
        bubble.start(); // 버블정렬 시간복잡도 (O(n²))
        selection.start(); // 선택정렬  시간복잡도 (O(n²))
        insertion.start(); // 삽입정렬  시간복잡도 (O(n²)) - 최악의경우
    }
 
}
 
class Bubble extends Thread {
    int[] a;
    int b;
 
    Bubble(int[] array) {
        a = array;
    }
 
    @Override
    public void run() {
        System.out.println("버블정렬 시작");
        long start = System.currentTimeMillis();
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    b = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = b;
                }
            }
        }
        long endTime = System.currentTimeMillis();

        System.out.println("버블정렬 끝. 수행시간 : " + (endTime - start) / 1000.0f + "초");
    }
}
 
class Selection extends Thread {
    int[] a;
    int b;
 
    Selection(int[] array) {
        a = array;
    }
 
    @Override
    public void run() {
        System.out.println("선택정렬 시작");
        long start = System.currentTimeMillis();
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {
                    b = a[j];
                    a[j] = a[i];
                    a[i] = b;
                }
            }
        }
        long endTime = System.currentTimeMillis();

        System.out.println("선택정렬 끝. 수행시간 : " + (endTime - start) / 1000.0f + "초");
    }
}
 
class Insertion extends Thread {
    int[] a;
    int b, j;
 
    Insertion(int[] array) {
        a = array;
    }
 
    @Override
    public void run() {
        System.out.println("삽입정렬 시작");
        long start = System.currentTimeMillis();
        for (int i = 1; i < a.length; i++) {
            b = a[i];
            for (j = i - 1; j >= 0 && a[j] > b; j--) {
                a[j + 1] = a[j];
            }
            a[j + 1] = b;
        }
        long endTime = System.currentTimeMillis();

        System.out.println("삽입정렬 끝. 수행시간 : " + (endTime - start) / 1000.0f + "초");
    }
}


입력한 수만한 크기의 배열에 입력한갯수만큼의 난수를 집어넣어 세가지 정렬알고리즘을 비교해본 코드입니다.


혹시 잘못된 코드나 정보가 있으면 알려주세요.


댓글을 달아 주세요