[자료구조] 선택정렬과 버블정렬 정의 및 차이

1. 선택정렬 (Selection Sort) :  가장 작은 수를 찾아서 맨 앞으로 보내는 것

선택정렬

방법

1) 배열의 처음부터 끝까지 반복문을 통해 가장 작은 수를 탐색

2) 가장 작은 수를 배열의 맨 앞으로 보내기

3) 그 다음 배열부터 다시 1),2) 행동 반복

 

즉, 이중 for문을 통해 구현하므로 시간 복잡도는 n^2,0이다.

 

* 자리바꾸기 공식의 로직
1. 맨 왼쪽자리 변수 temp 선언
2. 맨 왼쪽자리에 올 값
3. 2번의 값은 temp

 

    //선택정렬 :  가장 작은 것을 선택해서 맨 앞으로 보낸다
    void SelectionSort()
    {
       //외부루프는 첫번째 요소부터 길이까지 탐색
        for(int i = 0; i < num.Count-1 ; i++)
        {
            //최솟값 설정
            int minIdex = i;
            //하나하나씩 비교
            for(int j = i+1; j < num.Count; j++)
            {
                //만약에 최솟값이 탐색한 값보다 크다면
                if (num[minIdx] > num[j])
                {
                    //최솟값이 탐색한 값이 된다.
                    minIdex = j;
                }
            }
            //자리바꾸기 공식(1. 맨 왼쪽자리 변수 temp 선언 2. 맨 왼쪽자리에 올 값 3. 2번의 값이 temp)
            //temp는 맨 왼쪽자리 변수 선언
            int temp = num[i];
            //맨 왼쪽자리는 최솟값
            num[i] = num[minIdex];
            //최솟값은 temp
            num[minIdex] = temp;
        }

        foreach (int n in num)
        {
            
            Debug.Log(n);
        }

    }

---

2. 버블정렬 (Bubble Sort) : 앞 뒤의 연결된 숫자를 서로 비교해서 큰 값은 뒤로 이동, 작은 값은 앞으로 이동한다.

버블 정렬

 

바로 오른쪽 옆에 있는 숫자와 크기 비교해서 크기가 작으면 자리를 바꿔 큰 숫자부터 맨 오른쪽으로 위치하는 것

이것도 마찬가지로 이중 for문을 사용하여 시간복잡도는 n^2,0으로 선택정렬과 동일하다.

    //버블 정렬 : 앞 뒤의 연결된 숫자를 서로 비교해서 큰 값은 뒤로 이동, 작은 값은 앞으로 이동한다.
    void BubbleSort()
    {
        for(int i = 0; i < num.Count-1; i++)
        {
            for(int j = 0; j < num.Count-1-i; j++)
            {
                //두 수를 비교
                if (num[j] > num[j+1])
                {
                    //자리 변경
                    int temp = num[j];
                    num[j] = num[j + 1];
                    num[j + 1] = temp;
                }
            }
        }

        foreach (int n in num)
        {

            Debug.Log(n);
        }
    }

 

정렬은 가장 기초적인 알고리즘으로 이번 포스팅에서 정렬을 확실하게 이해하고 넘어가야했다. 그래서 이해하는데 시간이 오래 걸렸다.

선택정렬은 버블정렬과 동일한 시간복잡도이다. 하지만 성능면에서 선택정렬이 더 우수하다는 것을 깨달았다. 왜냐하면 버블정렬은 자리이동마다 계산을 해야하기 때문이다. 추가적으로 시간복잡도에 대해서도 이해할 수 있었다. 

 

*시간 복잡도 : 컴퓨터가 연산하는 수행횟수 Big O(n)