TIL_68(버블정렬과 선택정렬)

 

23.11.09. 68차

 

오늘은 기술면접시간에 버블정렬과 선택정렬에 대해서 공부했다.

 

버블정렬은 배열에서 2개의 원소를 선택해 비교한다.
기본적으로 오름차순 정렬이라고 가정했을 때, 왼쪽의 원소가 오른쪽의 원소보다 크면 교환한다.
그 후 오른쪽으로 이동해가며 전부 정렬 될 때까지 반복한다.
최악의 경우 모든 원소를 다 교환해야하므로 버블 정렬의 시간복잡도는 O(n²)다.

버블정렬은 정렬을 가장 직관적으로 이해할수 있지만 효율이 떨어지기 때문에 그렇게 좋은 알고리즘은 아니다.

-코드-

class BubbleSort
    {
        static void Main(string[] args)
        {
            int[] arr = new int[]{ 1, 4, 3,  5, 9, 6, 2, 7, 8, 10 };
 
            int temp;
            int count = 0;
            for(int i = 0; i < arr.Length-1; i++)
            {
                for (int j = 0; j < arr.Length-1; j++)
                {
                    if(arr[j] < arr[j+1])  
                    {
                        temp = arr[j+1];
                        arr[j+1] = arr[j];
                        arr[j] = temp;
                    }
                    count++;
                }
            }
 
            Console.WriteLine("Count : {0}", count);
 
            for(int i = 0; i < arr.Length; i++)
                Console.Write(arr[i] + "\t");
        }
    }

선택정렬은 전체 원소중 가장 순서가 빠른 원소의 위치를 변수에 저장한다.
원소를 한바퀴 돌며 순서가 가장 빠른 원소의 위치를 기억하고 끝까지 다 돌았을 때 가장 순서가 빠른 원소와 맨 앞의 원소의 자리를 바꿔준다.
그 후 정렬되지 않은 부분중에서 가장 순서가 빠른 원소를 찾으며 반복한다.
선택정렬이 버블정렬보다 2배 더 빠를수 있음에도 최악의 경우가 있으므로 시간복잡도는 버블정렬과 마찬가지로 O(n²)다.

-코드-
class SelectionSort
    {
        static void Main(string[] args)
        {
            int[] arr = new int[]{ 1, 4, 3,  5, 9, 6, 2, 7, 8, 10 };
            int TargetIndex, temp;
 
            for(int i = 0; i < arr.Length-1; i++)
            {
                TargetIndex = i;
 
                for(int j = i+1; j < arr.Length; j++)
                {
                    if (arr[j] < arr[TargetIndex])
                        TargetIndex = j;
                }
                 
                if( i != TargetIndex)
                {
                    temp = arr[i];
                    arr[i] = arr[TargetIndex];
                    arr[TargetIndex] = temp;
                }
            }
 
            for (int i = 0; i < arr.Length; i++)
                Console.Write(arr[i] + "\t");
        }
    }