[기술 면접] 선택 정렬과 버블 정렬

버블 정렬

버블 정렬은 인접한 두 요소를 비교하고, 비교된 값이 작다면 서로 교환하는 방식으로 정렬하는 알고리즘을 말한다. 

 

버블 정렬의 시간 복잡도는 O(n^2)이다.

 

모든 원소에 대한 검사가 이루어지기 때문에 매우 정밀하다는 장점이 있지만, 그렇기에 시간이 오래걸린다는 단점이 있다.

 

버블 정렬 코드 (C#)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BubbleAlgorithm
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] data = { 10, 1, 15, 20, 5 };
            Console.Write("bubble data: ");
            for (int i = 0; i < data.Length; i++)
            {
                Console.Write(data[i] + " ");
            }

            Console.WriteLine();
            // 버블 정렬 알고리즘
            for (int i = 0; i < data.Length; i++) 
            {
                for(int j = i + 1; j < data.Length; j++)
                {
                    if (data[i] > data[j])
                    {
                        Swap(ref data[i], ref data[j]);
                    }
                }
                // 정렬마다 콘솔을 찍어봄
                for (int k = 0; k < data.Length; k++)
                {
                    Console.Write($"{data[k]}, ");
                }
                Console.WriteLine();
            }

        }

        private static void Swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }


    }
}

 

 

선택 정렬

 

선택 정렬은 버블 정렬과 유사한 정렬로 해당 순서에 어떤 원소를 넣을 지 선택하는 알고리즘을 말한다.

즉 정렬되지 않은 데이터의 최소값을 해당 데이터들의 가장 앞 부분에 위치하도록 하는 정렬 방식을 말하는 것이다.

 

선택 정렬의 시간 복잡도는 O(n^2)이다.

 

유사하지만 차이점은 버블 정렬은 하나의 원소로 나머지 원소들과 비교하는 과정을 모든 원소에 적용하는 것이고, 선택 정렬은 모든 원소에서 최소값을 찾아 가장 앞의 위치로 이동시키고 이동한 원소를 제외한 나머지에서 다시 같은 작업을 반복한다는 점에서 차이가 있다.

 

그래서 선택정렬은 정확도과 높다는 장점이 있지만, 버블 정렬보다 빠를 뿐, 마찬가지로 시간이 오래 걸린다는 단점이 있다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SelectAlgorithm
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] data = { 10, 1, 15, 20, 5 };
            Console.Write("data: ");
            for (int i = 0; i < data.Length; i++)
            {
                Console.Write(data[i] + " ");
            }
                
            Console.WriteLine();
            // 선택 정렬 알고리즘
            for (int i = 0; i < data.Length; i++)
            {
                int min = i;

                for(int j = i + 1;  j < data.Length; j++)
                {
                    // data의 앞과 바로 뒤를 비교
                    if (data[min] > data[j])
                        min = j;
                }

                Swap(ref data[i], ref data[min]);

                // 정렬마다 콘솔을 찍어봄
                for(int k = 0; k <  data.Length; k++)
                {
                    Console.Write($"{data[k]}, ");
                }
                Console.WriteLine();
            }

            Console.Write("정렬된 data: ");
            for (int i = 0; i < data.Length; i++)
            {
                Console.Write($"{data[i]}, ");
            }

        }

        // 두 수의 자리를 바꿔줌
        private static void Swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
    }
}