[C,C++] 기본 3가지 정렬(선택정렬, 버블정렬, 삽입정렬)

1. 선택정렬

{0,1,2,3,4,5}  : 여기서 숫자는 인덱스 자리를 표현한다고 가정

{21,59,36,99,17} : 여기서 숫자는 값이라고 가정

 

루프를 돌아서 가장 작은 값을 찾은 뒤 0번째 인덱스와 교환한다.

(현재 21이 들어있는 자리와 5가지 숫자중 가장 작은 값이 교환된다.)

(이때 교체는 가장 작은숫자를 선택하여 한번만 이루어진다. -> 선택정렬)

 

그 다음 1번째 인덱스자리에 같은 루프가 돌고, 반복하게 되면 오름차순으로 값이 정렬된다.

void selectionSort(int arr[], int size) 
{
	int minIndex;						
	int i, j;
	for (i = 0; i < size-1; i++)		
	{
		minIndex = i; // i번째 인덱스자리에 가장 작은 값을 넣겠다는 의미
		for (j = i + 1; j < size; j++)  
		
			if (arr[j] < arr[minIndex]) 
			{
				minIndex = j; // 가장 작은 값이 들어있는 j번째 인덱스를 넣겠다는 의미

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

2. 버블정렬

버블 정렬은 선택정렬과 다르게 가장 큰값 or 가장 작은값을 찾아내지 않는다.

다만 바로 옆에 있는 값과 비교하여 정렬한다.

 

{0,1,2,3,4,5}  : 여기서 숫자는 인덱스 자리를 표현한다고 가정

{21,59,36,99,17} : 여기서 숫자는 값이라고 가정

 

이런식으로 루프를 돌다보면, 가장 오른쪽 인덱스에 가장 높은 숫자가 자연스럽게 배치된다.

(선택정렬은 가장 낮은 숫자부터 왼쪽에서 배치되고, 버블정렬은 가장 높은 숫자부터 오른쪽에서 배치된다.)

 

가장 오른쪽 배치가 끝나면 0~3번 인덱스만 루프를 돈다.  그 다음은 0~2번 인덱스, 이런식이다.

#include <iostream>

void bubbleSort(int* ptr, int sortSize);
void swap(int*a,int*b);


int main()
{
    int sort1[5]= {21,59,36,99,17};

    int sortSize = sizeof(sort1)/sizeof(int);
    bubbleSort(sort1,sortSize);

    for(int i = 0; i < sortSize; i++)
    {
        printf("%d ",sort1[i]);
    }
    printf("\n");
}

void bubbleSort(int* ptr, int sortSize) // 버블 정렬 함수
{
    for(int j = 1; j < sortSize; j++)
    {
        for(int i = 0; i < sortSize-j; i++)
        {
            if(*(ptr+i) > *(ptr+i+1))
            {
                swap(ptr+i,ptr+i+1);
            }
        }
    }
}

void swap(int*a,int*b) // 스왑 함수
{
    int temp = 0;
    temp = *a;
    *a = *b;
    *b = temp;
}

 

3. 삽입정렬

세 정렬중에 가장 복잡하다고 느꼈던 정렬이다.

정렬 순서는 아래와 같이 이루어진다.

1. 파란 네모를 숫자 크기를 먼저 비교를 한다. (빨간 네모는 정렬이 되었다고 보기 때문이다.)

2. 오른쪽이 더 숫자가 클 경우, 빨간 네모에서 버블정렬을 우측부터 수행한다.(우측부터 바로 옆 숫자와 크기를 비교한다는 뜻)

3. 삽입정렬이라고 불리는 이유는 빨간네모 가장 우측의 숫자가 자신의 자리를 찾아서 삽입되기 때문이다.

 

개인적으로 짜본 삽입정렬 코드는 다음과 같다.

근데 지금 생각해보니, 한가지 문제점이 있는것 같다.

빨간색네모안의 숫자가 정렬이 됬다고 본다면,

가장 우측의 숫자가 왼쪽의 숫자와 비교해서 자신이 더 크다면 더이상 버블정렬을 수행하면 안되는데

아래 내가 짠 코드는 가장 처음 파란색에서만 그런식으로 비교하고

한번 버블정렬 루프에 들어가면 끝까지 다 수행해버린다

#include <iostream>

void bubbleSort(int* ptr, int sortSize);
void swap(int*a,int*b);
void insertSort(int* ptr, int sortSize);


int main()
{
    int sort1[5]= {99,59,36,21,17};
    int sortSize = sizeof(sort1)/sizeof(int);

    insertSort(sort1,sortSize);

    for(int i = 0; i < sortSize; i++)
    {
        printf("%d ",sort1[i]);
    }
    printf("\n");
}

void insertSort(int* ptr, int sortSize) // 삽입정렬
{
    for(int i = 0; i < sortSize-1; i++)
    {
        //for(int i = 0; i < sortSize-j; i++)
        {
            if(*(ptr+i) > *(ptr+i+1))
            {
                bubbleSort(ptr,i+2); // 빨간네모에서 버블정렬
            }
        }
    }
}

void bubbleSort(int* ptr, int sortSize) // 버블정렬
{
    for(int j = 1; j < sortSize; j++)
    {
        for(int i = sortSize-1; i > 0; i--)
        {
            if(*(ptr+i) < *(ptr+i-1))
            {
                swap(ptr+i,ptr+i-1);
            }
        }
    }
}

void swap(int*a,int*b) // 스왑 합수
{
    int temp = 0;
    temp = *a;
    *a = *b;
    *b = temp;
}

블로그 쓰다가 수정해본 삽입정렬 코드는 다음과 같다.

버블정렬에서 swap을 하지 않게 될경우, return;을 주어 그냥 함수를 나가버리게 만들었다.

빨간네모는 정렬이 되어있으므로 스왑을 하는 경우가 아니면 당연히 자신의 인덱스 왼쪽 인덱스들은 정렬이 되어있기 때문이다.

#include <iostream>

void bubbleSort(int* ptr, int sortSize);
void swap(int*a,int*b);
void insertSort(int* ptr, int sortSize);


int main()
{
    int sort1[5]= {99,59,36,21,17};
    int sortSize = sizeof(sort1)/sizeof(int);

    insertSort(sort1,sortSize);

    for(int i = 0; i < sortSize; i++)
    {
        printf("%d ",sort1[i]);
    }
    printf("\n");
}

void insertSort(int* ptr, int sortSize) // 삽입정렬
{
    for(int i = 0; i < sortSize-1; i++)
    {
        //for(int i = 0; i < sortSize-j; i++)
        {
            if(*(ptr+i) > *(ptr+i+1))
            {
                bubbleSort(ptr,i+2); // 빨간네모에서 버블정렬
            }
        }
    }
}

void bubbleSort(int* ptr, int sortSize) // 버블정렬
{
    for(int j = 1; j < sortSize; j++)
    {
        for(int i = sortSize-1; i > 0; i--)
        {
            if(*(ptr+i) < *(ptr+i-1))
            {
                swap(ptr+i,ptr+i-1);
            }
            else
            {
            	return; // 큰 숫자를 만나지 않을 경우 버블정렬 함수에서 나가버린다.
            }
        }
    }
}

void swap(int*a,int*b) // 스왑 합수
{
    int temp = 0;
    temp = *a;
    *a = *b;
    *b = temp;
}

 

이상 가벼운 정렬 끝.