정렬이란?

특정 값을 기준으로 데이터를 순서대로 배치하는 방법이다.

정렬의 종류

정렬도 난이도와 속도에 따라 여러가지로 나눌 수 있다. 이번에는 그 중에서 구현난이도가 쉽지만 속도는 느린 버블 정렬, 삽입 정렬, 선택 정렬에 대해 구현법을 알아봤다. 이 세가지 정렬 방법은 swap하는데 필요한 tmp변수가 사용하는 메모리 말고는 추가적인 메모리를 사용하지 않는 inplace정렬법이다! 그래서 구현하기는 쉽지만 속도는 느리다. (메모리 사용량과 속도는 반비례관계가 있다.)

  • 구현 난이도 easy / 속도 slow : O(n2)O(n^2)
    • 버블 정렬
    • 삽입 정렬
    • 선택 정렬
  • 구현 난이도 difficult / 속도 fast : O(nlogn)O(n logn)
    • 합병 정렬
    • 힙 정렬
    • 퀵 정렬
    • 트리 정렬
  • 하이브리드 정렬: 여러가지 정렬 방법이 합쳐진 정렬 방법
    • 팀 정렬
    • 블록 병합 정렬
    • 인트로 정렬
  • 기타 정렬 알고리즘
    • 기수 정렬
    • 카운팅 정렬
    • 셸 정렬

버블 정렬 (Bubble sort)

버블 정렬은 인접한 데이터를 비교하며 자리를 바꾸는 방식이다.
1번 정렬할 때마다 가장 큰 값의 위치가 정해진다(오름차순).
해당 인덱스와 그 이전 인덱스를 비교했을 때, 이전 인덱스가 더 크면 두 값을 교환한다.

버블 정렬 예시 그림

버블 정렬 구현:

다양한 방법으로 구현할 수 있지만 인덱스만 신경써서 잘 나타내 주면 된다!

// 버블 정렬 오름차순
    public static void bubbleSort(int[] arr) {
    	// 0.
    	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 tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                }
            }
        }
        // 1.
        for(int i = 1; i<arr.length-1; i++){
            for(int j = 0; j < arr.length-i; j++){
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }

        // 2. 1과 같은 방법이지만 i인덱스 다르게 사용!
        for(int i = arr.length-1; i>0; i--){
            for(int j = 0; j<i; j++){
                if(arr[j]>arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                };
            }
        }
		// 3. 이 코드가 가장 그림과 유사
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 1; j <= i; j++) {
                if (arr[j-1] > arr[j]) {
                    int tmp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

삽입 정렬

앞의 데이터를 정렬해 가면서 삽입 위치를 찾아 정렬하는 방식이다.
해당위치의 데이터가 바로 자신의 위치를 찾아가기 때문에 이전의 모든 데이터는 오름차순으로 정렬된 상태를 가지게 된다.

삽입 정렬 예시

삽입 정렬 구현

// 삽입 정렬 오름차순
    public static void insertionSort(int[] arr) {
        for(int i = 1; i<arr.length; i++){
            for(int j = i; j>0; j--){
                if(arr[j] < arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                } else{
                    break;
                }
            }
        }

    }

선택 정렬

최소 또는 최대 값을 찾아 가장 앞 또는 뒤부터 정렬하는 방식이다.

선택 정렬 예시

선택 정렬 구현

// 선택 정렬 오름차순
private static void selectionSort(int[] arr) {
        // 1. 최솟값을 찾아 앞부터 교환
        for(int i = 0; i < arr.length-1; i++){
            int min = i; // 최솟값이 위치할 자리
            for(int j = i+1; j < arr.length; j++){
                if(arr[min] > arr[j]){
                    min = j; // 최소값이 위치한 인덱스
                }
            }
            int tmp = arr[min]; // 최솟값과 최솟값이 위치해야 할 자리의 값을 스왑하여 최솟값을 앞쪽에 둠
            arr[min] = arr[i];
            arr[i] = tmp;
        }

        //2. 최댓값을 찾아 뒤부터 교환
        for(int i = arr.length-1; i>0; i--){
            int max = i; // 최댓값이 위치할 자리
            for(int j = i-1; j>=0; j--){
                if(arr[max] < arr[j]){
                    max = j; // 최댓값이 위치한 인덱스
                }
            }
            int tmp = arr[i]; // 최댓값을 최댓값이 위치해야할 자리로 옮기기 위해 스왑 한다.
            arr[i] =  arr[max];
            arr[max] = tmp;
        }
    }

교훈

정렬을 구현할 때에는 인덱스 값을 신경을 써주자!

profile
백엔드 개발자로 일하고 싶어요 제발

0개의 댓글