[Inflearn] 영리한 프로그래밍을 위한 알고리즘 - 기본적인 정렬 알고리즘

정렬 알고리즘
Selection sort, Bubble sort, Insertion sort

 

* 버블 정렬, 삽입 정렬, 선택 정렬 : 구현이 단순하지만 속도가 느림

* 퀵 정렬, 합병(병합) 정렬, 힙 정렬 : 구현이 복잡하지만 속도가 빠름

* Radix sort : 위에 것들과 다른 방식으로 작동되는 정렬 - ? 뒤에서 확인해보자.

 

 

 

선택 정렬 Selection Sort

가장 큰 값을 찾아 배열의 맨 마지막 위치의 값과 바꾼다.

맨 마지막에 있는 값이 가장 큰 값이 되기 때문에 다음 정렬에서는 0부터 n-1번째 값까지 탐색하며 최대값을 찾는 동작을 반복한다.

 

 

 

* 선택 정렬의 시간복잡도 : O(x^n)

최악의 경우 = 평균의 경우 = 최선의 경우

 

 

* 선택 정렬 자바 코드 ( selection sort java code )

Ver1. 강의에서 배운 코드

import java.util.Arrays;

public class sort {
    public static void main(String[] args) {
        int[] a = {4, 9, 2, 6, 8, 5, 7, 1, 3};
        int n = a.length;
        
	// Selection sort
        for (int last = n-1; last >= 1; last--) { // 인덱스 0은 비교 안해도 됨.
            int max_index = last;
            for (int i = 0; i <= last-1; i++) {
                if(a[max_index] < a[i]) max_index=i;
            }
            int tmp = a[max_index];
            a[max_index] = a[last];
            a[last] = tmp;
            System.out.println(Arrays.toString(a));
        }
    }       
}

결과

 

 

Ver2. 내가 구현하기 쉬웠던 코드 (가장 작은 수를 찾아 인덱스 0부터 채움)

import java.util.Arrays;

public class sort {
    public static void main(String[] args) {
        int[] a = {4, 9, 2, 6, 8, 5, 7, 1, 3};
        int n = a.length;
        
        int min, tmp;
        for(int i=0; i<n-1; i++){ // n-1 : 마지막 요소는 자연스럽게 정렬됨
            min = i;
            for(int j=i+1; j<n; j++){
                if(a[min] > a[j]){
                    min = j;
                }
            }
            tmp = a[min];
            a[min] = a[i];
            a[i] = tmp;
            System.out.println(Arrays.toString(a));
        }
    }
}

결과

 

 

 

 

 

버블 정렬 Bubble Sort

첫 번째 값부터 다음 값과 비교해서 자기가 더 크면 자리를 바꾼다.

최대값은 계속 자리가 바뀌어 맨 오른쪽으로 이동한다.

맨 마지막에 있는 값이 가장 큰 값이 되기 때문에 다음 정렬에서는 0부터 n-1번째 값까지 탐색하며 최대값을 찾는 동작을 반복한다.

 

 

* 버블 정렬의 시간복잡도 : O(x^n)

최악의 경우 = 평균의 경우 = 최선의 경우

 

 

* 버블 정렬 자바 코드 ( bubble sort java code )

Ver1. 강의에서 배운 코드

import java.util.Arrays;

public class sort {
    public static void main(String[] args) {
        int[] a = {4, 9, 2, 6, 8, 5, 7, 1, 3};
        int n = a.length;

        for (int last = n; last >= 2; last--) {
            for (int i = 0; i < last-1; i++) {
                if(a[i] > a[i+1]) {
                    int tmp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = tmp;
                }
            }
            System.out.println(Arrays.toString(a));
        }
    }
}

첫 번째 for문을 (int last=n-1; last>=1; last--)라고 했으면 의미가 더 쉽지 않았을까?

(그래서 선택 정렬 Ver1. 코드에서 좀 바꿔봄ㅎ)

배열 시작을 인덱스 1 끝을 인덱스 n으로 강의가 되어있어 구현하는데 살짝 헷갈렸다.

 

 

Ver2. 내가 구현하기 쉬웠던 코드

import java.util.Arrays;

public class sort {
    public static void main(String[] args) {
        int[] a = {4, 9, 2, 6, 8, 5, 7, 1, 3};

         // Bubble Sort
        for(int i = 0 ; i < a.length-1 ; i ++) {
            for(int j = 0 ; j < a.length -i -1 ; j ++) {
                if(a[j]>a[j+1]) {
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
            System.out.println(Arrays.toString(a));
        }
    }
}

결과

 

 

 

 

 

삽입 정렬 Insertion Sort

첫 번째 값은 이미 정렬이 되어 있다고 가정한다.

그 상태로 2, 3, 4, ... 번째의 값들을 차례로 정렬되는 위치에 삽입해준다.

 

15는 정렬이 된 상태.

다음 숫자인 12는 15보다 작기 때문에 15의 왼쪽으로 정렬,

그 다음 숫자인 13은 12와 15 사이의 숫자이기 때문에 그 사이로 정렬,

이렇게 마지막에 있는 숫자까지 제 위치를 찾아서 기존 정렬된 숫자들에 하나씩 끼워 넣어 준다.

 

 

동작 방식은 삽입하고자 하는 숫자를 tmp에 담고

비교할 숫자가 tmp에 있는 숫자보다 크다면 한 칸씩 오른쪽으로 밀어내는 동작을 반복한다.

tmp보다 작은 작은 숫자를 만났다면 바로 오른쪽 위치에 tmp에 있는 숫자를 넣어준다.

(혹은 앞에서부터 비교를 시작해 tmp에 있는 숫자가 들어갈 자리를 찾아준다.)

 

 

* 삽입 정렬의 시간복잡도 : O(x^n)

최선의 경우 : O(n)

평균의 경우 : O(x^n)의 절반 정도의 시간

최악의 경우 : O(x^n)

 

 

* 삽입 정렬 자바 코드 ( insertion sort java code )

Ver1. 강의에서 배운 코드

import java.util.Arrays;

public class sort {
    public static void main(String[] args) {
        int[] a = {4, 9, 2, 6, 8, 5, 7, 1, 3};
        int n = a.length;

        // Insertion sort
        for (int i = 1; i <= n-1; i++) { // 인덱스 0은 정렬되어 있다고 가정.
            int tmp = a[i]; // 정렬하고자 하는 값
            for (int j = i-1; j >= 0; j--) {
                if(tmp < a[j]) { // 이전 값들보다 작다면 swap
                    a[j+1] = a[j];
                    a[j] = tmp;
                }
                else break;
            }
            System.out.println(Arrays.toString(a));
        }

 

 

Ver2. 

import java.util.Arrays;

public class sort {
    public static void main(String[] args) {
        int[] a = {4, 9, 2, 6, 8, 5, 7, 1, 3};
        int n = a.length;
        
        for(int i = 1; i < n; i++) {
            int target = a[i];
            int j = i - 1;
            while(j >= 0 && target < a[j]) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = target;
            System.out.println(Arrays.toString(a));
        }

결과