[데이터베이스] 내부정렬

내부정렬

버블 정렬(Bubble Sort)
정렬 범위를 좁혀나가면서 정렬합니다.
인접한 원소끼리 크기를 비교하여 크기에 따라 교환합니다.

BubbleSort(Arr:배열, n:원소 개수)
Loop(i:= n->1)  //i를 n로 초기화하여 점차 1씩 감소시키면서 1까지 반복
    Loop(j:=1->i) //j를 1로 초기화하여 점차 1씩 증가하면서 i까지 반복
        IF Arr[j-1] > Arr[j] Then //Arr[j-1] 값이 Arr[j]보다 크면
            Swap(Arr[j-1], Arr[j]) //Arr[j-1]과 Arr[j]를 교환

선택 정렬(Selection Sort)
정렬 범위를 좁혀나가면서 정렬합니다.
범위 내에서 제일 큰 값(혹은 제일 작은 값)을 찾아 맨 뒤(혹은 맨 앞)의 요소와 교환합니다.

SelectionSort(Arr:배열, n:원소 개수)
Loop(i:=0->n)  //i를 0으로 초기화하여 점차 1씩 증가하면서 n까지 반복
    mp:=i; //최대값의 위치를 i로 초기화 합니다.
    Loop(j:=i+1->n) //j를 i+1로 초기화하여 점차 1씩 증가하면서 n까지 반복
        IF Arr[mp] < Arr[j] Then //Arr[mp] 값보다 Arr[j] 값이 크면
            mp := j //최대값의 위치를 j로 설정합니다.
    Swap(Arr[mp], Arr[i]) //Arr[mp]와 Arr[i]를 교환

삽입 정렬(Insertion Sort)
정렬 범위를 넓혀가면서 정렬합니다.
정렬 범위에 포함한 맨 뒤의 데이터를 앞으로 이동하면서 자리를 찾아갑니다.

InsertionSort(Arr:배열, n:원소 개수)
Loop(i:=0->n)  //i를 1로 초기화하여 점차 1씩 증가하면서 n까지 반복    
    Loop(j:=i->1) //j를 i로 초기화하여 점차 1씩 감소하면서 1까지 반복
        IF Arr[j-1] < Arr[j] Then //Arr[j-1] 값이 Arr[j] 값이 크면
            Swap(Arr[j-1], Arr[j]) //Arr[j-1]와 Arr[j]를 교환
        Else
            Break Loop //Loop 탈출

쉘 정렬(Shell Sort)
쉘 정렬을 삽입 정렬 원리를 이용한 개념입니다.
쉘 정렬은 i번째 원소와 h 배수의 거리에 떨어진 원소들을 삽입 정렬합니다.
부분적으로 정렬 상태일 때 좋은 성능을 갖습니다.

퀵 정렬(Quick Sort)
피벗을 선택하여 피벗보다 작은 값들은 왼쪽으로 큰 값들은 오른쪽으로 보낸 후에 피벗의 자리를 확정시킵니다.
그리고 재귀적인 방법으로 피벗의 왼쪽 요소들과 오른쪽 요소들을 정렬합니다.
가장 빠른 방식으로 알려졌습니다.
하지만 어떠한 피벗을 선택하는가에 따라 현재 정렬 상태에 따라 성능에 영향을 미칩니다.

힙 정렬(Heap Sort)
완전 이진 트리(Complete Binary Tree, 전이진 트리)를 이용한 정렬 방식입니다.

2-Way 합병 정렬(Merge Sort)
정렬 상태의 두 개의 파일을 하나의 파일로 합병하는 정렬 방식입니다.

기수 정렬(Radix Sort)
우선 순위가 낮은 자리수부터 정렬하는 방식으로 버켓(Bucket) 정렬로도 부릅니다.

정렬 알고리즘에 관한 사항은 C언어 예제 카테고리와 디딤돌 알고리즘 with C 카테고리를 참고하세요.

너와 나의 연결고리 "공감"