Kim Ji Soo

I am an amazing person.

정렬 알고리즘

정의

컴퓨터의 기억공간 내에 순서 없이 배열되는 자료들 중에 레코드의 특정 항목을 순서화 하려는 기준을 따라 자료들을 배치하는 알고리즘

정렬 알고리즘의 동작 원리

동작원리 내용
판단 두 레코드의 대소 비교, 비교 대상은 레코드의 키 값
교환 판단 결과를 만족하는 경우 두 레코드를 교환시, 교환 대상은 레코드 자체


정렬 알고리즘의 분류

구분 정렬방법 내용
자료위치 내부정렬
(internal sorting) 		데이터 크기가 주기억장치 용량보다 적을 경우
기억장소를 활용하여 정렬하는 방법
외부정렬
(external sorting) 		데이터 크기가 주기억장소의 용량보다 클 경우
외부 기억장치(디스크, 테이프 등)를 사용하여 정렬하는 방법
교환 방법 직접정렬 레코드 전체를 교환하는 방법
간접정렬 레코드에 대한 포인터를 교환하는 방법


정렬 알고리즘의 유형

구분 알고리즘 유형 종류
내부정렬 삽입법 - 삽입정렬(Insertion Sort)
- 쉘정렬(Shell Sort)
교환법 - 선택정렬(Selection Sort)
- 퀵정렬(Quick Sort)
- 버블정렬(Bubble Sort)
선택법 - 힙정렬(Heap Sort)
병합법 - 머지정렬(Merge Sort)
분포에 의한 정렬 - 계수정렬(Count Sort)
- 기수정렬(Radix Sort)
외부정렬 균형적 다방향 정렬



선택 정렬알고리즘

배열에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 원소와 자리 교체, 나머지 원소들로 작업 반복하는 알고리즘

각 루프마다

  1. 최대 원소를 찾는다
  2. 최대 원소와 맨 오른쪽 원소를 교환한다
  3. 맨 오른쪽 원소를 제외한다

하나의 원소만 남을 때까지 위의 루프를 반복한다


import java.util.*;

public class Main {

    public static void main(String[] args) {

        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        for (int i = 0; i < n; i++) {
            int min_index = i; // 가장 작은 원소의 인덱스 
            for (int j = i + 1; j < n; j++) {
                if (arr[min_index] > arr[j]) {
                    min_index = j;
                }
            }
            // 스와프
            int temp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = temp;
        }

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}


버블 정렬알고리즘

선택정렬과 유사하게 제일 큰 원소를 옮기는 작업을 반복하나, 바로 이웃한 값과 비교하여 이동시키는 알고리즘

  1. 왼쪽부터 시작해 이웃한 쌍들을 비교해 나간다
  2. 순서대로 되어 있지 않으면 자리 바꾼다
  3. 맨 오른쪽 수를 대상에서 제외한다

앞의 작업을 반복하면서 계속 제외해 나간다
두개짜리 배열의 처리를 끝으로 정렬이 완료된다

삽입 정렬 알고리즘

2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘

  1. 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하고, 두번째 데이터가 어디로 들어갈지 판단한다. 첫번째 데이터의 왼쪽으로 들어가거나 오른쪽으로 들어가는 두 경우만 존재한다.

  2. 이어서 세번째 데이터가 어떤 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지 이다. 첫번째 데이터의 왼쪽, 두번째 데이터의 왼쪽 또는 그대로

삽입 정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다.
이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정 할 때(삽입될 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

즉, 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 되는것이다.

You may also enjoy