정렬 알고리즘 시간 복잡도, 공간 복잡도와 구현

정렬 알고리즘의 종류와 시간복잡도

백준 알고리즘에서 실버단계로 올라가면서 점점 알고리즘을 공부해야 한다는 필요성을 느꼈다. 그래서 가장 기본적인 정렬알고리즘에 대해 정리를 해보고 예시들도 풀어보았다. 우선 정렬알고리즘 종류와 시간 복잡도를 나타냈다. 언어는 c#이다.

위의 사진은 최악의 경우 시간복잡도 기준으로 맨위가 가장 느린순이다. 버블,삽입,선택,퀵은 O(n*n)이므로 모두 느린 정렬이다. 

단순하지만 비효율적 정렬

버블 정렬, 삽입 정렬, 선택정렬

복잡하지만 효율적 정렬

퀵 정렬, 쉘 정렬, 힙 정렬, 병합정렬

 

이번 블로그에서는 단순하지만 비효율적인 정렬을구현을 해보았다.

복잡하지만 효율적 정렬은 아래 링크에 작성해놨다.

정렬 알고리즘 시간 복잡도, 공간 복잡도와 구현(복잡하지만 효율적 정렬)

---

버블정렬

배열의 첫번째 원소부터 인접한 원소를 비교하고 순서가 잘못된 경우 교환하는 간단한 정렬 알고리즘입니다. 

공간복잡도는 알고리즘이 정렬을 진행할 때 입력으로 받은 리스트 안에서 바로 요소들의 위치를 교환(swap)하며 정렬이 이루어지기 때문에 O(1)이다.

시간 복잡도: O(N^2), 공간복잡도: O(1)

버블 정렬 알고리즘 작동원리

1. 리스트의 첫 번째 요소부터 시작하여 인접한 요소 쌍을 차례대로 비교합니다.
2. 만약 왼쪽 요소가 오른쪽 요소보다 크면(오름차순 정렬의 경우), 두 요소의 위치를 교환(swap)합니다.
3. 리스트의 끝까지 위 과정을 반복하여 가장 큰 요소를 리스트의 맨 뒤로 이동시킵니다. 이를 통해 가장 큰 요소가 정렬됩니다.
4. 이제 리스트의 끝에서 두 번째 요소까지 동일한 과정을 반복하여 두 번째로 큰 요소가 정렬됩니다.
5. 이 과정을 리스트의 모든 요소가 올바른 순서로 정렬될 때까지 계속 반복합니다.

버블 정렬 알고리즘 예시 

[ 5,3,8,4,2 ]를 버블정렬한 예시입니다.

---

 

백준예제문제

2750번: 수 정렬하기

 

구현

int input = Int32.Parse(Console.ReadLine());
int[] arr = new int[input];
for (int i = 0; i < arr.Length; i++)
{
    arr[i] = Int32.Parse(Console.ReadLine());
}

while (true)
{
    int Count = 0;
    for (int i = 0; i < arr.Length - 1; i++)
    {
        if (arr[i] > arr[i + 1])
        {
            int swap = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = swap;
            Count++;
        }
    }
    if (Count == 0)
        break;
}

 

---

 

삽입정렬

삽입 정렬(Insertion Sort)은 간단한 정렬 알고리즘 중 하나로, 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나누어 정렬되지 않은 부분의 각 요소를 순차적으로 정렬된 부분의 올바른 위치에 삽입하는 방식으로 작동한다.

삽입 정렬의 공간 복잡도는 O(1)이다.  정렬을 진행할 때 입력으로 받은 리스트 안에서 직접 요소들의 위치를 변경하며 정렬이 이루어지기 때문에 O(1)이다.

시간 복잡도: O(N^2), 공간복잡도: O(1)

삽입 정렬 알고리즘 작동원리

1. 리스트의 첫 번째 요소는 이미 정렬된 것으로 간주하고, 정렬되지 않은 부분의 첫 번째 요소를 선택한다
2. 선택한 요소를 정렬된 부분에서 올바른 위치에 삽입하기 위해, 정렬된 부분의 요소들과 비교하면서 왼쪽으로 이동한다
3. 적절한 위치를 찾으면 선택한 요소를 그 위치에 삽입한다
4. 정렬되지 않은 부분의 모든 요소에 대해 위 과정을 반복하여 전체 리스트를 정렬한다

삽입 정렬 알고리즘 예시 

 [ 5, 3, 8, 4, 2 ]를 삽입 정렬한 예시입니다.

---

백준예제문제

2750번: 수 정렬하기

 

구현

int input = Int32.Parse(Console.ReadLine());
int[] arr = new int[input];

for (int i = 0; i < arr.Length; i++)
{
    arr[i] = Int32.Parse(Console.ReadLine());
}

int key, other;

for (key = 1; key < input; key++)
{
    int key_num = arr[key];
    for (other = key - 1; other >= 0 && key_num < arr[other]; other--)
    {
        arr[other + 1] = arr[other];
    }
    arr[other + 1] = key_num;

}

foreach (int i in arr)
{
    Console.WriteLine(i);
}

 

---

 

선택정렬

리스트에서 최소값(또는 최대값)을 찾아 맨 앞의 값과 교환하는 방식으로 작동합니다. 이 과정을 리스트의 모든 요소에 대해 반복하여 전체 리스트를 정렬합니다.

공간복잡도 역시나 입력으로 받은 리스트 안에서 바로 요소들의 위치를 교환(swap)하며 정렬이 이루어지기 때문에 O(1)이다.

시간 복잡도: O(N^2), 공간복잡도: O(1)

선택 정렬 알고리즘 작동원리

1. 리스트에서 최소값(또는 최대값)을 찾습니다.
2. 그 값을 리스트의 맨 앞 요소와 교환합니다.
3. 이제 맨 앞 요소를 제외한 나머지 리스트에서 동일한 과정을 반복합니다.
4. 위 과정을 리스트의 모든 요소가 올바른 순서로 정렬될 때까지 계속 반복합니다.

선택 정렬 알고리즘 예시 

[ 5, 3, 8, 4, 2 ]를 선택 정렬한 예시입니다.

---

 

백준예제문제

2750번: 수 정렬하기

 

구현

int input = Int32.Parse(Console.ReadLine());
int[] arr = new int[input];
for (int i = 0; i < arr.Length; i++)
{
    arr[i] = Int32.Parse(Console.ReadLine());
}


for(int i=0; i< arr.Length; i++)
{
    int min = i;
    for(int j=i+1; j<arr.Length; j++)
    {
        if (arr[j] < arr[min])
            min = j;
    }

    if (i != min)
    {
        int swap = arr[i];
        arr[i] = arr[min];
        arr[min] = swap;
    }
}

foreach (int i in arr)
{
    Console.WriteLine(i);
}