Lavine's Dev Site

버블 정렬 (Bubble Sort)

정렬 순서 (오름차순 정렬 기준)

1. 인접한 원소 두 개((arr[0], arr[1]), (arr[1], arr[2]) ~ (arr[n-2], arr[n-1]))를 쌍으로 지어 앞에 위치한 원소가 뒤의 원소보다 크다면 swap한다.
2. 1회전을 끝내게 되면 배열 내의 가장 큰 원소가 가장 마지막에 배치된다. (뒤에서부터 정렬이 완료된다.)
3. 따라서 1~2과정을 정렬되지 않은 원소가 1개가 될때까지 반복한다. 

예시

장점

• 구현이 쉽고 이해하기 쉽다.
• In-place Sorting Algorithm
  • 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n)
• 안정 정렬 (Stable Sorting)
  • 중복 값이 입력 순서와 동일하게 정렬 됨

단점

•  O(n²)의 시간복잡도
• 정렬을 위해 swap 과정이 많이 일어나게 된다. (계산 시간 상승)
  • 다른 O(n²) 시간 복잡도를 갖는 삽입, 선택 정렬보다 오래 걸리게 된다.

시간 복잡도 

• 원소 비교 횟수
  • n-1, n-2, ... ,2, 1 = n(n-1)/2
• swap: 최악의 경우 비교 횟수마다 교환 진행
  • 3 * (n(n-1)/2)
• T(n) =  n(n-1)/2 + (3 * (n(n-1)/2))∈ O(n²) 

Code (C/C++)

#include <stdio.h>
#define LENGTH 5

// bubbleSort
void bubbleSort(int* arr){
    // outer loop: 배열 크기 - 1 만큼 반복 (회전 횟수)
    for(int i = 1; i < LENGTH; i++) {
        // inner loop: 각 회전 횟수만큼 뺀 만큼 비교 (회전마다 맨 뒤 공간부터 정렬된다)
        for(int j = 0; j < LENGTH - i; j++) {
            // 이전 원소가 다음 원소보다 큰 경우 swap
            if(arr[j] > arr[j+1]) {
                // swap
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

int main() {
    int arr[LENGTH] = {7,4,2,9,5};
    printf("Before Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    bubbleSort(arr);

    printf("After Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
}

Code (Java)

public class sorting {
    public static void main(String[] args) {
        int[] arr = {7, 4, 2, 9, 5};
        System.out.print("Before Sorting: ");
        printArr(arr);
        bubbleSort(arr);
        System.out.print("After Sorting: ");
        printArr(arr);
    }

    // Print Array
    static void printArr(int[] arr) {
        int l = arr.length;
        for (int i = 0; i < l; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // Bubble sort
    static void bubbleSort(int[] arr) {
        int l = arr.length;
        // outer loop: 배열 크기 - 1 만큼 반복 (회전 횟수)
        for (int i = 1; i < l; i++) {
            // inner loop: 각 회전 횟수만큼 뺀 만큼 비교 (맨 뒤 공간부터 정렬된다)
            for (int j = 0; j < l - i; j++) {
                // 이전 원소가 다음 원소보다 큰 경우 swap
                if (arr[j] > arr[j + 1]) {
                    // swap
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }
}

선택 정렬 (Selection Sort)

정렬 순서 (오름차순 정렬 기준)

1. 주어진 리스트에서 최소 값을 찾는다.
2. 최소 값을 유효 범위 내에서 맨 앞의 값과 swap한다.
3. swap된 위치를 제외 한 나머지 공간이 1개가 될때까지 1 ~ 2를 반복한다.

예시

장점

• 구현이 쉽고 이해하기 쉽다.
• In-place Sorting Algorithm
  • 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n)

단점

•  O(n²)의 시간복잡도
• 불안정 정렬 (Unstable sorting)
  • 중복 값 순서 보장 못함

시간 복잡도 

• 외부 루프: (n-1)번 반복
• 최솟값 탐색: n-1, n-2, n-3, ... ,2, 1
• T(n) =  1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2 ∈ O(n²) 

Code (C/C++) 

#include <stdio.h>
#define LENGTH 5

// Selection Sort
void selectionSort(int* arr){

    // 맨 마지막 원소는 알아서 정렬이 되기 때문에 l-2까지 반복
    for(int cur = 0; cur < LENGTH -1 ; cur++) { 
       int min = cur;
       
       // 최소값 찾기
       for(int j = cur + 1; j < LENGTH; j++) {
           if(arr[min] > arr[j])
                min = j;
       }
       
       // 최소값이 자기 자신인 경우 swap이 필요없다.
      if(min == cur)
        continue;
            
      int tmp = arr[min];
      arr[min] = arr[cur];
      arr[cur] = tmp;
    }
}

int main() {
    int arr[LENGTH] = {7,4,2,9,5};
    printf("Before Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    selectionSort(arr);

    printf("After Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
}

Code (Java)

public class sorting {
    public static void main(String[] args) {
        int[] arr = {7,4,2,9,5};
        System.out.print("Before Sorting: ");
        printArr(arr);
        selectionSort(arr);
        System.out.print("After Sorting: ");
        printArr(arr);
    }

    // Print Array
    static void printArr(int[] arr) {
        int l = arr.length;
        for(int i = 0; i<l; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    // Selection Sort
    static void selectionSort(int[] arr) {
        int l = arr.length;
        
        // 맨 마지막 원소는 알아서 정렬이 되기 때문에 l-2까지 반복
        for(int cur = 0; cur < l-1; cur++) {   
            int min = cur;
            
            // 최소값 찾기
            for(int j = cur + 1; j < l; j++) {
                if(arr[min] > arr[j])
                    min = j;
            }
            
            // 최소값이 자기 자신인 경우 swap이 필요없다.
            if(min == cur)
                continue;
                
            // swap
            int tmp = arr[min];
            arr[min] = arr[cur];
            arr[cur] = tmp;
        }
    }
}

정렬 알고리즘(Sorting Algorithm)

 정렬 알고리즘이란 n개로 이루어진 배열이 주어져있을 때, 이를 번호순 혹은 사전 순 같이 일정 순서대로 열거를 해주는 알고리즘을 의미한다. 데이터를 정렬하는 이유는 탐색 및 데이터 편집 시 시간을 절약하기 위해서이다. 예를 들어 정렬이 안되어 있는 데이터를 탐색하려면 데이터를 순차적으로 조사해야 하지만 정렬이 되어있을 경우 이진탐색과 같은 알고리즘을 사용하여 탐색시간을 효율적으로 줄일 수 있기 때문이다.

삽입 정렬 (Insertion Sort)

정렬 순서

1. 비교 대상이 되는 원소를 잡고 앞에 있는 원소들과 비교를 한다. 
2. 비교대상이 되는 원소가 이전 위치의 원소보다 작다면 swap
3. 마지막 인덱스 원소까지 1~2를 반복한다.

예시

장점

• 구현이 쉽고 이해하기 쉽다.
• In-place Sorting Algorithm
  • 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n)
• 대부분 정렬이 되어 있는 경우 시간복잡도가 O(n)에 수렴한다. (Best Time Complexity = O(n))
• 안정 정렬 (Stable Sorting)
  • 중복 값이 입력 순서와 동일하게 정렬 됨.

단점

•  O(n²)의 시간복잡도

시간 복잡도 

• Best Time Complexity
  • 데이터가 이미 정렬되어 있는 경우 
  • 총 비교 횟수는 n-1번이 되기 때문에 O(n)
• Worst Time Complexity
  • 데이터가 역순으로 정렬되어 있는 경우
  • 매 회전에서는 앞에 놓인 데이터들이 모두 한 칸씩 뒤로 움직여야 한다.
  • 외부 루프: T(n) = 1 +2 + ... + (n-2) + (n-1) = n(n-1)/2 ∈ O(n²)
  • 내부 교환: O(n)
  • Worst Time Complexity: O(n²) + O(n) ∈ O(n²)

Code (C/C++) 

#include <stdio.h>
#define LENGTH 5

// insertion Sort
void insertionSort(int* arr){
    for(int i = 1; i<LENGTH; i++) { // 두번째 원소부터 시작
        int cur = arr[i];
        int prev = i - 1;   // 이전 데이터

        // cur 데이터보다 앞에 있는 원소들 중 cur 데이터보다 큰 값이 있는 경우
        while(prev >= 0 && cur < arr[prev]) {
            arr[prev+1] = arr[prev];    // 우측으로 1칸씩 이동
            prev--;
        }
        arr[prev+1] = cur;     // 정렬 순서에 맞는 위치에 저장
    }
}

int main() {
    int arr[LENGTH] = {7,4,2,9,5};
    printf("Before Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    insertionSort(arr);

    printf("After Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
}

Code (Java)

public class sorting {
    public static void main(String[] args) {
        int[] arr = {7,4,2,9,5};
        System.out.print("Before Sorting: ");
        printArr(arr);
        insertionSort(arr);
        System.out.print("After Sorting: ");
        printArr(arr);
    }

    // Print Array
    static void printArr(int[] arr) {
        int l = arr.length;
        for(int i = 0; i<l; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    // Insertion Sort
    static void insertionSort(int[] arr) {
        int l = arr.length;
        for(int i = 1; i < l; i++) {   // 두번째 원소부터 시작
            int cur = arr[i];
            int prev = i - 1;    // 이전 데이터

            // cur 데이터보다 앞에 있는 원소들 중 cur 데이터보다 큰 값이 있는 경우
            while(prev >= 0 && cur < arr[prev]){
                arr[prev+1] = arr[prev];    // 우측으로 1칸씩 이동
                prev--;
            }
            arr[prev+1] = cur;  // 정렬 순서에 맞는 위치에 저장
        }
    }
}