[알고리즘] 정렬(Sort) 알고리즘

 

들어가기 전

예를 들어 선택 정렬의 로직을 배우고 "선택"이라는 이름과 로직이 매칭이 잘 안 되었다.

그러다 보니까, 로직을 강제로 암기를 하게 되고 시간이 지나면 까먹는 문제가 생긴다.

 

즉, 선택과 정렬 등의 단어가 왜 사용하고 있는지 어원을 이해 해보자!!!

정렬 알고리즘

1. 퀵 정렬(Quick Sort)

동작 방법

퀵 정렬 방법

코드 작성

 

2. 선택 정렬(Selection Sort)

어원편

선택 정렬(Selection Sort)에서 선택이라는 단어는 정렬되지 않은 데이터 중에서 가장 작은(또는 가장 큰) 값을 "선택"하여 정렬된 부분으로 이동시키는 방식에서 유래했습니다.

 

동작 방법

• https://www.youtube.com/watch?v=uCUu3fF5Dws

 

코드 작성

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

        int[] arr = {3, 6, 1, 8, 2, 4};
        for (int i = 0; i <arr.length - 1; i++) { // 배열의 마지막까지 확인할 필요가 없다.
            int minIndex = i;
            for (int j = i + 1; j<arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // swap
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }

        System.out.println("arr = " + Arrays.toString(arr));

    }
}

3.  삽입 정렬(Insertion Sort)

어원편

값을 정렬된 부분에 알맞은 위치에 삽입한다. 마치 손에 카드를 들고 정렬하는 방식과 유사합니다. 새로운 카드를 알맞은 자리에 "삽입"하는 방식으로 정렬을 진행.

 

동작 방법

 

코드 작성

import java.util.*;

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

        int[] arr = {7,2,3,8};
        insertion_sort(arr, arr.length);


    }

    private static void insertion_sort(int[] a, int size) {
        for (int i = 1; i < size; i++) {
            int target = a[i];
            int j = i - 1;

            // target이 a[j]보다 작을 경우, j를 하나씩 왼쪽으로 이동
            while (j >= 0 && target < a[j]) {
                a[j + 1] = a[j];  // a[j]를 한 칸 뒤로 이동
                j--;
            }

            a[j + 1] = target;  // target을 적절한 위치에 삽입
        }

        System.out.println("a = " + Arrays.toString(a));
    }
}

 

4.  버블 정렬(Bubble Sort)

동작 방법

출처:  https://sfida.tistory.com/30  [Meezzi 미찌:티스토리]

 

회전은 배열크기 - 1 번 수행하고,

비교연산은 배열크기 - 라운드 횟수 번 수행한다.

출처: https://sfida.tistory.com/30 [Meezzi 미찌:티스토리]

 

코드 작성

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {

        int[] arr = { 5, 2, 9, 4, 7, 1};
        bubbleSort(arr);
    }

    private static void bubbleSort(int[] arr) {

        // 회전 횟수
        for (int i=0; i < arr.length-1; i++) {

            // 비교연산
            for (int j=1; j < arr.length - i; j++) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }

		// arr = [1, 2, 4, 5, 7, 9]
        System.out.println("arr = " + Arrays.toString(arr));
    }
}

 

5. 힙 정렬(Heap Sort)

동작 방법

 

코드 작성