정렬 (정처기 정리 부분, C로 구현)

 

정렬은 정말 해도 해도 헷갈린다 금붕어인가봄

정처기 하면서 그래도 완벽하게 익혔다고 생각했는데 또 가물가물..

그래서 정리를 해보려고 한다

 

<핵심 내용>

 

정처기 때 필기한 내용

 

<구현 (by C)>

- 윤성우의 열혈 자료구조 참고

- 구현이 쉬운 삽입, 선택, 버블 정렬만 정리했음..

 

1. 삽입 정렬 - 정렬이 완료된 영역과 그렇지 않은 영역을 구분하는 방법

void InerSort(int arr[], int n)
{
    int i, j;
    int insData;
    
    for (i=1; i<n; i++)
    {
        insData = arr[i];	//정렬 대상 저장 (맨 앞 데이터는 정렬이 됐다고 가정하고 두번째 데이터부터)
        
        for (j=i-1; j>=0; j--)
        {
            if (arr[j] > insData)
                arr[j+1] = arr[j];	//비교 대상 뒤로 한 칸 밀기
            else
                break;
        }
        
        arr[j+1] = insData;	//찾은 위치에 정렬 대상 삽입
    }
}

 

2. 선택 정렬 - 하나씩 선택해서 정렬 결과를 완성

별도의 메모리 공간이 요구된다는 단점 -> 가장 작은 것을 맨 앞으로 보내면서 개선 (하나씩 비워가면서 이동시킴)

void SelSort(int arr[], int n)
{
    int i, j;
    int maxIdx;
    int temp;
    
    for (i=0; i<n-1; i++)
    {
        maxIdx = i;
        
        for (j=i+1; j<n; j++)   //최솟값 탐색
        {
            if (arr[j] < arr[maxIdx])
                maxIdx = j;
        }   // for문 - 정렬되지 않은 부분
        
        // 교환 //
        temp = arr[i];
        arr[i] = arr[maxIdx];
        arr[maxIdx] = temp;
    }
}

 

3. 버블 정렬 - 가장 큰 숫자를 마지막에 넣음

void BubbleSort(int arr[], int n)
{
    int i, j;
    int temp;
    
    for (i=0; i<n-1; i++)
    {
        for (j=0; j<(n-i)-1; j++)
        {
            if (arr[j] > arr[j+1])
            {
                // 데이터의 교환 //
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}