정렬 알고리즘

정렬 알고리즘

 

컴퓨터 과학과 수학에서 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘을 말합니다.

 

이런 정렬 알고리즘에도 여러가지 알고리즘이 존재합니다.

 

선택 정렬

 

1번째 원소부터 끝까지 훑어서 가장 작은 게, 1번째, 2번째 원소부터 끝까지 훑어서 가장 작은 게 2번째…해서 (n-1)번 반복합니다.

 

 

구현 코드

 

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {

        int[] nums = { 3, 1, 5, 4, 2 };
        for(int i = 0; i < nums.length; i++) {
            int minNum = i;
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[minNum] > nums[j])
                    minNum = j;
            }
            int temp = nums[minNum];
            nums[minNum] = nums[i];
            nums[i] = temp;
        }
        System.out.println("선택정렬 : " + Arrays.toString(nums));
    }
}

 

시간 복잡도

 

Best	Avg	Worst
n²	n²	n²

 

삽입 정렬

 

n번째 원소를 첫번째 원소와 k-1까지 원소와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식입니다.

 

 

구현 코드

 

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {

        int[] nums = { 3, 1, 5, 4, 2 };
        for(int end = 1; end < nums.length; end++) {
            for(int i = end; i > 0; i--){
                if(nums[i-1] > nums[i]){
                    int temp = nums[i-1];
                    nums[i-1] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        System.out.println("삽입정렬 : " + Arrays.toString(nums));
    }
}

 

시간 복잡도

 

Best	Avg	Worst
n	n²	n²

 

버블 정렬

 

1번째 원소와 2번째 원소를 비교하여 정렬하고, 2번째 원소와 3번째 원소를, …, n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n-2번째 원소와 n-1번째 원소까지 정렬한다.

 

 

구현 코드

 

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {

        int[] nums = { 3, 1, 5, 4, 2 };
        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < nums.length - i - 1; j++) {
                if(nums[j] > nums[j+1]) {
                    int temp = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        System.out.println("버블정렬 : " + Arrays.toString(nums));
    }
}

 

시간 복잡도

 

Best	Avg	Worst
n²	n²	n²