기술면접 - 선택 정렬과 버블 정렬에 대해 설명해주시고, 코드를 작성해보세요.

Q - 선택 정렬과 버블 정렬에 대해 설명해주시고, 코드를 작성해보세요.

A - 

선택정렬은 전체의 아이템의 위치를 변수에 저장한 후에 가장 작은 아이템과 위치를 바꾸는 방식

for(int i=0; i<arr.Length - 1; i++){

    int temp = i;

    for(int j= i+1; j < arr.Length; j++){

        if(arr[j] < arr[temp]) temp = j;

    }

    int num = arr[temp];

    arr[temp] = arr[i];

    arr[i] = num;

}

버블정렬은 현재요소와 다음요소의 값을 비교하여 다음요소의 값이 작다면 위치를 바꾸는 방식이다. (교환이 없을때 까지 반복)

for(int i=0; i<arr.Length - 1; i++){

    for(int j= 0; j < arr.Length - i - 1; j++){

        if(arr[j] > arr[j+1]){

            int temp = arr[j];

            arr[i] = arr[j+1];

            arr[j+1] = temp;

        }

    }

}

[GPT]

선택 정렬(Selection Sort)과 버블 정렬(Bubble Sort)은 기본적인 정렬 알고리즘 중 두 가지입니다. 이 두 정렬 방식은 이해하기 쉽고 구현하기도 간단하지만, 데이터의 양이 많을 때는 비효율적일 수 있습니다.

선택 정렬(Selection Sort)

선택 정렬은 배열 전체에서 가장 작은 요소를 찾아 첫 번째 위치에 놓고, 그 다음 작은 요소를 찾아 두 번째 위치에 놓는 방식으로 진행합니다. 이 과정을 배열의 모든 요소가 정렬될 때까지 반복합니다.

특징:

• 시간 복잡도: 평균 및 최악의 경우 O(n^2)
• 공간 복잡도: O(1)
• 불안정 정렬
• 작은 데이터 세트에 적합

csharp

      using System;
classProgram{
staticvoidSelectionSort(int[] arr)    {
int n = arr.Length;
for (int i = 0; i < n - 1; i++)
        {
// 현재 위치의 요소를 최소값으로 가정int minIdx = i;
for (int j = i + 1; j < n; j++)
            {
if (arr[j] < arr[minIdx])
                {
                    minIdx = j;
                }
            }
// 찾은 최소값을 현재 위치로 이동int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }
staticvoidMain(string[] args)    {
int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        SelectionSort(arr);
        Console.WriteLine("Sorted array");
foreach (int item in arr)
        {
            Console.Write(item + " ");
        }
    }
}
      

버블 정렬(Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여, 잘못된 순서(첫 번째 요소가 두 번째 요소보다 큰 경우)가 있으면 서로 위치를 바꾸는 방식으로 진행합니다. 이 과정을 배열이 정렬될 때까지 반복합니다.

특징:

• 시간 복잡도: 평균 및 최악의 경우 O(n^2), 최선의 경우 O(n) (이미 정렬된 경우)
• 공간 복잡도: O(1)
• 안정 정렬
• 작은 데이터 세트에 적합

csharp

      using System;
classProgram{
staticvoidBubbleSort(int[] arr)    {
int n = arr.Length;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
                {
// 인접한 요소를 비교하여 잘못된 순서일 경우 교체int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
    }
staticvoidMain(string[] args)    {
int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        BubbleSort(arr);
        Console.WriteLine("Sorted array");
foreach (int item in arr)
        {
            Console.Write(item + " ");
        }
    }
}
      

선택 정렬과 버블 정렬은 간단하고 직관적이지만, 정렬해야 할 요소의 수가 많아질수록 효율성이 떨어집니다. 따라서 큰 데이터 세트에는 더 효율적인 정렬 알고리즘(예: 퀵 정렬, 병합 정렬 등)을 사용하는 것이 좋습니다.